使用两个队列实现栈 | Baeldung中文网

1. 简介

在本教程中，我们将通过两个队列（Queue）来模拟栈（Stack）的行为，实现一个栈数据结构。这种实现方式虽然在实际中并不常见，但在学习数据结构和算法时非常有帮助。

2. 栈与队列基础

在深入实现之前，我们先来快速回顾一下栈和队列的基本特性。

2.1. 栈（Stack）

栈是一种后进先出（LIFO, Last In First Out）的数据结构，也就是说最后压入栈的元素会最先被弹出。其核心操作包括：

push：将元素压入栈顶
pop：从栈顶弹出一个元素

2.2. 队列（Queue）

队列是一种先进先出（FIFO, First In First Out）的数据结构，也就是说最先入队的元素会最先出队。其核心操作包括：

enqueue：将元素加入队尾
dequeue：从队头移除一个元素

3. 实现思路

我们使用两个队列 q1 和 q2 来模拟栈的行为。其中 q1 作为主队列，用于保存栈的当前状态；q2 作为辅助队列，在 push 操作中帮助我们调整元素顺序。

✅ 核心逻辑

`push(E element)` 操作

如果 q1 是空的，则直接将元素 E 入队 q1
否则，先将 q1 中所有元素依次出队并入队到 q2，然后将 E 入队 q1，最后再将 q2 中所有元素出队并入队回 q1

这样，新元素总是被插入到 q1 的队首位置，从而保证栈的 LIFO 特性。

`pop()` 操作

直接对 q1 执行一次 dequeue() 操作即可，因为此时 q1 的队首元素就是栈顶元素

⚠️ 时间复杂度分析

操作	时间复杂度
`push`	O(n)
`pop`	O(1)

push 操作中，我们最多需要两次元素迁移（从 q1 到 q2 再回到 q1），所以是 O(n) 时间复杂度；而 pop 操作只需一次出队，因此是 O(1)。

🧠 示例伪代码

`push` 操作伪代码

algorithm Push(q1, q2, E):
    // INPUT
    //   q1, q2 = two queues
    //   E = element to push to stack
    // OUTPUT
    //   element E is now at the head of queue q1
    if q1 is empty:
        q1.enqueue(E)
    else:
        q1Size <- q1.size()
        for i <- 1, 2, ..., q1Size:
            q2.enqueue(q1.dequeue())
        q1.enqueue(E)
        for j <- 1, 2, ..., q1Size:
            q1.enqueue(q2.dequeue())

`pop` 操作伪代码

algorithm Pop(q1):
    // INPUT
    //   q1 = main queue
    // OUTPUT
    //   the head element of the queue q1 (which is removed from q1)
    element <- q1.dequeue()
    return element

🧪 Java 示例代码

下面是一个基于 Java 的实现示例，使用 LinkedList 来模拟队列：

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingTwoQueues {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();

    // Push element onto stack
    public void push(int x) {
        if (q1.isEmpty()) {
            q1.offer(x);
        } else {
            // Move all elements from q1 to q2
            while (!q1.isEmpty()) {
                q2.offer(q1.poll());
            }

            // Add new element to q1
            q1.offer(x);

            // Move back all elements from q2 to q1
            while (!q2.isEmpty()) {
                q1.offer(q2.poll());
            }
        }
    }

    // Remove the top element from stack
    public int pop() {
        return q1.poll();
    }

    // Get the top element
    public int top() {
        return q1.peek();
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return q1.isEmpty();
    }
}

✅ 使用示例

public class Main {
    public static void main(String[] args) {
        StackUsingTwoQueues stack = new StackUsingTwoQueues();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.top()); // 3
        System.out.println(stack.pop()); // 3
        System.out.println(stack.top()); // 2
    }
}

4. 小结

通过使用两个队列，我们成功模拟了栈的行为。虽然这种方法在实际开发中并不常用，但它有助于加深我们对数据结构之间关系的理解。

总结如下：

✅ q1 是主队列，始终保持栈顶元素在队首
✅ push 操作需要借助 q2 来调整顺序，时间复杂度为 O(n)
✅ pop 和 top 操作非常高效，时间复杂度为 O(1)

如果你在学习算法或准备面试题，这种题目非常常见，建议熟练掌握其实现逻辑和时间复杂度分析。

📚 更多关于栈和队列的内容，可以参考我们关于常用数据结构详解的文章。

Persistence

REST

Security