C++中的双端队列(deque)

基本含义

deque (double-ended queue，双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。

优缺点

尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。

实现双端队列

实现双端队列最好使用双向链表，因为在双向链表中，链表中每一个节点，都能指向它的前一个节点和后一个节点，只操作一个节点，就能进行插入和删除操作

因此使用双向链表实现队列时，只要队列中知道头尾两个节点，就可以在队列的两端进行插入和删除操作。

双端队列中，使用双向链表，所以可以声明一个内部类DLNode表示链表中的每一个节点，因为节点中有数据，前一个节点的引用和后一个节点的引用，所以它有三个属性data, next 和previous, 又因为双端队列中要知道链表中头尾两个节点的引用，所以还要声明两个属性firstNode, lastNode.

向队列(链表)尾部添加元素，就是创建一个新节点，如果链表为空，直接让firstNode和lastNode指向这个新节点，如果链表不为空，lastNode.next指向新节点，新节点的previous 指向lastNode，最后，lastNode指向新节点

向队列(链表)头部插入一个元素，就是创建一个新元素，它的lnext要指向firstNode, firstNode的previous指向新节点，然后firstNode 指向新节点

从队列(链表)头部，删除一个元素，如果链表为空，抛出异常，如果链表不为空，firstNode = firstNode.next; 同时iirstNode 的 previous只为null。如要只有一个元素，删除之后，firstNode 为null，那lastNode也为null。
从队列(链表)尾部删除一个元素，就是通过lastNode, 找到它的前一个节点，前一个节点的next 为null，就可以。