栈（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_TEMPLATES template <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 都是容器的配接器。