题目在《算法导论》机械工业出版社 中文版 第三版 P131 10.1-5

题目描述

题目描述：
栈插入和删除元素只能在同一端进行，队列的插入和删除操作分别在两端进行，与它们不同的是有一种双端队列(deque)，其插入和删除都可以在两端进行。
写出4个时间均为O（1）的过程，分别实现在双端队列的两端插入和删除元素的操作，该队列是用一个数组来实现的。

双端队列的概念：

  1. 双端队列是一个限定插入和删除操作的数据结构，具有队列和栈的性质。
  2. 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
  3. 双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。
  4. 如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。

简易实现

根据概念，我做了简单的实现：

如图，先只考虑左侧进出，右侧是对称的，可以类比。
让head虚指，进而当插入时可以直接将元素x放入指向的位置，然后左移head即可。
当出队时，让head先自增，再将指向的4出队即可。
值得注意的是，当head-tail==1时，此时deque中没有元素，需要抛出下溢 异常
伪代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
addHead(x):
      Deque[head--]=x;             //一句代码完成先填值，再移动指针
addTail(x):
      Deque[tail++]=x;
      
popHead():
      if(head-tail == 1)
         throw "deque underflow"
      return Deque[++head];      //一句代码完成先移动指针，再出队。
 popTail():
      if(head-tail == 1)
         throw "deque underflow"
      return Deque[--tail];