栈与队列相关算法题
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
private int toPeek;
private int size;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
if (this.empty()) {
this.toPeek = x;
}
stack1.push(x);
this.size ++;
}
public int pop() {
if (this.empty()) {
return 0;
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
int toPop = stack2.pop();
if (!stack2.empty()) {
this.toPeek = stack2.peek();
}
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
this.size--;
return toPop;
}
public int peek() {
return this.toPeek;
}
public boolean empty() {
return this.size == 0;
}
}
|
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop
和 empty）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| public class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
private int top;
private int size;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
this.top = x;
queue1.add(x);
this.size ++;
}
public int pop() {
if (this.empty()) {
return 0;
}
for (int i = 0; i < size - 1; i++) {
if (i == size - 2) {
this.top = queue1.peek();
}
queue2.add(queue1.poll());
}
int toPop = queue1.poll();
while (!queue2.isEmpty()) {
queue1.add(queue2.poll());
}
this.size--;
return toPop;
}
public int top() {
return this.top;
}
public boolean empty() {
return this.size == 0;
}
}
|
给定一个只包括
'('，')'，'{'，'}'，'['，']'
的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
1
2
3
4
| 输入：s = "()[]{}"
输出：true
输入：s = "([)]"
输出：false
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean isValid(String s) {
if (s == null || s.isEmpty()) {
return false;
}
char[] chars = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '{' || chars[i] == '[' || chars[i] == '(') {
stack.push(chars[i]);
} else if (stack.empty()) {
return false;
} else if (chars[i] == '}' && stack.pop() != '{') {
return false;
} else if (chars[i] == ')' && stack.pop() != '(') {
return false;
} else if (chars[i] == ']' && stack.pop() != '[') {
return false;
}
}
return stack.empty();
}
}
|
根据逆波兰表示法，求表达式的值。
有效的算符包括
+、-、*、/
。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为
0 的情况。
1
2
3
| 输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>();
Set<String> symbols = new HashSet<>();
symbols.add("+");
symbols.add("-");
symbols.add("*");
symbols.add("/");
for (int i = 0; i < tokens.length; i++) {
if (symbols.contains(tokens[i])) {
int a = stack.pop();
int b = stack.pop();
if ("+".equals(tokens[i])) {
stack.push(b + a);
} else if ("-".equals(tokens[i])) {
stack.push(b - a);
} else if ("*".equals(tokens[i])) {
stack.push(b * a);
} else if ("/".equals(tokens[i])) {
stack.push(b / a);
}
continue;
}
stack.add(Integer.valueOf(tokens[i]));
}
return stack.peek();
}
}
|