deque雙端隊(duì)列，分段連續(xù)空間數(shù)據(jù)結(jié)構(gòu)，由中控的map（與其說map，不如說是數(shù)組）控制，map中每個(gè)槽指向一個(gè)固定大小的緩沖（連續(xù)的線性空間）。
deque的迭代器，關(guān)鍵的四個(gè)指針：
cur //所指緩沖區(qū)中的現(xiàn)元素first //所指緩沖區(qū)中的頭last //所指緩沖區(qū)中的尾node //指向中控的槽
start指向中控第一個(gè)槽位的buffer中的第一個(gè)元素，finish指向中控最后一個(gè)槽位指向的buffer中的最后一個(gè)元素。
每次新建deque時(shí)，創(chuàng)建中控map和nodes，根據(jù)初始的元素個(gè)數(shù)計(jì)算開始槽位nstart和nfinish。
map_pointer nstart = map + (map_size - num_nodes) / 2; map_pointer nfinish = nstart + num_nodes - 1;
這樣做的原因是雙端push或pop時(shí)的平均性能最佳。
如圖，如果需要push_back，剛好finish指向的buffer將滿，會(huì)向map中finish后一個(gè)槽位新建一個(gè)buffer node；對應(yīng)的push_front會(huì)向map中start前一個(gè)槽位新建一個(gè)buffer node；如果map不夠空間，也還是要reallocate_map，重新分配map空間遷移已有數(shù)據(jù)，釋放老數(shù)據(jù)。
std::stack，std::queue
stack是FILO的數(shù)據(jù)結(jié)構(gòu)，只有一個(gè)出口，若以上述的deque實(shí)現(xiàn)，封住deque的頭端開口，輕易就能實(shí)現(xiàn)stack，stack往往不被歸為container，而被歸為container adapter，源碼十分簡短，底層容器就是deque（當(dāng)然也可以使用list：如stack<int, list >）
class Sequence = deque<T>
queue是FIFO的數(shù)據(jù)結(jié)構(gòu)，封住back的出口和front的入口即可輕易實(shí)現(xiàn)，代碼同stack，也被認(rèn)為是container adapter。
