步步為營（十）常用資料結構（3）STL-Deque（雙端隊列）

和前兩個不同，雙端隊列（double-end queue）更像是一種折衷的産物。可能是人們發現Vector和List的水火不容，于是發明了這麼一個集兩家所長的東西。

雙端隊列具有Vector和List的優點，或者說二者的特征點都可以在Deque裡實作。

我真想說，這是一個湊不要臉的結構……原因如下：

1. 支援随機通路（下标通路，也就是[]操作符）(Vector)
2. 支援在兩端進行資料插入和删除（List）
3. Vector因為連續記憶體通路快，List因為動态記憶體消耗少，于是…… Deque在内部使用連續記憶體+連結清單的方式把一塊一塊的連續記憶體串聯起來使用~

諸葛村夫都要炸了好嗎~我從未見過如此厚顔無恥之結構！！！

好了，不鬧了。

雙端隊列由于吸取了List和Vector的優點，使得在同一種結構下可以進行某種操作都可以消耗盡量少的資源，使得在很多複雜條件下，Deque的使用變得相當順手。

但是Deque在單項性能上還是比不過單純的List或者Vector，也就是說：

1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用Vector
2. 如果你需要大量的插入和删除，而不關心随即存取，則應使用List
3. 如果你需要随即存取，而且關心兩端資料的插入和删除，則應使用Deque

好一個黑-白-灰組合~~

下面列出Deque的成員函數說明：

deque<Elem> c     建立一個空的deque。

      deque<Elem> c1(c2)     複制一個deque。

      deque<Elem> c(n)     建立一個deque，含有n個資料，資料均已預設構造産生。

      deque<Elem> c(n, elem)    建立一個含有n個elem拷貝的deque

      deque<Elem> c(beg,end)     建立一個以[beg;end)區間的deque

      ~deque<Elem>()     銷毀所有資料，釋放記憶體


      assign(beg,end)    将[beg; end)區間中的資料指派給c。

      assign(n,elem)    将n個elem的拷貝指派給c。

       at(idx)     傳回索引idx所指的資料，如果idx越界，抛出out_of_range。

      back()     傳回最後一個資料，不檢查這個資料是否存在。

      begin()    傳回疊代器中的第一個資料。

      clear()     移除容器中所有資料。

      empty()    判斷容器是否為空。

      end()    指向疊代器中的最後一個資料位址。

     erase(pos)     删除pos位置的資料，傳回下一個資料的位置。

     erase(beg,end)     删除[beg,end)區間的資料，傳回下一個資料的位置。

     front()     傳回第一個資料。

     get_allocator    使用構造函數傳回一個拷貝。

     insert(pos,elem)     在pos位置插入一個elem拷貝，傳回新資料位置

     insert(pos,n,elem)     在pos位置插入>n個elem資料。無傳回值

     insert(pos,beg,end)    在pos位置插入在[beg,end)區間的資料。無傳回值

     max_size()     傳回容器中最大資料的數量。

     pop_back()     删除最後一個資料。

     pop_front()    删除頭部資料。

     push_back(elem)    在尾部加入一個資料。

     push_front(elem)    在頭部插入一個資料。

     rbegin()    傳回一個逆向隊列的第一個資料。

     rend()    傳回一個逆向隊列的最後一個資料的下一個位置。

     resize(num)     重新指定隊列的長度。

     size()    傳回容器中實際資料的個數。

     swap(c2)   将c1和c2元素互換。

     swap(c1,c2)     将c1和c2元素互換。