用栈实现队列 & 用队列实现栈

概览

• 目标1：用两个 栈 实现一个 队列（FIFO）
• 目标2：用一个 队列 实现一个 栈（LIFO）

用两个栈实现队列

思路

1. 使用两个栈：

   • in：专门接收新元素（入队）

   • out：专门负责出队/取队头

2. 只在 out 为空时，将 in 的所有元素逐个 pop 并 push 到 out；这样原先进入 in 的先入元素会在 out 顶部，满足 FIFO。倒栈时，必须把 in 全部倒光（保证顺序）。

3. push(x)：压入 in；（本实现选择“立即尝试倒栈”，也可延迟到 pop/peek 时再倒）

4. pop()/peek()：若 out 为空则先倒栈，再从 out 进行操作。

5. 判空：in 与 out 同时为空。

 class MyQueue{
        public Stack<Integer> in;
        public Stack<Integer> out;

        public MyQueue(){
            in = new Stack<Integer>();
            out = new Stack<Integer>();
        }
        //倒数据，从in进栈，把数据倒入out栈
        private void inToOut(){
            if(out.empty()){
                while(!in.empty()){
                    out.push(in.pop());
                }
            }
        }

        public void push(int n){
            in.push(n);
            inToOut();
        }

        public int pop(){
            inToOut();
            return out.pop();
        }

        public int peek(){
            inToOut();
            return out.peek();
        }

        public boolean empty(){
            return in.isEmpty() && out.isEmpty();
        }
    }

用一个队列实现栈

思路

1. 入栈 push(x)：

   • 先把 x 入队到队尾；

   • 记录之前已有元素个数 n，把这 n 个旧元素依次从队头取出再放回队尾；

   • 旋转后，x 来到队头，成为“栈顶”。

2. 出栈 pop()：

   • 直接 poll() 队头即可（因为队头就是当前“栈顶”）。

3. 取顶 top()：

   • 直接 peek() 队头。

4. 判空：队列是否为空。

class MyStack{
        Queue<Integer> queue;

        public MyStack(){
            queue = new LinkedList<Integer>();
        }
        //O(n)
        //记录当前队列元素个数，加入新的数字后，依次把前面的从队头取出再从队尾插入，这样就是栈的顺序
        public void push(int x){
            int n = queue.size();
            queue.offer(x);
            for(int i = 0;i<n;i++){
                queue.offer(queue.poll());
            }
        }

        public int pop(){
            return queue.poll();
        }

        public int top(){
            return queue.peek();
        }

        public boolean empty(){
            return queue.isEmpty();
        }
    }