数据结构——栈与队列相关题目

232. 用栈实现队列

232. 用栈实现队列

使用栈实现队列的下列操作：

• push(x) – 将一个元素放入队列的尾部。
• pop() – 从队列首部移除元素。
• peek() – 返回队列首部的元素。
• empty() – 返回队列是否为空。

说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路

需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中private void dumpstackIn(){if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}

225. 用队列实现栈

225. 用队列实现栈

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

1.两个队列实现栈

队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

使用两个 Queue 实现：

class MyStack {Queue<Integer> queue1; // 和栈中保持一样元素的队列Queue<Integer> queue2; // 辅助队列public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> queueTemp;queueTemp = queue1;queue1 = queue2;queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中}public int pop() {// 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1return queue1.poll(); }public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}

使用两个 Deque 实现：

class MyStack {// Deque 接口继承了 Queue 接口// 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirstDeque<Integer> que1;Deque<Integer> que2;public MyStack() {que1 = new ArrayDeque<>();//双端队列que2 = new ArrayDeque<>();}public void push(int x) {que1.addLast(x);}public int pop() {int size = que1.size();size--;// 将que1导入que2 ，留下最后一个值while (size-- > 0) {que2.addLast(que1.peekFirst());que1.pollFirst();}//删除que1中最后的元素并作为返回结果int res = que1.pollFirst();// 将que2对象的引用赋给que1,此时que1，que2指向同一个队列que1 = que2;// 如果直接操作que2，que1也会受到影响，所以为que2分配一个新的空间que2 = new ArrayDeque<>();return res;        }public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}

2.一个队列实现栈

队列模拟栈，其实一个队列就够了

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

class MyStack {// Deque 接口继承了 Queue 接口Deque<Integer> que1;public MyStack() {que1 = new ArrayDeque<>();//双端队列}public void push(int x) {que1.addLast(x);}public int pop() {int size = que1.size();size--;while (size-- > 0) {//队列头部的元素（除了最后一个元素外） 重新添加到队列尾部que1.addLast(que1.peekFirst());que1.pollFirst();}int res = que1.pollFirst();return res;}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}

ArrayDeque双端队列可直接使用提供的API实现：(没啥意义了)

class MyStack {// Deque 提供了实现堆栈的push,pop,peekDeque<Integer> que1;public MyStack() {que1 = new ArrayDeque<>();//双端队列}public void push(int x) {que1.push(x);}public int pop() {return que1.pop();        }public int top() {return que1.peek();}public boolean empty() {return que1.isEmpty();}
}

20. 有效的括号

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false

思路

括号匹配是使用栈解决的经典问题。
编译原理中，编译器在词法分析的过程中处理括号、花括号等这个符号的逻辑，也是使用了栈这种数据结构。

由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
   

2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。
   

3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。
   
   代码随想录动画：
   

字符串遍历完之后，栈是空的，就说明全都匹配了。

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

技巧：在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了

时间复杂度：$O(n)$，其中 nn 是字符串 ss 的长度。
空间复杂度：$O(n+\mid \Sigma \mid )$，其中Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。

class Solution {public boolean isValid(String s) {Deque<Character> deque = new LinkedList<>();char ch;for (int i=0;i<s.length();i++) {ch = s.charAt(i);//碰到左括号，就把相应的右括号入栈if (ch=='(') {deque.push(')');} else if (ch=='{') {deque.push('}'); } else if (ch=='[') {deque.push(']');} else if (deque.isEmpty()||deque.peek()!=ch) {//栈已经为空或匹配不对return false;} else {//如果是右括号判断是否和栈顶元素匹配//匹配则从栈中删除deque.pop();}}//最后判断栈中是否还有元素return deque.isEmpty();}
}

1047. 删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca”
输出：“ca”
解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

思路

本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。
可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。

从栈中弹出剩余元素，因为从栈里弹出的元素是倒序的，所以在对字符串进行反转一下，就得到了最终的结果。

用Deque作为堆栈：

class Solution {public String removeDuplicates(String s) {//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlistArrayDeque<Character> deque = new ArrayDeque<>();char ch;for (int i=0;i<s.length();i++) {ch = s.charAt(i);if (deque.isEmpty()||deque.peek()!=ch) {deque.push(ch);} else {deque.pop();}}String str = "";while (!deque.isEmpty()) {//直接把删除的元素放在前面拼接//否则还需要反转字符串str = deque.pop() + str;}return str;}
}

拿字符串直接作为栈，省去了栈还要转为字符串的操作：

class Solution {public String removeDuplicates(String s) {// 将 res 当做栈StringBuffer res = new StringBuffer();// top为 res 的长度int top = -1;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--if (top >= 0 && res.charAt(top) == c) {res.deleteCharAt(top);top--;// 否则，将该字符入栈，同时top++} else {res.append(c);top++;}}return res.toString();}
}

拓展：双指针

class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int fast = 0;int slow = 0;while (fast< s.length()) {// 直接用fast指针覆盖slow指针的值ch[slow] = ch[fast];// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了if(slow > 0 && ch[slow] == ch[slow - 1]){slow--;}else{slow++;}fast++;}return new String(ch,0,slow);}
}

155. 最小栈

155. 最小栈

150. 逆波兰表达式求值

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: [“2”, “1”, “+”, “3”, " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入: [“4”, “13”, “5”, “/”, “+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入: [“10”, “6”, “9”, “3”, “+”, “-11”, " * ", “/”, " * ", “17”, “+”, “5”, “+”]

输出: 22

解释:该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

思路

本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这就是一个相邻元素做运算的过程，出现运算符就要对之前的元素计算

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<>();for (int i=0;i<tokens.length;i++) {if ("+".equals(tokens[i])) {stack.push(stack.pop()+stack.pop());} else if ("-".equals(tokens[i])) {stack.push(-stack.pop()+stack.pop());} else if ("*".equals(tokens[i])) {stack.push(stack.pop()*stack.pop());} else if ("/".equals(tokens[i])) {int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2/temp1);} else {stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}
}

239. 滑动窗口最大值

239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

进阶：
你能在线性时间复杂度内解决此题吗？

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

单调队列

我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。队列里的元素一定是要排序的，而且要最大值放在出队口。

但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。
实际上没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。

代码随想录动画：

对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

设计单调队列的时候，pop，和push操作要保持如下规则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

时间复杂度： $O(n)$
空间复杂度： $O(k)$

自定义单调队列：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1) {return nums;}//结果数组的长度int len = nums.length - k + 1;int[] res = new int[len];int num = 0;MyQueue myQueue = new MyQueue();for (int i=0;i<k;i++) {myQueue.add(nums[i]);}res[num++] = myQueue.peek();for (int i = k; i < nums.length; i++) {//滑动窗口移除最前面的元素，移除时判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[num++] = myQueue.peek();}return res;}
}
class MyQueue {Deque<Integer> deque = new LinkedList<>();//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() && val == deque.peek()) {deque.poll();}}//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2void add(int val) {while (!deque.isEmpty() && val > deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}

利用双端队列手动实现单调队列：

/*** 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)*/
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int res[] = new int[nums.length-k+1];int idx = 0;for (int i=0;i<nums.length;i++) {// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出while(!deque.isEmpty() && deque.peek() < i - k + 1){deque.poll();}// 2.单调就要保证每次放进去的数字要比末尾的都大，否则也弹出while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offer(i);// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了if(i >= k - 1){res[idx++] = nums[deque.peek()];}}return res;}
}

PS：题解中单调队列里的pop和push接口，仅适用于本题。单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。

347. 前 K 个高频元素

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 $O(n\log n)$ , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

思路

这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种容器适配器就是优先级队列。
为什么不用快排呢， 使用快排要将map转换为数组的结构，然后对整个数组进行排序，效率较低。而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

如果定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

寻找前k个最大元素流程如代码随想录图所示：（图中的频率只有三个，所以正好构成一个大小为3的小顶堆，如果频率更多一些，则用这个小顶堆进行扫描）

class Solution {public int[] topKFrequent(int[] nums, int k) {int[] result = new int[k];HashMap<Integer, Integer> map = new HashMap<>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}Set<Map.Entry<Integer, Integer>> entries = map.entrySet();// 根据map的value值正序排，相当于一个小顶堆// 使用lambda表达式PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue()); for (Map.Entry<Integer, Integer> entry : entries) {queue.offer(entry);if (queue.size() > k) {queue.poll();}}for (int i = k - 1; i >= 0; i--) {result[i] = queue.poll().getKey();}return result;}
}