Day35-【13003】短文，什么是双端队列？栈和队列的互相模拟，以及解决队列模拟栈时出栈时间开销大的方法

第三节进一步讨论栈和队列

双端队列

假设你芷在邮局排队等待办理某项业务。

当你排到最前面时，邮局柜员要求你填一 张表。

你靠边去填表，而让邮局柜员为下— 位排队的顾客服务。

在填完表后，邮局柜员要服务的下— 个对象就是你。

这意味着，你排到了队头，而不需要从队尾再排一 次队。

类似地，假如你去银行排队，发现队伍很长，所以决定离开，这相当于你从队尾走掉了。

可以用队列模拟排队情形。

邮局排队的清形表明，可以在队头出队，也可以在队头入队。

银行排队的清形表明，可以在队尾入队，也可以在队尾出队。

在队头、队尾两端均能够进行入队、出队操作的队列称为双端队列，如图3-21所示。

因为双端队列的两端都可以进行入队和出队操作，所以两端不再分队头及队尾。

当将队列画成水平方式时，可以将两端称为左端及右端。

当将队列画成垂直方式时，可以将两端分别称为上端及下端。

当然，也可以标记为端1和端2,或你喜欢的名字。

当将一 端的入队操作及另一 端的出队操作看作一 对操作时，双端队列与普通队列是一 样的。

当将同一 端的入队橾作及出队橾作看作一 对橾作时，双端队列与普通的栈是一 样的。

所以双端队列既有与队列一 样的橾作，又有与栈一 样的操作。

从队列的角度来看，这是双端队列，

从栈的角度来看，这是对底栈，只是栈的底是通的，即从— 个栈进入的元素，可以从另— 个栈中出栈。

对双端队列两端的操作加以限制，如其中一 端仅允许入队，另一 端既允许入队，又允许出队，得到的是输入受限的双端队列。

类似地， 一 端仅允许出队，另一 端既允许入队，又允许出队，得到的是输出受限的双端队列。

栈和队列的相互模拟

栈与队列可以相互模拟。

具体来说，使用两个栈能模拟出队列的行为，

或使用两个队列能模拟出栈的行为。

使用栈来模拟队列

类型定义

入队

出队

判空，判满

使用队列来模拟栈

类型定义

初始化

清空操作

判空，判满

栈长度输出

入栈

出栈

避免出栈时间开销大的方法