Deque雙端隊列容器

一、基本原理

    deque的元素數(shù)據(jù)采用分塊的線性結(jié)構(gòu)進行存儲，如圖所示。deque分成若干線性存儲塊，稱為deque塊。塊的大小一般為512個字節(jié)，元素的數(shù)據(jù)類型所占用的字節(jié)數(shù)，決定了每個deque塊可容納的元素個數(shù)。

所有的deque塊使用一個Map塊進行管理，每個Map數(shù)據(jù)項記錄各個deque塊的首地址。Map是deque的中心部件，將先于deque塊，依照deque元素的個數(shù)計算出deque塊數(shù)，作為Map塊的數(shù)據(jù)項數(shù)，創(chuàng)建出Map塊。以后，每創(chuàng)建一個deque塊，都將deque塊的首地址存入Map的相應數(shù)據(jù)項中。

  在Map和deque塊的結(jié)構(gòu)之下，deque使用了兩個迭代器M_start和M_finish，對首個deque塊和末deque塊進行控制訪問。迭代器iterator共有4個變量域，包括M_first、M_last、M_cur和M_node。M_node存放當前deque塊的Map數(shù)據(jù)項地址，M_first和M_last分別存放該deque塊的首尾元素的地址（M_last實際存放的是deque塊的末尾字節(jié)的地址），M_cur則存放當前訪問的deque雙端隊列的元素地址。

二、應用

4、插入

1）deque 具有高效的頭部插入元素的函數(shù)push_front()。

void push_front(const T&)

2）將在pos位置之前，插入新元素x。

iterator insert(iterator pos, const T& x)

5、刪除

（1）void pop_front()    

刪除deque的第一個元素。

（2）void pop_back()

刪除deque的最后一個元素。         //聲明一點是vector 沒有pop_back();

（3）iterator erase(iterator pos)

刪除pos所指向的元素。

（4）iterator erase(iterator first, iterator last)

刪除迭代器區(qū)間[first,last)所指向的所有元素。

（5）void clear()

刪除所有元素。

6、交換

void swap(deque&)

如d1.swap(d2);

7、其它

（1）bool empty()

判斷deque容器是否已有元素，是則返回true，否則返回false。

（2）size_type size()

當前deque容器的元素個數(shù)。

（3）size_type max_size()

系統(tǒng)所支持的deque容器的最大元素個數(shù)。

（4）reference front()

deque容器的首元素（引用返回），要求deque不為空。

（5）reference back()

deque容器的末元素（引用返回），要求deque不為空。