棧（stack）
?stack是一種先進后出（First In Last Out，FILO）的數據結構，它只有一個口，平常在我們寫深度優先遍歷算法時，，就會用到棧，stack允許我們增加，移除，取得最頂端元素。但是除了最頂端元素之外，沒有任何其他方法可以存取stack的其它元素，因此stack不允許有遍歷行為。
以某種既有容器為底層結構，將其接口改變，使之符合 “先進后出” 的特性，形成一個 stack ，是很容易做到的。deque 是雙向開口的數據結構，若以 deque為底部結構并封閉其頭部端口，便輕而易舉形成一個 stack 。因此，SGI STL 便以 deque 作為缺省情況下的 stack 底部結構。
template <class _Tp, class _Sequence> class stack { public:typedef typename _Sequence::value_type value_type;typedef typename _Sequence::size_type size_type;typedef _Sequence container_type;typedef typename _Sequence::reference reference;typedef typename _Sequence::const_reference const_reference; protected:_Sequence c; //底層容器 public:stack() : c() {}explicit stack(const _Sequence& __s) : c(__s) {}//以下完全利用_Sequence c 的操作完成 stack 的操作bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference top() { return c.back(); }const_reference top() const { return c.back(); }//末端進，末端出void push(const value_type& __x) { c.push_back(__x); }void pop() { c.pop_back(); } };
?
stack 因為所有元素都必須遵守“先進后出”的條件，只有 stack 頂端的元素，才有機會被外界取用，stack 不提供走訪功能，因此沒有迭代器。
當然還可以以 list 作為 stack 底層容器：
#include <iostream> #include <string> #include <stack> #include <list> using namespace std; int main() { //用雙向鏈表作為底層容器 stack<int, list<int> > temp;for(int i = 0; i < 10; i++){temp.push(i); //0 1 2 3 4 5 6 7 8 9 }for(int i = 0; i < 10; i++){printf("%d ", temp.top()); //9 8 7 6 5 4 3 2 1 0 temp.pop();}return 0; }
隊列（stack）
queue是一種先進先出（First In First Out，FIFO）的數據結構，它有兩個出口，queue 允許新增元素，移除元素，從最低端加入元素，取得最頂端元素。但除了最底端可以加入，最頂端可以取出外，沒有其他任何方法可以存取 queue 的其他元素，因此 queue 不允許有遍歷行為，也就是沒有迭代器。同棧一樣，STL里面默認 deque 作為缺省情況下的 queue 底部結構：
template <class _Tp, class _Sequence> class queue {public:typedef typename _Sequence::value_type value_type;typedef typename _Sequence::size_type size_type;typedef _Sequence container_type;typedef typename _Sequence::reference reference;typedef typename _Sequence::const_reference const_reference; protected:_Sequence c; //底層容器 public:queue() : c() {}explicit queue(const _Sequence& __c) : c(__c) {}//以下完全利用 Sequence c 的操作完成queue操作bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference front() { return c.front(); }const_reference front() const { return c.front(); }reference back() { return c.back(); }const_reference back() const { return c.back(); }void push(const value_type& __x) { c.push_back(__x); }void pop() { c.pop_front(); } };
?
優先級隊列（priority_queue）
priority_queue 是一種具有權值觀念的 queue，他允許加入新元素，移除舊元素，審視元素值等功能，同樣只支持底部加元素，頂端取元素，除此以外別無其他存取元素途徑。但priority_queue 其內部的元素并非按照被推入的次序排列，而是自動依照元素的權值排列，權值越高，排在越前面。缺省情況下，priority_queue 利用max-heap 完成，后者是一個以vector表現的 complete binary tree。max-heap 可以滿足 priority_queue 所需要的 “權值從高到低自動地減排序” 的特性。
template <class _Tp, class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),class _Compare__STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) > class priority_queue {public:typedef typename _Sequence::value_type value_type;typedef typename _Sequence::size_type size_type;typedef _Sequence container_type;typedef typename _Sequence::reference reference;typedef typename _Sequence::const_reference const_reference; protected:_Sequence c; //底層容器_Compare comp; //排序規則 public:priority_queue() : c() {}explicit priority_queue(const _Compare& __x) : c(), comp(__x) {}//以下用到的 make_heap(), push_heap() 和 pop_heap()都是泛型算法//任何一個構造函數都在底層產生一個 implicit representation heap (隱式表述堆)priority_queue(const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x) { make_heap(c.begin(), c.end(), comp); }#ifdef __STL_MEMBER_TEMPLATEStemplate <class _InputIterator>priority_queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }template <class _InputIterator>priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x): c(__first, __last), comp(__x) { make_heap(c.begin(), c.end(), comp); }template <class _InputIterator>priority_queue(_InputIterator __first, _InputIterator __last,const _Compare& __x, const _Sequence& __s): c(__s), comp(__x){ c.insert(c.end(), __first, __last);make_heap(c.begin(), c.end(), comp);}#else /* __STL_MEMBER_TEMPLATES */priority_queue(const value_type* __first, const value_type* __last) : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }priority_queue(const value_type* __first, const value_type* __last, const _Compare& __x) : c(__first, __last), comp(__x){ make_heap(c.begin(), c.end(), comp); }priority_queue(const value_type* __first, const value_type* __last, const _Compare& __x, const _Sequence& __c): c(__c), comp(__x) { c.insert(c.end(), __first, __last);make_heap(c.begin(), c.end(), comp);}#endif /* __STL_MEMBER_TEMPLATES */bool empty() const { return c.empty(); }size_type size() const { return c.size(); }const_reference top() const { return c.front(); }void push(const value_type& __x) {//push_heap()是泛型算法，先利用底層的push_back() 將新元素推入末端，再重排heap __STL_TRY{c.push_back(__x); push_heap(c.begin(), c.end(), comp);}__STL_UNWIND(c.clear());}void pop(){//pop_heap()是泛型算法，從 heap 內取出一個元素，它并不是真正將元素彈出//而是重排 heap, 然后以底層容器的 pop_back() 取得被彈出的元素 __STL_TRY {pop_heap(c.begin(), c.end(), comp);c.pop_back();}__STL_UNWIND(c.clear());} };
?
priority_queue 的所有元素進出都有一定規則，只有 queue 頂端的元素，也就是權值最高者，才有機會被外界取用，priority_queue沒有迭代器。
priority_queue 測試如下：
#include <iostream> #include <string> #include <queue> #include <list> using namespace std; int main() {int a[] = {0, 1,12,5,56,3,23,16}; priority_queue<int> temp(a, a + 8);cout << "top element: " << temp.top() << endl; //56 cout << "output from top: ";int pd_size = temp.size();for(int i = 0; i < pd_size; i++){cout << temp.top() <<" "; //56 23 16 12 5 3 1 0 temp.pop();}return 0; }
stack , queue , priority_queue 都是以底部容器完成其所有工作，而這些具有 “修改某物接口，形成另一種風貌” 的性質的數據結構， 成為adapter（配接器），?stack , queue , priority_queue 都是容器的配接器。
?
