下载掌阅APP，畅读海量书库
立即打开
【问题描述】 循环队列是一种线性数据结构，其操作表现基于FIFO（先进先出）原则，并且队尾被连接在队首之后以形成一个循环，它也被称为“环形缓冲器”。循环队列的一个优点是可以使用这个队列之前用过的空间。在一个普通队列中，一旦一个队列满了就不能插入下一个元素，即使在队列的前面仍有空间，但是在循环队列中能使用这些空间去存储新的值。该实现应该支持以下操作。
（1）MyCircularQueue（k）：构造器，设置队列的长度为 k 。
（2）Front（）：从队首获取元素，如果队列为空，返回-1。
（3）Rear（）：获取队尾元素，如果队列为空，返回-1。
（4）enQueue（value）：向循环队列插入一个元素，如果成功插入，则返回true。
（5）deQueue（）：从循环队列中删除一个元素，如果成功删除，则返回true。
（6）isEmpty（）：检查循环队列是否为空。
（7）isFull（）：检查循环队列是否已满。
示例：
【限制】 所有的值都在0～1000范围内，操作数将在1～1000范围内，请不要使用内置的队列库。
【解题思路】 使用数组实现循环队列 。除了存放队中元素的data数组、队头指针front和队尾指针rear外，增加容量capacity和长度length数据成员，让front指向队头元素的前一个位置，rear指向队尾元素的位置。初始时front=rear=0。
（1）队空条件：length=0。
（2）队满条件：length=capacity（ k ）。
（3）元素 x 进队：rear=（rear+1）%capacity；data[rear]= x 。
（4）出队元素 x ：front=（front+1）%capacity； x =data[front]。
例如，如图4.3所示的循环队列是将元素10和20进队后的结果，容量capacity=4，长度length=2，front=0，rear=2。
图4.3 一个循环队列
【问题描述】 实现MyCircularDeque类。
（1）MyCircularDeque（int k）：构造函数，双端队列的容量为 k 。
（2）boolean insertFront（）：将一个元素添加到双端队列的头部，如果操作成功，返回true，否则返回false。
（3）boolean insertLast（）：将一个元素添加到双端队列的尾部，如果操作成功，返回true，否则返回false。
（4）boolean deleteFront（）：从双端队列的头部删除一个元素，如果操作成功，返回true，否则返回false。
（5）boolean deleteLast（）：从双端队列的尾部删除一个元素，如果操作成功，返回true，否则返回false。
（6）int getFront（）：从双端队列的头部获得一个元素，如果双端队列为空，返回-1。
（7）int getRear（）：获得双端队列的最后一个元素，如果双端队列为空，返回-1。
（8）boolean isEmpty（）：若双端队列为空，返回true，否则返回false。
（9）boolean isFull（）：若双端队列满了，返回true，否则返回false。
示例：
【限制】 1≤ k ≤1000，0≤value≤1000，insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty和isFull的调用次数不超过2000次。
【解题思路】 使用数组实现循环双端队列 。除了存放队中元素的data数组、队头指针front和队尾指针rear外，增加容量capacity和长度length数据成员，同样让front指向队头元素的前一个位置，rear指向队尾元素的位置。其进队和出队操作的过程如下。
（1）元素 x 从前端进队时，在front处放置 x ，将front循环减1，长度length加1。
（2）元素 x 从后端进队时，将rear循环加1，在rear处放置 x ，长度length加1。
（3）从前端出队时，将front循环加1，长度length减1。
（4）从后端出队时，将rear循环减1，长度length减1。
例如，如图4.4所示的双端队列是进队元素 a 和 b 的结果，容量capacity=4，长度length=2，front=0，rear=2。
图4.4 一个双端队列
【问题描述】 请设计一个队列FrontMiddleBack，支持在前、中和后3个位置的push和pop操作。
（1）FrontMiddleBack（）：初始化队列。
（2）void pushFront（int val）：将val添加到队列的最前面。
（3）void pushMiddle（int val）：将val添加到队列的正中间。
（4）void pushBack（int val）：将val添加到队列的最后面。
（5）int popFront（）：将最前面的元素从队列中删除并返回值，如果删除之前队列为空，那么返回-1。
（6）int popMiddle（）：将正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回-1。
（7）int popBack（）：将最后面的元素从队列中删除并返回值，如果删除之前队列为空，那么返回-1。
注意，当有两个中间位置的时候，选择靠前面的位置进行操作。例如，将6添加到[1，2，3，4，5]的中间位置，结果数组为[1，2，6，3，4，5]；从[1，2，3，4，5，6]的中间位置删除元素，则数组变为[1，2，4，5，6]。
示例：
【限制】 1≤val≤10 9 ，最多调用1000次pushFront、pushMiddle、pushBack、popFront、popMiddle和popBack。
【解法1】 使用双端队列作为前中后队列 。设计双端队列dq，初始为空队，dq的两个端点分别称为前端和后端。
（1）FrontMiddleBack（）：初始化队列的操作。
（2）void pushFront（int val）：直接将val插入dq的前端。
（3）void pushMiddle（int val）：其操作如下。
①若原队列为空，则置front、mid和rear均指向结点s，length为1。
②若原队列非空，直接在dq的前端插入val。
③其他情况，求出dq中元素的个数 n ， i 从1到 n 循环：当 i = n /2+1时在dq的后端插入val，否则从dq的前端出队元素tmp并且将其从后端插入。
（4）void pushBack（int val）：直接将val插入dq的后端。
（5）int popFront（）：若原队列为空，返回-1，否则从dq的前端出队 x 并且返回 x 。
（6）int popMiddle（）：其操作如下。
①若原队列为空，返回-1。
②否则求出dq中元素的个数 n ， i 从1到 n 循环：当 i =（ n +1）/2时从前端出队 x ，否则从dq的前端出队元素tmp并且将其从后端插入，最后返回 x 。
（7）int popBack（）：若原队列为空，返回-1，否则从dq的后端出队 x 并且返回 x 。
在上述算法中，pushMiddle（int val）和popMiddle（）的时间复杂度均为 O （ n ），其他算法的时间复杂度均为 O （1）。对应的FrontMiddleBackQueue类如下。
C++：
提交运行：
Python：
提交运行：
【解法2】 使用带前中后指针的双链表作为队列 。设计一个双链表，每个结点存放一个队列元素，同时设计前、中、后3个指针成员（分别为front、mid、rear），为了方便，增加表示结点个数的length成员。例如，依次从队后（或者队尾）进队1、2、3和4后的队列如图4.5所示。
图4.5 依次从队后进队1、2、3和4后的队列
（1）FrontMiddleBack（）：初始化队列的操作是置front、mid和rear为空，length为0。
（2）void pushFront（int val）：该运算的操作是先创建存放val的结点s。
①若原队列为空，则置front、mid和rear均指向结点s，length为1。
②若原队列非空，将结点s插入结点front的前面，置front=s，当原结点的个数为奇数时前移mid，例如队列为[1，2，3]，mid=2，执行pushFront（4）变为[4，1，2，3]，新mid=1；当原结点的个数为偶数时mid不变，例如队列为[1，2]，mid=1，执行pushFront（4）变为[4，1，2]，仍然有mid=1。最后length增1。
（3）void pushMiddle（int val）：该运算的操作是先创建存放val的结点s。
①若原队列为空，则置front、mid和rear均指向结点s，length为1。
②若原队列只有一个结点，将结点s插入rear结点的前面，置front和mid指向结点s，最后length增1。
③其他情况，当原结点的个数为奇数时在结点mid之前插入s，结点s为新mid结点，例如队列为[1，2，3]，mid=2，执行pushMiddle（4）变为[1，4，2，3]，新mid=4；当原结点的个数为偶数时在结点mid之后插入s，结点s为新mid结点，例如队列为[1，2]，mid=1，执行pushMiddle（4）变为[1，4，2]，新mid=4。最后length增1。
（4）void pushBack（int val）：该运算的操作是先创建存放val的结点s。
①若原队列为空，则置front、mid和rear均指向结点s，length为1。
②若原队列非空，将结点s插入结点front的后面，置rear=s，当原结点的个数为偶数时后移mid，例如队列为[1，2]，mid=1，执行pushBack（3）变为[1，2，3]，新mid=2；当原结点的个数为奇数时mid不变，例如队列为[1，2，3]，mid=2，执行pushBack（4）变为[1，2，3，4]，仍然有mid=2。最后length增1。
（5）int popFront（）：该运算的操作如下。
①若原队列为空，返回-1。
②若原队列只有一个结点，置 x 为front结点值，删除front结点，置front、rear和mid均为空，length为0，返回 x 。
③其他情况，置 x 为front结点值，当原结点的个数为偶数时mid后移，例如队列为[1，2]，mid=1，执行popFront（）变为[2]，新mid=2；当原结点的个数为奇数时mid不变，例如队列为[1，2，3]，mid=2，执行popFront（）变为[2，3]，仍然有mid=2。再删除front结点，length减1，返回 x 。
（6）int popMiddle（）：该运算的操作如下。
①若原队列为空，返回-1。
②若原队列只有一个结点，置 x 为mid结点值，删除mid结点，置front、rear和mid均为空，length为0，返回 x 。
③若原队列只有两个结点，置 x 为mid结点值，删除mid结点，置front和rear均为rear，length为1，返回 x 。
④其他情况，置 x 为mid结点值，当原结点的个数为偶数时mid后移，例如队列为[1，2]，mid=1，执行popMiddle（）变为[2]，新mid=2；当原结点的个数为奇数时mid前移，例如队列为[1，2，3]，mid=2，执行popMiddle（）变为[1，3]，新mid=1。再删除原mid结点，length减1，返回 x 。
从队列中删除并返回值，如果删除之前队列为空，那么返回-1。
（7）int popBack（）：该运算的操作如下。
①若原队列为空，返回-1。
②若原队列只有一个结点，置 x 为rear结点值，删除rear结点，置front、rear和mid均为空，length为0，返回 x 。
③其他情况，置 x 为rear结点值，当原结点的个数为偶数时mid不变，例如队列为[1，2]，mid=1，执行popBack（）变为[1]，仍然有mid=1；当原结点的个数为奇数时mid前移，例如队列为[1，2，3]，mid=2，执行popBack（）变为[1，2]，新mid=1。再删除rear结点，length减1，返回 x 。
上述所有算法的时间复杂度均为 O （1），比解法1的设计更加高效。
【问题描述】 请使用两个栈实现先入先出队列。该队列应该支持一般队列支持的所有操作（push、pop、peek、empty），实现MyQueue类。
（1）void push（int x）：将元素 x 推到队列的末尾。
（2）int pop（）：从队列的开头移除并返回元素。
（3）int peek（）：返回队列开头的元素。
（4）bool empty（）：如果队列为空，返回true，否则返回false。
示例：
【限制】 1≤ x ≤9，最多调用100次push、pop、peek和empty。假设所有操作都是有效的（例如，一个空的队列不会调用pop或者peek操作）。
进阶：实现每个操作的均摊时间复杂度为 O （1）的队列，就是执行 n 个操作的总时间复杂度为 O （ n ），即使其中一个操作可能花费较长时间。
【解题思路】 用两个 stack 栈实现一个队列 。设计一个主栈st和一个辅助栈tmpst，st栈如图4.6（a）所示，以栈底作为队头，栈顶作为队尾，进队和进栈一致，执行push（x）的结果如图4.6（b）所示，即直接将 x 进入st栈。
图4.6 push（x）的过程
若st栈如图4.6（a）所示， a 0 为队头元素，执行pop（）的操作如下：
①将st栈的所有元素依次出栈并进入tmpst栈，如图4.7（a）所示。
②此时 a 0 是tmpst栈的栈顶元素，出栈 a 0 。
③将tmpst栈的剩余元素依次出栈并进入st栈，如图4.7（b）所示。最后返回 a 0 。
图4.7 pop（）的过程
top（）的操作与pop（）类似。从中看出，tmpst栈仅用于求队头元素，在一般情况下是空栈。对应的MyQueue类如下。
C++：
提交运行：
显然，上述pop（）和top（）算法的时间复杂度均为 O （ n ）。在执行一次步骤①后，st栈变为空，若tmpst栈非空，如果此时执行push（x），仅将 x 进入st栈，此时出队的元素正好是tmpst栈的栈顶元素，所以执行pop（）当tmpst非空时不必执行步骤③，只有当tmpst栈为空时才执行步骤③。这样改进后每个操作的均摊时间复杂度为 O （1）。对应的MyQueue类如下。
C++：
提交运行：
采用改进的方法对应Python语言的MyQueue类如下。
Python：
提交运行：
