用两个栈来实现队列的功能，支持队列的基本操作（add、poll、peek）

题目：

        用两个栈实现队列，支持队列的基本操作（add、poll、peek）

解决方案：

        队列是先进先出（FIFO）的数据结构，而栈是后进先出（LIFO）。我们可以用两个栈来模拟队列的操作。有两种不同的解决方案：

方案一：

思路：

一个栈专门用于入队（stack1），另一个栈专门用于出队（stack2）

- 入队操作（add）：直接将元素压入stack1。

- 出队操作（poll）和查看队首元素（peek）：

如果stack2为空，则将stack1中的所有元素依次弹出并压入stack2，这样stack2的栈顶就是队首元素。

如果stack2不为空，则直接操作stack2的栈顶。

代码实现：

import java.util.Stack;

public class TwoStackQueue1 {
    private final Stack<Integer> stackIn;
    private final Stack<Integer> stackOut;

    public TwoStackQueue1() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    // 入队操作
    public void add(int value) {
        stackIn.push(value);
    }

    // 出队操作
    public Integer poll() {
        transferIfNeeded();
        return stackOut.isEmpty() ? null : stackOut.pop();
    }

    // 查看队首元素
    public Integer peek() {
        transferIfNeeded();
        return stackOut.isEmpty() ? null : stackOut.peek();
    }

    // 若出队栈为空，从入队栈转移数据
    private void transferIfNeeded() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }
}

方案二：

思路：

用两个栈：stack1和stack2

- add：先将stack1中的所有元素弹出并压入stack2，然后将新元素压入stack1，再将stack2中的所有元素弹出并压回stack1。这样新元素就在栈底，而栈顶是队首。

- poll：直接弹出stack1的栈顶

- peek：直接查看stack1的栈顶

代码实现：

import java.util.Stack;

public class TwoStackQueue2 {
    private final Stack<Integer> mainStack;
    private final Stack<Integer> tempStack;

    public TwoStackQueue2() {
        mainStack = new Stack<>();
        tempStack = new Stack<>();
    }

    // 入队操作
    public void add(int value) {
        // 将主栈元素移到临时栈（反转顺序）
        while (!mainStack.isEmpty()) {
            tempStack.push(mainStack.pop());
        }
        // 新元素压入主栈底部
        mainStack.push(value);
        // 将临时栈元素移回主栈（恢复队列顺序）
        while (!tempStack.isEmpty()) {
            mainStack.push(tempStack.pop());
        }
    }

    // 出队操作
    public Integer poll() {
        return mainStack.isEmpty() ? null : mainStack.pop();
    }

    // 查看队首元素
    public Integer peek() {
        return mainStack.isEmpty() ? null : mainStack.peek();
    }
}

小结：

方案一：两个栈分工（入队栈和出队栈）

优点：入队操作O(1)，出队操作均摊O(1)（虽然有时候需要转移，但每个元素最多被转移一次，所以均摊下来是O(1)）。

缺点：出队操作在某些情况下需要转移整个栈，可能会造成延迟。

方案二：入队时调整顺序

优点：出队和查看队首都是O(1)，操作直接。

缺点：入队操作需要两次栈转移，时间复杂度O(n)，其中n为队列元素个数。

方案一在大多数情况下更优，特别是对于频繁入队的情况。