一个接口、两种内部顺序
先进先出队列返回仍在队列中最早加入的项目;栈却移除最近压入的项目。两个栈可把顺序反转两次,但必须在正确时机转移。队列的逻辑顺序应独立于实现栈的数组或链式结构来描述。
假设两个栈起初为空,每次栈 push 或 pop 花一个基本操作,其他比较、判空及返回项目均为常数时间。空队列出队报告下溢;以下成本界只计成功入队与出队。
操作及不变量
定义 2.1.1
(双栈队列)
称输入栈为 、输出栈为 。入队把新项目 push 到 。出队时若 为空,便反复从 pop 并 push 到 ,直至 清空;然后 pop 并返回 的栈顶项。若二者均空则报告下溢。
定理 2.1.2
(队列的逻辑顺序)
每次操作边界,队列从最旧到最新的逻辑顺序,是 从顶到底的序列,接上 从底到顶的序列。
证明
(对操作归纳)
起初两段都空。入队把新项目放在 顶部,也就是其从底到顶序列的末尾,因此追加到逻辑队列。若 非空,其栈顶项就是最早项目,pop 恰好移除它。若 空而 非空,搬动全部项目会反转栈顺序:原本 底部成为 顶部,故原输入的从底到顶序列成为输出的从顶到底序列。再 pop 即返回最旧项目。对操作归纳便证明不变量及先进先出性。
证明透视
为什么要等输出栈清空才转移
已在 的项目都早于目前 的项目。若把较新的输入项目移到非空 ,它们会置于旧输出项目之上,改变下一次答案。例如 有 、 有 ,过早转移会让 在顶部,尽管队列顺序是 。输出为空的条件保留两组新旧项目之间的界线。
常见错误
(转移时只搬一项)
设 (从底到顶)、,所以队列顺序是 。若转移只搬 的顶项,则 ,出队就会返回 ,而最旧的项目其实是 。转移必须搬走整个 ,把它的顺序反转,使原来的底部 落在 的顶部。
一次跟踪
例题 2.1.3
(交错的入队与出队)
栈均从底到顶书写。依次入队 ,得到 。出队时先转移成 ,再返回 ,余下 。入队 得 。其后两次出队不需转移,依次返回 。最后 空,把 转移并返回。返回序列是 。
反例模式
摊还不代表每次操作都便宜
若 中有 项而 为空,一次出队需从 pop 次、向 push 次,再从 pop 一次,共 次栈操作。即使整段操作序列的每次成功操作有常数摊还成本,这一次操作的最坏成本仍非常数。
例题 2.1.4
(下溢与单个项目)
两个栈起初都空。出队发现 与 均空,不作任何栈操作就报告下溢。入队 :。此时出队要转移一项,即从 pop 一次、向 push 一次,再从 pop 出 :成本 ,两个栈恢复为空。再出队就报告下溢。成本界只计成功的出队。
例题 2.1.5
(达到上界的序列)
入队 :四次 push,,势能 。第一次出队转移四项,再 pop 出 : 次操作,剩下 。其后三次出队各花一次操作,依次返回 。总成本是 ,而 。等号成立,因为每个项目都被转移一次,也都被出队一次。
计算转移成本
定理 2.1.6
(操作序列的总成本)
从两个空栈开始,含 次入队及 次成功出队的序列至多使用 次栈操作。因此每次成功操作的摊还成本是 ,尽管当 中有 项等待时,单次出队可花 。
证明
(每个项目至多移动三次)
一段序列有 次入队和 次成功出队时,每件项目只被 push 到 一次,最多被转移一次。总栈操作最多 :每次入队一次 push,每件入队项目最多一次输入 pop 和输出 push,每次成功出队一次输出 pop。有些入队项目可能仍留在某个栈,所以这是上界,不是每次都完成转移的断言。
也可使用势能 ,起初为零且永不为负。入队实际成本一、势能增加二,摊还成本为三;不转移的出队成本一且势能不变;转移 项的出队实际成本 、势能减少 ,摊还成本一。把实际成本加势能变化逐项相加后望远镜式消去;由末势能非负,实际栈成本不超过 。起初为空的假设很重要:预先放入 的项目会带来正的初始势能。
常见错误
(选了太小的势能)
若以 代替 ,入队的摊还成本是 ,但转移 项的出队摊还成本是 ,并非常数,论证就什么也没有证明。因子二支付了项目之后的两次移动,即从 pop 及 push 到 ;取 时,转移的摊还成本是 。
练习与解答
快速检查
(若 、 均从底到顶列出,写出逻辑队列。)
解答 · 答案
:先从顶到底读 ,再从底到顶读 。
快速检查
(从空开始,入队 ,出队一次,入队 ,再出队两次。返回什么?)
解答 · 答案
依次返回 。返回 后 仍在 的顶部,必须早于新加入的 。
快速检查
(若一次出队转移三项,实际栈操作成本及势能变化各是多少?)
解答 · 答案
成本 ; 减少三,故 ,摊还成本为一。
快速检查
(若 非空,为什么每次入队时都转移 是错误的?)
解答 · 答案
它可能把新项目放到较旧输出项目之上。证明中 的 与 的 例子显示了顺序违背。