【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 个高频元素