本节扩展已有的双栈队列课,该课已证明先进先出与基本摊还界。本节增加内部转移不变量、队首观察操作、实现细节与底层成本条件。
栈移除的是最新加入的元素,队列却必须移除等待时间最长的元素。将一个栈中的元素全部转移到另一个栈会颠倒顺序,因此两个栈可以实现队列。难点不在于颠倒本身,而在于确定什么时候颠倒才能保持已有元素与新到元素之间的先后次序。
这个实现还提供了一个小而完整的摊还分析例子。一次队列操作可能转移许多元素,但一长串操作所需的栈操作总量仍与操作次数成线性关系。我们将证明这两个结论,并解释一个看似意外的事实:查看队首可以改变内部表示,却不改变抽象队列。
为两个栈规定精确的序列含义
定义 2.3.1
(输入栈、输出栈与抽象的先进先出序列)
设 为输入栈, 为输出栈。将每个栈都写成从栈底到栈顶的序列,栈顶在右侧。队列按从最早到最新的顺序表示为
其中 表示序列拼接。两个栈初始时均为空。每次入队的元素实例恰好出现在其中一个栈中,两个栈的长度之和就是队列长度。
enqueue(x) 将 添加到队尾。队列非空时,front() 返回最早的元素而不将其移除;dequeue() 返回并移除该元素。队列为空时,这两个操作都会报告错误。
这里约定的顺序很重要。若 且 ,队列是 ,而不是 。输出栈的栈顶是等待时间最长的元素;输入栈的栈底则是尚未转移的到达元素中最早的一个。
概念视角结构
一条序列和一个可移动的切点
把队列写成 ,并令 。此时 存放 , 在栈顶; 存放 , 在栈顶。入队在右端加长序列,切点不动;出队删去 并使 减一;转移则把切点移到右端,即 。后文使用的势能就是 。
常见错误
(从错误的一端读取输出栈)
若 、,把队列写成 ,就是把输出栈的栈底当成最早的元素,出队便会错误地返回 7。最早的是输出栈的栈顶:队列是 ,出队返回 4。
仅在输出栈为空时转移
入队总是将元素压入 。读取或移除队首之前,按以下规则处理:如果 为空,就反复从 弹出元素并将其压入 ,直到 为空。如果 已经非空,则不要转移任何元素。
定理 2.3.2
(两个栈实现先进先出队列)
从两个空栈开始,入队时压入 ,只有在 front 或 dequeue 之前 为空时才转移。每次公开操作之后, 就是抽象队列的序列:入队添加到队尾,front 返回最早的元素,dequeue 移除并返回它。
证明
(每个公开操作都保持先进先出的序列含义)
入队使 变为 ,所以表示的队列变为 ,恰好是在队尾添加元素。
若 非空,它的栈顶是 的第一个元素,因而也是 的第一个元素。读取该栈顶就返回队首;弹出它则恰好移除队列的第一个元素。
若 为空,设原来的输入栈序列为 。将其全部转移后, 且 。新的抽象序列为 ,与原队列相同。之后便可根据上一段的论证读取或移除输出栈栈顶。因此,入队、读取队首和出队都实现了各自规定的序列行为。
反例模式
将新到元素倒入非空输出栈会破坏先进先出
设初始时 、,表示队列 。如果将 9 转移到非空的输出栈上,就得到 和 ,此时表示的队列变成 。
最新的元素跑到了等待更久的元素前面。“输出栈为空”是保证正确性的条件,不只是性能优化。
转移过程有自己的循环不变量
在颠倒只完成一部分时,公开操作所用的简单抽象公式未必仍表示原队列。我们需要单独的循环不变量,不能过早读取结果。
引理 2.3.3
(转移循环不变量)
设 为转移前的输入序列, 为空。转移循环每一轮都有 ;循环在 轮后结束,此时 、。
证明
(原输入序列分成未转移部分与已转移部分)
设转移前的输入栈序列为 ,输出栈初始为空。在循环中,将 分为 ,其中 且 。等价地,
初始时 且 。从 末尾弹出一个元素并压入 ,相当于把该元素加到已转移后缀 的开头,因此仍保持上述分解。每次循环使 减少一,所以循环必定终止。
终止时 ,故 ,公开的队列解释得以恢复。代码会在返回队首值或完成出队之前完成这次内部转移。
反例模式
第一个被移动的是最新元素,而非队首
若 且 ,只移动一个元素后得到 、。此时读取输出栈栈顶会返回 9,但队首实际上是 4。
循环不变量仍以 记录原序列。它不能说明公开公式 在转移结束前仍表示原队列。不能把内部中间状态误认为操作完成后的状态。
追踪旧元素仍在等待时的新到元素
例题 2.3.4
(两次转移服务多次读取队首和出队)
表中每个栈均从栈底写到栈顶。返回值一栏中的破折号表示入队操作不返回队列元素。
| 操作 | 操作后的输入栈 I | 操作后的输出栈 O | 返回值 | 操作后的抽象队列 |
|---|---|---|---|---|
| 入队 4 | — | |||
| 入队 7 | — | |||
| 读取队首 | ||||
| 入队 9 | — | |||
| 出队 | ||||
| 入队 2 | — | |||
| 出队 | ||||
| 读取队首 | ||||
| 出队 |
第一次 front 将两个元素逆序转移;第二次则逆序转移之后到达的两个元素。两次读取队首都没有改变抽象队列序列。新到的 9 和 2 留在输入栈中,直到输出栈中较早的一批元素被取完。
例题 2.3.5
(一次昂贵的队首调用,精确计费)
把 入队到空队列,于是 、、。调用 front 从 弹出 、、 并压入 ,得到 、,再读取栈顶,即 。计入的工作是 次弹出、 次压入和 次读取,共 ,其中 。势由 降到 ,所以摊还费用是 。之后紧接着的第二次 front 只需 ,不改变势。
例题 2.3.6
(空队列与值 None)
在新建的队列上,front() 调用 _prepare_front,但输入列表为空,所以什么也不做。输出列表也是空的,于是抛出 IndexError,没有任何栈被改变,工作量为常数。enqueue(None) 之后,front() 转移唯一的元素,使 _outgoing == [None]。对这个非空列表,not self._outgoing 为假,所以调用返回 None,队列长度仍是 。区分空队列与存放了 None 的,是异常,而不是返回值。
因此,读取队首是对抽象队列的观察,却不一定保持其内部表示不变。一旦输出栈中已有一批元素,重复调用 front 就只需查看同一个栈顶。使用队列操作的客户端看到的值和长度,与元素目前存在哪个内部栈中无关。
按每个元素实例的单向行程计费
先规定一个精确的代价模型:每次栈的压入、弹出或读取栈顶都计一单位。一次出队使用一次返回值的弹出操作,而不是先读取栈顶再弹出。其他控制和长度检查在每次循环迭代或公开调用中只增加常数工作量,不改变渐近结论。假设存储操作成功。
每个入队的元素实例只会被压入 一次;之后它可能从 弹出一次并压入 一次,最终还可能从 弹出一次。它不会回到 。即使值相等,不同的元素实例也要分别计数。
若从空队列开始的一串操作包含 次入队、 次成功出队和 次成功读取队首,则计入的栈工作量至多为
其中第一个 支付输入栈压入,至多 支付转移, 支付输出栈弹出和读取。这是聚合分析:有些入队元素可能仍留在 或 中,因此不一定达到这个上界。
用势函数证明相同的上界
定义状态的势为 。它始终非负,并且在初始空状态下为零。将一次操作的摊还费用定义为该操作计入的实际工作量加上势的变化量。
| 成功的操作 | 实际工作量 c | 势的变化量 | 摊还费用 |
|---|---|---|---|
| 入队 | |||
| 读取队首或出队,输出栈非空 | |||
| 读取队首或出队,先转移 k 个输入元素 |
转移这一行中 。每个到达元素都存入足够的势,以支付它将来从 弹出和压入 的费用。实现本身不存储这样的余额:势只是数学上的记账工具。
定理 2.3.7
(从空状态开始的线性总工作量)
从空状态开始,任何含 次入队、 次成功出队和 次成功读取队首的合法操作序列,所计总工作量至多为 。
证明
(任意合法操作序列中的势变化可以望远镜式相消)
将状态编号为 ,令 为计入的实际工作量,。求和得到
从空状态开始时, 且 ,故实际总工作量不超过摊还费用总和 。如果分析开始时输入栈已有元素,就必须保留初始势项 ,不能悄然套用空状态起始的上界。
证明透视
为何势是输入栈大小的两倍
中的系数由转移那一行决定。转移的 个元素各弹出一次、压入一次,代价约为 ,所以必须由约 的势下降来支付。若取 ,下降只有 ,转移的摊还费用便是 ,并非常数。同一系数也使每次入队存入两单位,得出费用 。 非负及 ,才使相消后的等式变成实际工作量的上界。证明只计抽象的栈基本操作,所以对底层数组的扩容没有任何结论。
在上面的操作表中,输入栈压入四次,转移使用八次基本操作,输出栈弹出三次,读取栈顶两次,总计 17 次。上界为 ;最终输入栈为空,所以没有剩余的势。
单次操作仍可能代价高。先将 个元素入队,再调用 front:仅该次调用就执行 个计入的基本操作,即 工作量。它的摊还费用为一,是因为之前入队积累的 势在此释放。摊还常数时间是对整个操作序列的保证,并不承诺每次调用都有常数延迟,也不是对随机输入取平均。
常见错误
(把摊还常数当成每次调用都是常数)
先入队 次之后,单次 front 调用要执行 个计入的基本操作。它的摊还费用是 ,只因为之前的入队已存入 单位的势。整串 次入队加一次 front 的代价是 ,是线性的,但那一次调用并不是常数时间。需要每次调用都有上界的应用,须使用另一种设计。
查询长度和是否为空,以及在空队列上调用 front 或 dequeue 而被拒绝,都只需每次常数工作量,且不会改变势。统计公开调用的总次数时,可以将这些操作单独计入。
用两个支持末端访问的栈直接实现
下面的 Python 列表表示栈,右端是栈顶。客户端接口只包括公开的队列操作;直接修改内部列表会破坏证明所需的条件。对空队列调用 front 或 dequeue 会抛出 IndexError,且抽象队列仍为空。None 等值是普通元素,因此异常可以区分空队列与成功返回 None 的调用。
class TwoStackQueue:
def __init__(self):
self._incoming = []
self._outgoing = []
def __len__(self):
return len(self._incoming) + len(self._outgoing)
def is_empty(self):
return not self._incoming and not self._outgoing
def enqueue(self, value):
self._incoming.append(value)
def _prepare_front(self):
if not self._outgoing:
while self._incoming:
self._outgoing.append(self._incoming.pop())
def front(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("front of an empty queue")
return self._outgoing[-1]
def dequeue(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("dequeue from an empty queue")
return self._outgoing.pop()
例如,依次入队 4 和 7,调用 front(),再入队 9,最后调用三次 dequeue():读取队首返回 4,三次移除依次返回 。长度是两个栈长度之和,无须转移元素即可得到。
上面的精确势函数表统计的是抽象栈基本操作。它并未证明每一次机器层面的列表操作都有最坏情况常数时间:动态数组栈可能需要调整容量。若要得到使用该后端时的运行时间上界,还需将线性数量的基本操作调用与栈自身的扩缩容摊还分析结合起来。如果这 次基本操作调用的栈总成本为 ,则计入每次调用的常数额外开销后,队列总运行时间仍为线性。仅靠队列的势函数不能另行证明数组扩缩容的成本。
两个栈中共存有 个元素实例。底层数组的额外容量取决于栈实现的扩容与收缩策略,应与逻辑元素数量区分。链式栈的内存分配行为不同,但先进先出与单向转移的论证相同。循环数组队列或链式队列可以避免此处的整批逆序转移,但各有自己的表示方式和延迟分析。
练习与解答
快速检查
(1. 按正确方向读取两个栈)
输入栈为 ,输出栈为 ,两者均从栈底写到栈顶。抽象队列是什么?依次出队一次、读取队首一次会返回什么?之后两个栈分别是什么状态?
解答 · 解答 1
队列是 。出队返回 7,使输出栈变空。读取队首时转移输入栈中的两个元素,得到输入栈 、输出栈 ,并返回 9。读取队首后队列仍为 。
快速检查
(2. 分析不应进行的转移)
输入栈为 、输出栈为 。为什么读取队首时必须读取当前输出栈的栈顶,而不能先转移新元素?写出原抽象序列和错误转移后的序列。
解答 · 解答 2
原序列为 ,所以队首是 4。将 9 转移到输出栈上会使其变为 ,表示 ,把最新到达的元素放在了最前面。只有输出栈为空时才应转移。
快速检查
(3. 使用内部转移不变量,不要过早给出答案)
初始输入栈为 ,输出栈为空。只移动 9 之后,如何用循环不变量还原原队列?为什么此时读取输出栈栈顶不能作为完成的队首结果?
解答 · 解答 3
循环中的解释为 。输出栈栈顶是 9,但正确的队首是 4。只有完成逆序转移后,公开解释 才重新表示原队列。
快速检查
(4. 计算转移五个元素的费用)
输出栈为空,输入栈中有五个元素。一次成功的队首读取将它们全部转移。求计入的实际工作量、操作前后的势以及摊还费用。
解答 · 解答 4
从输入栈弹出五次、压入输出栈五次,再读取栈顶一次,代价为 11。势从十降到零,因此摊还费用为 。这次调用实际上仍执行了全部十一个基本操作。
快速检查
(5. 分析后缀操作时保留初始状态)
某次分析开始时,已有 k 个元素入队到输入栈,输出栈为空。分析只计算接下来的一次队首读取。为什么对这个仅含一次调用的操作后缀使用空状态起始的上界是错误的?
解答 · 解答 5
该后缀的代价为 ,而非仅为一。它从初始势 开始,因此相消求和给出实际代价等于摊还费用一再加上这笔初始势,即 。较早的入队积累了这些信用;不把那些入队计入所分析的操作序列,并不会让积累的工作消失。
快速检查
(6. 区分元素实例计数与栈扩缩容)
将同一个值入队十次,应算一次元素行程还是十次?仅凭抽象栈基本操作的上界,是否就能证明每次 Python 列表 append 的最坏情况运行时间都是常数?
解答 · 解答 6
共有十个分别入队的元素实例,每个都有自己的单向行程和两单位转移势。值相等不会使队列元素合并。基本操作计数并不能证明列表操作的最坏情况时间;动态数组后端需要单独的扩缩容分析。将其总成本上界与队列的线性基本操作数量结合,才能得到相应的摊还运行时间保证。