栈与队列

• • 1. 用栈实现队列
  • • [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)
  • 2. 用队列实现栈
  • • [225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/)
    • 两个队列实现
    • 一个队列实现
  • 3. 有效括号
  • • [20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/)
  • 4. 删除字符串中所有相邻重复项
  • • [1047. 删除字符串中的所有相邻重复项](https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/)
  • 5. 逆波兰表达式求值
  • • [150. 逆波兰表达式求值](https://leetcode.cn/problems/evaluate-reverse-polish-notation/)
  • 6. 前K个高频元素
  • • [347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)

1. 用栈实现队列

232. 用栈实现队列

两个栈,一个用来输入,一个用来输出

1. 先往输入栈中放,需要输出时,就将输入栈中所有元素放入输出栈(此时顺序会颠倒)
2. 之后如果还需要输出时,先判断输出栈是否为空,不为空直接输出,为空需要将输入栈执行①操作

class MyQueue {Stack stackIn;Stack 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());}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

2. 用队列实现栈

225. 用队列实现栈

两个队列实现

class MyStack {LinkedList queue1; LinkedList queue2; public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue1.offer(x);}public int pop() {//把除了最后一个元素,其他都拿去queue2while(queue1.size() > 1){queue2.offer(queue1.poll());}//交换,让元素保持在queue1中LinkedList temp = queue1;queue1 = queue2;queue2 = temp;return queue2.poll();}public int top() {//把除了最后一个元素,其他都拿去queue2while(queue1.size() > 1){queue2.offer(queue1.poll());}int res = queue1.peek();//最后一个也放过去queue2.offer(queue1.poll());//交换,让元素保持在queue1中LinkedList temp = queue1;queue1 = queue2;queue2 = temp;return res;}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

一个队列实现

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

class MyStack {LinkedList queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {queue.offer(x);}public int pop() {int length = queue.size();for(int i = 0; i < length - 1; i++){queue.offer(queue.poll());}return queue.poll();}public int top() {int length = queue.size();for(int i = 0; i < length - 1; i++){queue.offer(queue.poll());}int res = queue.peek();queue.offer(queue.poll());return res;}public boolean empty() {return queue.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

3. 有效括号

20. 有效的括号

方便起见,可以在存入字符的时候,存入对应的字符比如( 存入 )这样就能直接比对了

class Solution {public boolean isValid(String s) {char[] b = s.toCharArray();Stack stack = new Stack<>();for(int i = 0; i < b.length; i++){if(b[i] == '(') {stack.push(')');}else if(b[i] == '{'){stack.push('}');}else if(b[i] == '['){stack.push(']');}else{//没有左边,出现右边if(stack.isEmpty()) return false;if(stack.peek() == b[i]){stack.pop();}else{//不匹配return false;}}}return stack.isEmpty() ? true : false;}
}

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

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

每次取出栈顶元素进行比较即可

最终倒叙输出栈

class Solution {public String removeDuplicates(String s) {char[] c = s.toCharArray();Stack stack = new Stack<>();StringBuilder sb = new StringBuilder();for(int i = 0; i < c.length; i++){if(stack.size() == 0){stack.push(c[i]);continue;}if(stack.peek() == c[i]){stack.pop();}else{stack.push(c[i]);}}int sum = stack.size();for(int i = 0; i < sum; i++){sb.append(stack.pop());}sb.reverse();return sb.toString();}
}

5. 逆波兰表达式求值

150. 逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {int n = tokens.length;Stack stack = new Stack<>();for(int i = 0; i < n; i++){if(!isSymbol(tokens[i])){stack.push(tokens[i]);}else{int p2 = Integer.valueOf(stack.pop());int p1 = Integer.valueOf(stack.pop());if(tokens[i].equals("+")){stack.push(String.valueOf(p1 + p2));}else if(tokens[i].equals("-")){stack.push(String.valueOf(p1 - p2));}else if(tokens[i].equals("*")){stack.push(String.valueOf(p1 * p2));}else if(tokens[i].equals("/")){stack.push(String.valueOf(p1 / p2));}}}return Integer.valueOf(stack.peek());}//判断是否为符号public boolean isSymbol(String s){return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");}
}

6. 前K个高频元素

347. 前 K 个高频元素

1. 先使用hashmap获取每个元素出现的个数
2. 存取优先队列中(堆)完成排序
3. 取出前k个

注意在把entry这种二元组存入别的集合时,如果两个都为相同数据结构如int

可以直接使用int数组来存储

class Solution {public int[] topKFrequent(int[] nums, int k) {//得到每个元素的个数HashMap map = new HashMap<>();for(int i : nums){map.put(i, map.getOrDefault(i, 0) + 1);}//使用堆排序,倒序PriorityQueue queue = new PriorityQueue<>((a,b)->b[1] - a[1]);for (Integer i : map.keySet()) {queue.offer(new int[]{i, map.get(i)});}int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = queue.poll()[0];}return res;}
}