队列 (Queue) and 栈 (Stack)
代码随想录-总汇 中包含队列和栈的基础知识
题目
双栈实现队列题
很简单，一个栈负责暂时储存元素，另一个栈若为空的时候从第一个栈拿元素 aka 一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
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
| class MyQueue {
int count = 0;
Deque<Integer> dq1, dq2;
public MyQueue() {
dq1 = new ArrayDeque<>();
dq2 = new ArrayDeque<>();
}
public void push(int x) {
count++;
dq1.push(x);
}
public int pop() {
count--;
moveElements();
return dq2.pop();
}
private void moveElements() {
if (dq2.isEmpty()) {
while (!dq1.isEmpty()) {
int x = dq1.pop();
dq2.push(x);
}
}
}
public int peek() {
moveElements();
return dq2.peek();
}
public boolean empty() {
return count == 0;
}
}
|
用两个数组时，核心在于一个辅助数组用于置换，从而始终保持有一个数组的头为最后一个进来的元素，以达到FILO的结果：
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
| class MyStack {
Queue<Integer> q1, q2;
int count = 0;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
count++;
}
public int pop() {
count--;
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return count == 0;
}
}
|
这道题也可以只用一个Queue来做：
其实相当于形成了个循环队列，只不过开头一定是新进来的那个元素
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
| class MyStack {
Queue<Integer> q;
int count = 0;
public MyStack() {
q = new LinkedList<>();
}
public void push(int x) {
int size = q.size();
q.offer(x);
for (int i = 0; i < size; i++) {
q.offer(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}
|
括号匹配是使用栈解决的经典问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean isValid(String s) {
char[] s2Char = s.toCharArray();
Deque<Character> dq = new ArrayDeque<>();
for (char c : s2Char) {
if (c == '(') {
dq.push(')');
} else if (c == '{') {
dq.push('}');
} else if (c == '[') {
dq.push(']');
} else {
if (dq.isEmpty() || dq.peek() != c) {
return false;
}
dq.pop();
}
}
return dq.isEmpty();
}
}
|
本题有点像祖玛游戏
Credit to: LC详解 - 负雪明烛
本题要点：
- 两个相邻且相同字符会被删除。（注意：是两个！）
- 删除字符串中两个相邻并且相同的字符可能会产生新的相邻并且相同的字符。 比如对于 abba ，删除 bb 之后， aa 会碰到一起，也需要继续把 aa 删掉。
所以：
① 并不能一次删除操作就能达到目的；而应该在每次删除一对相邻且相同的字符之后、再看新的字符串是否存在相邻且相同的一对字符。
② 如果存在多组的相邻且相同的字符时，先删除哪一对对最终结果是没有影响的。比如对于 abbacca ，无论先删除 bb 还是先删除 cc 最终的结果都是 a 。
通过 ① 我们得出：需要用一个数据结构缓存结果，这个数据结构应该是后进先出，也就是栈！
通过 ② 我们得出：可以从左到右遍历一次输入字符串 S 的所有字符 Si，把 Si 跟栈顶元素比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public String removeDuplicates(String s) {
char[] s2Char = s.toCharArray();
Deque<Character> dq = new ArrayDeque<>();
for (char c : s2Char) {
if (!dq.isEmpty() && c == dq.peekLast()) {
dq.removeLast();
} else {
dq.addLast(c);
}
}
StringBuilder sb = new StringBuilder();
while (!dq.isEmpty()) {
sb.append(dq.removeFirst());
}
return sb.toString();
}
|
这是一道关于「表达式计算」的题目。所有的「表达式计算」问题都离不开「栈」。
思路总结：遇到数字压栈，遇到符号取出数字，计算，压栈更新后的数字。
用Deque：
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
| public int evalRPN(String[] tokens) {
Deque<String> dq = new ArrayDeque<>();
for (String token : tokens) {
if (token.equals("+")) {
int right = Integer.parseInt(dq.removeLast());
int left = Integer.parseInt(dq.removeLast());
String res = String.valueOf(left + right);
dq.addLast(res);
} else if (token.equals("*")) {
int right = Integer.parseInt(dq.removeLast());
int left = Integer.parseInt(dq.removeLast());
String res = String.valueOf(left * right);
dq.addLast(res);
} else if (token.equals("-")) {
int right = Integer.parseInt(dq.removeLast());
int left = Integer.parseInt(dq.removeLast());
String res = String.valueOf(left - right);
dq.addLast(res);
} else if (token.equals("/")) {
int right = Integer.parseInt(dq.removeLast());
int left = Integer.parseInt(dq.removeLast());
String res = String.valueOf(left / right);
dq.addLast(res);
} else {
dq.addLast(token);
}
}
int ret = Integer.parseInt(dq.removeLast());
return ret;
}
|
数组模拟栈：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int evalRPN(String[] ts) {
int[] d = new int[ts.length];
int hh = 0, tt = -1;
for (String s : ts) {
if ("+-*/".contains(s)) {
int b = d[tt--], a = d[tt--];
d[++tt] = calc(a, b, s);
} else {
d[++tt] = Integer.parseInt(s);
}
}
return d[tt];
}
int calc(int a, int b, String op) {
if (op.equals("+")) return a + b;
else if (op.equals("-")) return a - b;
else if (op.equals("*")) return a * b;
else if (op.equals("/")) return a / b;
else return -1;
}
}
|
两个难点：
- 我们需要求 k 窗口内的 最大值
- 不能够使用优先队列
- 因为优先队列排序后，要pop的元素可能不是排序后的元素了。
- 比如：1 3 -1 -3
- 队列中 3 1 -1 -3 此时会pop 3 而不是 1
因此需要自己设计一个数据结构支持：
- Pop()
- Push()
- getMaxValue()
- 数据结构内部单调递减，也就是 单调队列和单调栈
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
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MonolithicDownQueue monolithicDownQueue = new MonolithicDownQueue();
int left = 0, right = 0;
List<Integer> res = new ArrayList<>();
while (right < k) {
monolithicDownQueue.push(nums[right]);
right++;
}
res.add(monolithicDownQueue.getMaxValue());
while (right < nums.length) {
monolithicDownQueue.pop(nums[left]);
monolithicDownQueue.push(nums[right]);
res.add(monolithicDownQueue.getMaxValue());
left++;
right++;
}
return res.stream().mapToInt(i -> i).toArray();
}
class MonolithicDownQueue {
Deque<Integer> dq = new ArrayDeque<>();
void pop(int value) {
if (!dq.isEmpty() && dq.peekFirst() == value) {
dq.removeFirst();
}
}
void push(int value) {
while (!dq.isEmpty() && value > dq.peekLast()) {
dq.removeLast();
}
dq.addLast(value);
}
int getMaxValue() {
return dq.isEmpty() ? 0 : dq.peekFirst();
}
}
}
|
本题用到了 优先队列 + Map
Highlight: 用的是小顶堆，这样就不用维护所有的值而只维护k个元素，因为是不断把最小的元素pop()出去, 因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。 从而由 nlogn -> nlogk。
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
| public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> num2Count = new HashMap<>();
for (int i : nums) {
num2Count.put(i, num2Count.getOrDefault(i, 0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
for (Map.Entry<Integer, Integer> numEntry : num2Count.entrySet()) {
int[] cur = new int[]{numEntry.getKey(), numEntry.getValue()};
if (pq.size() < k) {
pq.add(cur);
} else {
if (pq.peek()[1] >= numEntry.getValue()) continue;
pq.poll();
pq.add(cur);
}
}
int[] ret = new int[k];
for (int i = k - 1; i >= 0; i--) {
ret[i] = pq.poll()[0];
}
return ret;
}
|
