【leetcode】栈与队列总结

本文内容来自于代码随想录

栈

用栈实现队列

两个栈实现队列。思路：两个栈分别表示入栈和出栈。

1. 入队：直接入栈
2. 出队：
   a. 出栈为空，先把入栈中的元素全部放到出栈中（相当于反过来，这样在出栈的时候先进的元素就变成先出了），然后弹出栈顶
   （2）出栈不为空，那么栈顶就是要出队的元素，直接弹出栈顶

说明：当出栈入栈都有元素的时候，出栈中的元素一定是先入队的，要弹栈优先弹出栈中的元素。出栈空了，再把入栈的元素放到出栈中，再弹栈。

/**
两个栈分别表示入栈和出栈
1. 入队：直接入栈
2. 出队：
（1）出栈为空，先把入栈中的元素全部放到出栈中（相当于反过来，这样在出栈的时候先进的元素就变成先出了），然后弹出栈顶
（2）出栈不为空，那么栈顶就是要出队的元素，直接弹出栈顶
说明：当出栈入栈都有元素的时候，出栈中的元素一定是先入队的，要弹栈优先弹出栈中的元素。出栈空了，再把入栈的元素放到出栈中，再弹栈*/class MyQueue {Stack<Integer> in;Stack<Integer> out;public MyQueue() {in = new Stack<>();out = new Stack<>();}public void push(int x) {in.push(x);}public int pop() {if (out.empty()) {inToOut();}return out.pop();}public int peek() {if (out.empty()) {inToOut();}return out.peek();}public boolean empty() {return in.empty() && out.empty();}public void inToOut() {// 把入栈中的元素全部放到出栈中while (!in.empty()) {int x = in.pop();out.push(x);}}
}/*** 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();*/

队列

用队列实现栈

两个队列实现栈。用栈模拟队列相对就容易一点，用两个队列。区别在于：另外一个队列只是用来备份数据。在弹栈的时候

1. 先将 q1 中的数据出队到只剩一个，保存在 q2 中
2. 将 q1 中最后一个数据出队。最后一个数据就是栈顶
3. 将 q2 中的数据再出队，保存到 q1 中

class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {q1.offer(x);}public int pop() {oneToTwo();int x = q1.poll();TwoToOne();return x;}public int top() {oneToTwo();int x = q1.poll();q2.offer(x);TwoToOne();return x;}public boolean empty() {return q1.isEmpty();}public void oneToTwo() {while (q1.size() > 1) {int x = q1.poll();q2.offer(x);}}public void TwoToOne() {while (!q2.isEmpty()) {int x = q2.poll();q1.offer(x);}}
}/*** 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();*/

经典题型

• 有效的括号
• 删除字符串中的所有相邻重复项
• 逆波兰表达式求值
• 前 K 个高频元素