后进先出与先进先出

第 9 课把「一段区间」交给一对下标去框，窗口这个说法随之出现：窗口往右滑一格，就要知道窗口里的最大值、窗口里还剩哪些元素。那一课换的是走法——同一批数据，扫过它的顺序变一下，两层循环就降成了一层。

这一课换的是另一件事：数据按什么顺序交出去。第 3 课量过容器上每个操作的价格，选容器的第一条标准是操作贵不贵；在两个价格相当的容器之间还要再选一层，选定进出的顺序。顺序定对了，一批看着绕的题有稳定的解法；顺序定错了，代码写得再紧凑也拿不到正确答案。

两种顺序，两类题目

栈（stack）与队列（queue）这两个名字都来自日常的排布：一叠东西要取只能从最上面拿，一队人要走只能从队头走。把这两种排布抽象成数据结构，就得到这门课最基础的两条线性结构。

栈是只允许在同一端插入和删除的线性结构。插入与删除都发生在那一端，因此最后插入的元素最先被取出，这种顺序称为后进先出（last in, first out）。允许插入和删除的那一端通常画在上方，称为栈顶；另一端称为栈底。

队列是只允许一端插入、另一端删除的线性结构。插入在一端、删除在另一端，因此最先插入的元素最先被取出，这种顺序称为先进先出（first in, first out）。插入的那一端称为队尾，删除的那一端称为队头。

两个定义只说了允许做哪些操作，选题时真正要看的是它们分别适合什么样的处理顺序。下面这张表把题面里常见的说法与结构对应起来，看到左边的特征就往右边找：

表的后两行是前两行的加强版，第六节与第七节各讲一个；前两行是基础用法，接下来两节各实现一遍。

用列表实现栈

Python 官方教程在「数据结构」一章里给出了这两条结构的实现建议。栈那一段的说法是：列表方法使得将列表作为栈来使用非常容易，最后添加的元素会最先被取出（"后进先出"）；要将一个条目添加到栈顶，可使用 append()；要从栈顶取出一个条目，则使用 pop() 而不必显式指定索引。教程随后的例子：

stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack.pop())
print(stack)

[3, 4, 5, 6, 7]
7
[3, 4, 5, 6]
6
5
[3, 4]

两个操作都作用在列表末尾，代价可以照第 3 课的价格表读出来。列表的元素连续存放，末尾是唯一一个不牵动其他元素的位置：加一项写在空位后面，删一项把长度减一，都不需要搬动已有元素，所以 append 与不带参数的 pop 都是 O(1)。其中 append 要按第 2 课讲的那层意思读作均摊 O(1)：多数时候只是往末尾空位写一下，偶尔遇上扩容才搬一次整块，这一次大开销摊到很多次追加上，每次仍是常数。

看一眼栈顶但不取出来的写法是 st[-1]：按下标取元素同样是 O(1)。判空写 not st，它与 len(st) == 0 等价，只是更短。

队列就用 deque

紧接着栈的那一段，官方教程写的是队列：列表也可当作队列来使用，首先添加的元素将被首先提取（"先进先出"）；不过，列表这样使用是低效的。理由也写在同处：虽然在列表末尾添加和弹出条目很快速，但在列表开头插入或弹出条目却很慢，因为所有其他元素都必须移动一位。这一段最后给出建议：实现队列最好用 collections.deque，可以快速从两端添加或删除元素。

官方的队列例子：

from collections import deque

queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           # Terry 到了
queue.append("Graham")          # Graham 到了
print(queue.popleft())          # 第一个到的现在走了
print(queue.popleft())          # 第二个到的现在走了
print(queue)                    # 按到达顺序排列的剩余队列

Eric
John
deque(['Michael', 'Terry', 'Graham'])

deque 这个名字是 double-ended queue（双端队列）的简写，官方给的读法是 deck。collections 文档对它的性能口径是：deque 是对栈或队列的泛化，支持从任一端添加和弹出条目，在两个方向上的大致性能均为 O(1)。与之对照的两句是：list 对象虽然也支持类似操作，但它是针对快速的固定长度操作优化的，pop(0) 和 insert(0, v) 操作对下层数据表示的大小和位置改变都将产生 O(n) 的内存移动开销；索引访问在 deque 两端的时间复杂度均为 O(1)，在中间则会低至 O(n)，需要快速随机访问时仍要用列表。

第 3 课已经在本机量过这条差距：同样出队 20 万次，list.pop(0) 约 2.74 秒，deque.popleft() 约 0.013 秒，相差约 200 倍。差距的来源是移动开销的累加——pop(0) 每次 O(n)，出 n 次就退化成 O(n^2)；popleft() 每次 O(1)，出 n 次仍是 O(n)。队列的容器就定在 deque 上：一头进、另一头出，从此不必再考虑用列表当队列的写法。

deque 还有一个创建时就限定长度的用法：deque(iterable, maxlen)。官方口径是，限长的 deque 一旦满了，新项加入时同样数量的项就从另一端弹出，这种结构提供类似 Unix tail 的功能，也可以用来追踪最近的活动。

from collections import deque

recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.append(x)
    print(recent)
print('maxlen =', recent.maxlen, '内容', list(recent))

deque([1], maxlen=3)
deque([1, 2], maxlen=3)
deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)
deque([3, 4, 5], maxlen=3)
maxlen = 3 内容 [3, 4, 5]

括号匹配

题目：给一段只由 (、)、[、]、{、} 组成的文本，判断里面的括号是否配对正确。空文本算正确。

读到任意一个右括号时，能跟它配对的只有最近一个还没有配对的左括号：夹在中间的那些左括号，必须由更靠后的右括号先了结。文本从左往右读，处理顺序正好是「最近进来的先处理」，这就是栈的后进先出。做法随之确定：遇到左括号入栈，遇到右括号就看栈顶是不是同一种左括号。

def is_valid(s):
    """配对表：右括号 -> 它对应的左括号。"""
    pair = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in '([{':
            st.append(ch)
        elif ch in ')]}':
            if not st or st[-1] != pair[ch]:
                return False
            st.pop()
    return not st


for s in ['()[]{}', '([)]', '(]', '((', '()', '']:
    print(f'"{s}"', is_valid(s))

"()[]{}" True
"([)]" False
"(]" False
"((" False
"()" True
"" True

([)] 这一组值得逐步走一遍：四种括号的个数看起来是配平的，配对却在第三步就被否掉。

三处边界写在代码里：

• 遇到右括号时栈可能是空的（文本以 ) 开头），所以先查 not st。少了这一条，st[-1] 会在空列表上取元素并报错。
• 文本读完后栈里还可能有东西（((），说明有左括号没被了结，所以最后 return not st。
• 空文本的 not st 为真，算正确。

表达式求值

括号匹配是把「最近一个没配对的左括号」存起来，表达式求值是同一件事的另一种用法：把还没参与运算的数存起来。先看一种把运算符写在两个操作数之后的写法，它叫后缀表达式，也叫逆波兰式。3 4 + 2 *（本文的代码里写成 34+2*）的意思是把 3 与 4 相加、再乘 2；它的好处是读的顺序就是计算的顺序，不需要括号，也不需要比较运算符的优先级。

读到数字时先存起来，读到运算符时取最近存进去的两个数算一次，再把结果存回去——又是「最近进来的先处理」，用的还是栈。

def eval_rpn(s):
    """s 是后缀表达式；为看清栈的动作，这里每个操作数都是一位数字。"""
    st = []
    for ch in s:
        if ch in '0123456789':
            st.append(int(ch))
        else:
            b = st.pop()          # 先弹出的是右操作数
            a = st.pop()
            if ch == '+':
                st.append(a + b)
            elif ch == '-':
                st.append(a - b)
            elif ch == '*':
                st.append(a * b)
            else:
                st.append(a // b)
    return st[-1]


for s in ['34+2*', '12+', '93/', '56+7*', '52-3+']:
    print(s, eval_rpn(s))

34+2* 14
12+ 3
93/ 3
56+7* 77
52-3+ 6

四处细节：

• 弹出顺序不能写反。栈顶是后读到的那个数，也就是右操作数，所以第一句 b = st.pop()、第二句 a = st.pop()；减法与除法要按 a - b、a // b 算。这两处中任一处写反，52- 的输出都会从 3 变成 -3，93/ 会从 3 变成 0。
• 除法用 //。用 / 会得到浮点数，后面的整数比较与输出都会跟着变。
• 除数为 0 会抛 ZeroDivisionError，题面一般会保证不会出现，写之前先确认这一条。
• 循环结束时栈里正好剩一个数，它就是答案。多位数字的读法要先按空格切开，那是输入解析的内容，这一课的例子把每个操作数限制成一位数字，好让注意力留在栈上。

中缀表达式（(1+2)*3 这种日常写法）的求值是历年真题常客，做法要用两个栈：一个存操作数，一个存运算符，遇到运算符时与运算符栈的栈顶比优先级，决定先算还是先入栈；遇到左括号把它压进运算符栈，遇到右括号就把运算符栈弹到左括号为止。这是这一课 lab 里的题，先把后缀版写顺，两个栈的版本就只是多了一张优先级表。

单调栈：该弹就弹

题目：给一个由 n 个整数组成的数组 a，对每个位置 i 求出它右边第一个比 a[i] 大的数；右边如果没有更大的数，答案记 -1。

最直接的写法是对每个 i 向右扫，扫到第一个更大的数就停。它的最坏情形是数组递减，此时每个 i 都要扫到末尾，总操作数是 \frac{n(n-1)}{2}，即 O(n^2)。

换一种走法。从左往右读数组，对每个位置只问一件事：它能不能给前面某些还没有答案的位置充当答案。a[i] 能当答案的那些位置，就在它左边、值比它小、并且还没了结——它们恰好是栈里值比 a[i] 小的那些下标。把还没有答案的下标按读入顺序放进栈，规则是：

• 读到 a[i] 时，只要栈不空且栈顶下标对应的值小于 a[i]，就弹出栈顶，并把那个位置的答案记为 a[i]；
• 一直弹到栈顶的值不小于 a[i]，或者栈空为止；
• 把 i 入栈。

照这条规则走，栈里下标对应的值自栈底向栈顶递减：值大的留在下面、还在等更大的数，值小的浮在上面、等着被新元素了结。答案在弹出的那一刻确定——元素被弹出，说明它右边第一个比它大的数出现了。

def next_greater(a):
    """对每个位置求右边第一个比它大的数，没有则记 -1。"""
    n = len(a)
    res = [-1 for _ in range(n)]      # 先摆一排 -1 占位
    st = []                           # 存还没有答案的下标，值自底向顶递减
    for i in range(n):
        while st and a[st[-1]] < a[i]:
            res[st.pop()] = a[i]      # 弹出的这一刻，答案就是 a[i]
        st.append(i)
    return res


a = [2, 1, 3, 1, 4]
print(a)
print(next_greater(a))

[2, 1, 3, 1, 4]
[3, 3, 4, 4, -1]

对着输出读一遍过程：下标 1 的 1 与下标 0 的 2 都在读到 3 时被弹出，答案都是 3；下标 3 的 1 与下标 2 的 3 都在读到 4 时被弹出，答案都是 4；下标 4 的 4 右边没有更大的数，它一直留在栈里，答案保持 -1。

代价可以数出来。每个下标入栈一次、出栈至多一次，所以整个循环只做 2n 次入栈与出栈动作，加上每轮一次比较，总代价是 O(n)，与数组长什么样无关。本机数了一遍：随机数组 n = 200000 时进栈 200000 次、出栈 199986 次；递减数组 n = 200000 时进栈 200000 次、出栈 0 次，最后栈里留着全部 200000 个下标——它们右边都没有更大的数，答案都是 -1，这是正确结果。

「一次都不弹」与「该弹的时候没弹」的区别正在这里。把上面代码里弹栈的 while 写成 if：

def next_greater_bad(a):
    """把弹栈的 while 写成了 if：一轮最多只弹一个。"""
    n = len(a)
    res = [-1 for _ in range(n)]
    st = []
    for i in range(n):
        if st and a[st[-1]] < a[i]:
            res[st.pop()] = a[i]
        st.append(i)
    return res


a = [2, 1, 3, 1, 4]
print(next_greater_bad(a))

[-1, 3, -1, 4, -1]

同一批数据上，下标 0 与下标 2 的答案从 3、4 变回了 -1。原因在栈顶：读到 3 时栈里自底向顶是 [2, 1]，if 只弹走了栈顶的 1，值 2 留在栈里，它既没有了结、又占着栈顶；读到下一个元素 1 时，栈顶是 2 而 2 不小于 1，这一轮什么也弹不掉。这些留下来的旧值，在后面的每一轮里既不会被弹出、也不会被当成答案——它们确实再也用不到了，代价是位置被它们占住，栈里「值自底向顶递减」这条性质随之被破坏，栈顶不再代表「最近的、还有可能被更大的数了结的那个下标」。两个版本在 200 组随机小数组上有 138 组答案不同，这类错误不会报错，只会把该有的答案抹成 -1。

两个版本在同一批数据上的耗时对照（本机实测，Python 3.14 的 free-threading 构建，各取三次运行的最小值）：

三列要分开读。第一列是暴力版的最坏情形：规模从 5000 到 10000 翻一倍，耗时从 0.234 秒涨到 0.977 秒，约 4 倍，正是 O(n^2) 的样子。第二列在同一批数据上是线性的：规模从 5000 到 10000 涨约 2 倍，n = 20000 时是 0.95 毫秒；到了毫秒以下，计时的抖动本身就有一个数量级，这一列只看量级，精确倍数不必细究。第三列解释了一个常见的错觉：随机数据上暴力版看着不慢（n = 20000 时 5 毫秒），因为平均只往右看几步就找到了更大的数。按 OI Wiki 的口径，算法竞赛里一般考虑最坏时间复杂度，判断一种写法行不行，要看它的最坏情形。

单调队列：窗口最大值

第 9 课的双指针用一个窗口框住连续一段，并让窗口只往右滑，前提是「加一个元素、减一个元素之后，关心的那个量不往回走」。窗口最大值不满足这条：最大值可能是窗口最左边那个元素，它一走，窗口里的最大值就得重新找。窗口长度固定为 k 时，最直接的写法是对每个窗口取一次 k 个数的最大值，代价 O(nk)。

题目：给定 n 个整数的数组 a 与窗口长度 k，输出每个长度 k 的窗口里的最大值，共 n-k+1 个。

把单调栈那套「没用的旧值当场丢掉」的做法搬到队列上，就得到单调队列：队列里存下标，队首是当前窗口最大值的下标，队列中下标对应的值自队首向队尾递减。窗口右端每移动到一个新位置 i：

• 弹队尾：只要队尾下标对应的值不大于 a[i]，就把它弹出；
• 把 i 入队；
• 弹队首：若队首下标已经滑出窗口（下标不大于 i - k），把它弹出；
• 此时队首就是当前窗口最大值的下标。

两条弹出都必须做，理由各不相同。队尾那条说的是「被丢弃的元素再也不会成为答案」：从队尾弹出的元素只有两种结局——它可能已经滑出窗口，那当然不可能再当答案；它也可能还在窗口里，那么此后每一个包含它的窗口（窗口右端不小于 i）都一定也包含 a[i]（窗口是连续的一段，右端往后走只会更晚离开），而 a[i] 不小于它，所以它同样当不上那个窗口的最大值。两种结局都说明，被丢掉的元素在剩下的过程里一次也不会被用到。队首那条说的是「答案必须来自窗口里面」：留着已经滑出窗口的旧值，输出就会拿它当答案。

from collections import deque


def max_window(a, k):
    """输出每个长度 k 的窗口里的最大值。"""
    q = deque()                    # 存下标，a[q[0]] 是当前窗口最大值
    res = []
    for i in range(len(a)):
        while q and a[q[-1]] <= a[i]:
            q.pop()                # 队尾更小的元素再也用不到
        q.append(i)
        if q[0] <= i - k:
            q.popleft()            # 队首已经滑出窗口
        if i >= k - 1:             # 第一个窗口已经凑满
            res.append(a[q[0]])
    return res


b = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_window(b, 3))

[3, 3, 5, 5, 6, 7]

六个输出对应六个窗口，逐个手工核对：[1, 3, -1] 的最大值是 3，[3, -1, -3] 是 3，[-1, -3, 5] 是 5，[-3, 5, 3] 是 5，[5, 3, 6] 是 6，[3, 6, 7] 是 7。代码里的 i >= k - 1 管的是开头：前 k-1 个位置上的窗口还没凑满 k 个数，不输出。

队首那条弹出的后果，要找最大值离开窗口、又没有更大的数进来的数据才看得见。取 a = [7, 1, 1, 1, 1]、k = 3：

第二行把早已滑出窗口的 7 一直当成答案，从第二个窗口起全错。这正是「该弹的时候没弹」在队列上的表现：留在队首的旧值已经不在窗口里，却还占着答案的位置。

代价：每个下标最多入队一次、出队一次，两条弹出加起来也不超过 2n 次，所以整个循环是 O(n)，与 k 无关；暴力版是 O(nk)。在 n = 200000 的随机数组上把 k 换几个值（本机实测，各取三次运行的最小值）：

单调队列那一列几乎不动（都在 0.038 秒上下），暴力那一列与 k 成正比，k 涨到 20000 时已经跑到 31.8 秒。窗口长度只决定暴力的代价，与单调队列无关，这也是它能一处不错的写法用到底的原因。表里的秒数是本机实测、非通用值，换个机器或 Python 版本绝对值都会变；要记的是那一列不随 k 增长。

用两个栈模拟队列

队列要一端进、另一端出，栈只能在同一端进出，反过来问一句：栈能不能表达出队列的顺序？用两个栈可以。一个只管进，一个只管出：入队时把元素压进「进栈」；出队时，若「出栈」是空的，就把「进栈」里的元素全部弹出、依次压进「出栈」——这一倒手把顺序翻了一次，「进栈」里最早进来的元素落到「出栈」的栈顶，正是队头。

def push(inbox, outbox, x):
    inbox.append(x)


def pop_front(inbox, outbox):
    if not outbox:
        while inbox:
            outbox.append(inbox.pop())
    return outbox.pop()


def front(inbox, outbox):
    if not outbox:
        while inbox:
            outbox.append(inbox.pop())
    return outbox[-1]


inbox = []
outbox = []
for x in [1, 2, 3]:
    push(inbox, outbox, x)
print(pop_front(inbox, outbox))       # 1
push(inbox, outbox, 4)
print(front(inbox, outbox))           # 2
print(pop_front(inbox, outbox))       # 2
print(pop_front(inbox, outbox))       # 3
print(pop_front(inbox, outbox))       # 4
print('剩下的：', inbox, list(outbox))

1
2
2
3
4
剩下的： [] []

这段代码按第 4 课的规矩把结构操作收成函数：inbox 与 outbox 都是列表，传进函数后被原地修改，调用方不必接收返回值。把代码里的调用按顺序读一遍：入队 1、2、3；出队得 1；入队 4；看队头得 2；继续出队得 2、3、4；两个栈都空。

倒手的代价按均摊算：每个元素最多被搬一次（从「进栈」倒进「出栈」），所以每次出队的均摊代价是 O(1)。本机数过一遍：出队 100000 次，总共搬迁 100000 次、耗时 0.0131 秒，与 deque.popleft() 的耗时同量级。搬迁次数与出队次数相同（都是 100000 次），原因是「出栈」为空时才倒手，一批元素搬一次就能维持很久的供给。与 list.pop(0) 当队列的模型对照 300 组随机操作序列，答案不一致的次数是 0。

多组数据之间要清空

蓝桥杯的题常有多组测试数据，读一组、算一组、输出一组。这时容器建在循环外面就会带上上一组的数据：

st = []
for a in [[2, 5, 1], [3, 4]]:
    for x in a:
        st.append(x)
    print(sum(st))

8
15

第二组打印 15，而它的三个数之和是 7——多出来的 8 是第一组留在 st 里的三个数。把容器建在循环里面，每轮重新开一个：

for a in [[2, 5, 1], [3, 4]]:
    st = []
    for x in a:
        st.append(x)
    print(sum(st))

8
7

同一件事在栈、队列、单调栈、单调队列上都会发生，而且症状比其他坑更隐蔽：单组数据的样例永远是对的，错的是第二组往后。deque 也有 clear() 方法可以把元素全部移除（官方口径是「移除所有元素，使其长度为 0」），但更稳的做法是让每组数据在各自的函数里处理，容器作为局部名字在函数开头创建——第 4 课讲过，函数里的局部名字在函数返回后就不再存在，下一组数据不可能碰到上一组的残留。

这一课用到的写法

把本课的操作与边界收在一张表里，以后写这类题随手查。

这一类题的题面话术通常落在「配对」「嵌套」「撤销」「按到达顺序」「第几个窗口」这几处。看到它们，第一步是判断要处理的是最近一个还是最早一个对象，第二步才选容器：栈用列表、队列用 deque，需要丢掉没用的旧值时再给结构加上弹栈或弹队的规则。

配套项目「AI 刷题助手」在这里要能给出第三层建议：不只推荐算法名与复杂度，还要指出这题需要哪一种处理顺序、用哪种结构实现，以及那个结构里的元素在什么条件下该被丢掉。

• Python 官方文档 · collections.deque本课 deque 的口径出自这里：两端大致 O(1)、popleft、maxlen、clear，以及与 list.pop(0) 的 O(n) 移动开销对照
• Python 官方教程 · 数据结构这一章里讲两条结构的 5.1.1 与 5.1.2 两节，本课的官方例子与「列表当队列低效」的说法出自这里
• OI Wiki · 复杂度基本操作数、最坏时间复杂度与均摊复杂度的口径，本课读耗时表的方式照它
• 《算法导论（第 3 版）》第 10 章 基本数据结构本地教材：栈与队列的抽象定义与两种实现，可作参考书查