LeeCode 225: 用队列实现栈

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 283

题目：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
· void push(int x) 将元素 x 压入栈顶。
· int pop() 移除并返回栈顶元素。
· int top() 返回栈顶元素。
· boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

方法一：

思路：
在用栈实现队列的题中，由于栈是后进先出，头插头取，经过两个栈的倒腾之后，起顺序就可以与队列一致。
但用队列实现栈的题中，这种思想不可用，两次倒腾后，顺序并不会发生改变。
不过还是需要两个队列：

将新加入的元素放进队列2
若队列1有元素，则将队列1的元素依次添加至队列2
将队列1和队列2 交换，此时队列1的顺序就与栈一致了！

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }
    
    public void push(int x) {
        //1. 输入的数先放在q2
        q2.add(x);
        //2. 若q1有数就放到q2(队列是尾插头取)
        while(!q1.isEmpty()){
            q2.add(q1.poll()); //q1会弹为空
        }
        //3. 交换q1 q2 ，交换后q2为空
        Queue<Integer> temp=q1;
        q1=q2;
        q2=temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}