首页 > 代码库 > STL容器适配器 stack, queue
STL容器适配器 stack, queue
stack是一种后进先出（last in first out）的数据结构。它只有一个出口，如图所示。stack允许新增元素，删除元素，取得最顶端元素。但除了最顶端外，没有其他任何地方可以存储stack的其他元素，换言之，stack不允许有遍历行为。
将元素推入stack的操作称为push, 将元素推出stack的操作称为pop.
为什么将stack称为适配器呢？我们先来看看适配器是怎么定义的。具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter（适配器）。换言之，由于stack的性质，可以使用vector或deque或list为底部结构进行一定的修改，轻易形成一个stack.
来看看stack的模板声明：
template<class T, class Sequence = deque<T>>class stack {// …protected: Sequeue c; //底层容器public: bool empty() const { return c.empty(); }
size_type size() const { return c.size(); } reference top() { return c.back(); } const_reference top() { return c.back(); } void push(const value_type& x) { c.push_back(x); } void pop() { c.pop_back(); }};
stack有2个模板参数，第二个Sequence(底层容器)默认的为deque。当然如果我们需要使用vector或list的话，必须自己指定出来。
测试代码：
#include <stack>#include <list>#include <vector>#include <iostream>#include <algorithm>using namespace std;int main(){// stack<int, vector<int>> mystack; // 底层容器使用vector// stack<int, deque<int>> mystack; // 底层容器使用deque (默认情况下） stack<int, list<int>> mystack; // 底层容器使用list mystack.push(1); mystack.push(3); mystack.push(6); mystack.push(7); mystack.push(2); cout << mystack.size() << endl; // 5 cout << mystack.top() << endl; // 2 mystack.pop(); cout << mystack.top() << endl; // 7 mystack.pop(); cout << mystack.top() << endl; // 6 mystack.pop(); cout << mystack.top() << endl; // 3 cout << mystack.size() << endl; // 2 return 0;}
queue(队列)是一种先进先出（first in first out）的数据结构。他有两个端口，如下图所示。queue允许新增元素，删除元素，从最底端加入元素，取得最顶端元素等，但除了最底端可以加入，最顶端可以取出外，没有任何其他方法可以存取queue的其他元素。换言之，queue不允许有遍历行为。
将元素推入queue的操作称为push, 将元素推出queue的操作称为pop.
来看看queue的模板声明：
template<class T, class Sequence = deque<T>>class queue {// …protected: Sequeue c; //底层容器public: bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() { return c.front(); } reference back() { return c.back(); } const_reference back() { return c.back(); } void push(const value_type& x) { c.push_back(x); } void pop() {c.pop_front(); }};
由于queue的结构性质，无法使用vector作为其底层容器（由于效率问题，vector类并未定义相关front函数），我们可以使用deque(默认）和list作为它的底层容器。
测试代码：
#include <queue>#include <list>#include <iostream>#include <algorithm>using namespace std;int main(){ // queue<int, deque<int>> myque; // 使用deque作为底层容器（默认） queue<int, list<int>> myque; // 使用list作为底层容器 myque.push(1); myque.push(3); myque.push(6); myque.push(7); myque.push(2); cout << myque.size() << endl; // 5 cout << myque.front() << endl; // 1 myque.pop(); cout << myque.front() << endl; // 3 myque.pop(); cout << myque.front() << endl; // 6 myque.pop(); cout << myque.front() << endl; // 7 cout << myque.size() << endl; // 2 return 0;}
特别注意，由于stack,queue的特性，它们没有迭代器。
STL容器适配器 stack, queue