数据结构与算法 / 系统课时

用两个结构实现顺序转换

用两个结构实现顺序转换

栈和队列的核心区别只是元素离开的顺序:栈是后进先出,队列是先进先出。借助两个同类结构进行暂存和搬运,就能改变元素暴露顺序。本节以双栈实现队列为主,重点理解何时搬运以及为什么看似昂贵的操作仍能得到较好的均摊复杂度。

学习目标

  • 能用两个栈实现队列的入队、出队和查看队首操作
  • 能解释延迟搬运策略以及单次最坏复杂度与均摊复杂度的区别
  • 能把同样的顺序转换思路迁移到双队列实现栈的问题

抽象顺序与底层顺序

栈只能从同一端压入和弹出,因此天然产生“后进先出”;队列要求最早进入的元素最先离开。要用栈模拟队列,关键不是让单个栈违反规则,而是让元素经过两次反转。

元素先依次进入 in 栈。当需要读取队首且 out 为空时,把 in 的元素逐个弹出并压入 out。原本最早进入 in 的元素经过这次搬运后恰好位于 out 顶部,于是可以按队列顺序弹出。

双栈实现队列的数据搬运流程

双栈实现队列

下面的实现把所有新元素压入 in,而 pop 和 peek 只从 out 读取。moveIfNeeded 是整个结构的关键:只要 out 还有旧元素,就绝不能把 in 中更新的元素混进去,否则会破坏先进先出的顺序。

java
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static class MyQueue {
        private final Deque<Integer> in = new ArrayDeque<>();
        private final Deque<Integer> out = new ArrayDeque<>();

        public void push(int x) {
            in.push(x);
        }

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

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

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

        private void moveIfNeeded() {
            // out 为空时才搬运,避免反复倒腾同一批元素。
            if (out.isEmpty()) {
                while (!in.isEmpty()) {
                    out.push(in.pop());
                }
            }
        }
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(10);
        queue.push(20);
        queue.push(30);

        System.out.println(queue.peek());
        System.out.println(queue.pop());
        queue.push(40);

        while (!queue.empty()) {
            System.out.print(queue.pop());
            if (!queue.empty()) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}

预期输出:

text
10
10
20 30 40

peek 与第一次 pop 触发搬运后,out 中已经保存了正确的队首顺序。之后即使又向 in 压入 40,也必须先消费完 out 中的 20、30,之后才能再次搬运,因此新元素不会插队。

为什么均摊仍是 O(1)

一次 pop 最坏可能把 nn 个元素从 in 搬到 out,所以单次最坏复杂度是 O(n)O(n)。但从一串操作整体观察,每个元素只会被压入 in 一次、从 in 弹出一次、压入 out 一次,再从 out 弹出一次。

因此执行 nn 次队列操作时,搬运总量仍与元素数量成线性关系,平均到每次操作上的均摊时间为 O(1)O(1)。空间复杂度是 O(n)O(n),因为两个栈合计最多保存当前队列中的全部元素。

双队列实现栈时怎么想

反方向的问题是用先进先出的队列模拟后进先出的栈。常见做法是保留两个队列:需要 pop 时,把主队列前面的 n−1n-1 个元素移动到辅助队列,最后留下的元素就是栈顶;删除它以后,再交换两个队列的职责。

这种策略让 push 为 O(1)O(1)、pop 为 O(n)O(n)。也可以在每次 push 后通过队列轮转,让新元素立即来到队首,从而把代价转移成 push 为 O(n)O(n)、pop 为 O(1)O(1)。选择哪一种,取决于题目中哪类操作更频繁。

什么时候选择哪种搬运策略

看到“用一种受限结构实现另一种结构”时,先写清目标结构要求暴露哪个元素,再判断现有操作能否直接得到它。如果不能,就利用第二个结构暂存元素,通过一次或延迟搬运改变顺序。

双栈队列最值得记住的不是固定代码,而是“旧数据未消费完就不重新搬运”这一不变量。只要能明确每个元素在两个结构之间最多移动多少次,就能同时证明顺序正确性和复杂度边界。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用两个结构实现顺序转换

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通