前言
在数据结构部分我们通过C实现了栈和队列，本节我们将了解C++版本下的
stack和queue。我们将会很轻松的学习这部分知识。
1.stack的介绍和使用
1.1 stack的介绍
后进先出
1.2 stack的使用
| 函数加接口说明 | 函数加接口说明 |
| stack() 构造空的栈 | empty()检测stack是否为空 |
| size()返回stack中元素的个数 | top()返回栈顶元素的引用 |
| push()将元素val压入stack中 | pop()将stack中尾部的元素弹出 |
void test_stack() { stack<int>s1; s1.push(1); s1.push(2); s1.push(3); s1.push(4); s1.push(5); cout << s1.size() << endl; cout << s1.top() << endl; s1.pop(); cout << s1.top() << endl; }
1.3 stack 的模拟
stack我们是先进先出，并从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。
我们将vector设为私有成员
#include <vector> namespace my_stack { template <class T> class stack { public: stack() { } void push(const T& x) { c.push_back(x); } void pop() { c.pop_back(); } const T& top() { return c.back(); } size_t size()const { return c.size(); } bool empty()const { return c.empty(); } private: std::vector<T> c; }; }
这样子实现有个缺陷，如果我们需要实现一个链式栈就无法，可能会想到改成list，但是很麻烦。
我们可以导入一个容器类来进行实现。在后面的适配器我们会讲到。
2. queue的介绍和使用
2.1 queue的介绍
1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元 素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。
该底层容器应至少 支持以下操作:
empty：检测队列是否为空 size：返回队列中有效元素的个数
front：返回队头元素的引用 back：返回队尾元素的引用
push_back：在队列尾部入队列 pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
2.2 queue的使用
void test_queue() { queue<int>q1; q1.push(1); q1.push(2); q1.push(3); q1.push(4); q1.push(5); cout << q1.size() << endl; cout << q1.front() << endl; cout << q1.back() << endl; q1.pop(); cout << q1.front() << endl; }
2.3 queue的模拟
因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实 现queue。
#include <list> namespace my_queue { template <class T> class queue { public: queue() { } void push(const T& x) { c.push_back(x); } void pop() { c.pop_back(); } T& back() { return c.back(); } T& front() const return c.front(); } size_t size()const { return c.size(); } bool empty()const { return c.empty(); } private: std::list<T> c; }; }
通过官方的queue和stack我们可以看到，在类模版中都定义了一个class Container=deque;
所以我们同样类似这样子写，在后续我们会讲解deque的知识。
namespace my_stack { template <class T,class Container=vector<T>> class stack { public: stack() { } void push(const T& x) { con.push_back(x); } void pop() { con.pop_back(); } const T& top() { return con.back(); } size_t size()const { return con.size(); } bool empty()const { return con.empty(); } const T& front() const { return con.front(); } const T& back() const { return con.back(); } private: Container con; }; }
这样我们既可以写顺序栈也可以链式栈
my_stack::stack>s1;
my_stack::stack>s1；
这里我们使用了vector来当默认参数，而在方法中却穿插了链表的方法，编译时却没有报错，这是因为这是类模版，在主函数类模板实例化时，按需实例化，使用哪些成员函数就实例化哪些，不会全实例化，所以当我们使用vector的时候，不调用list的方法就行了。
#include <list> namespace my_queue { template<class T, class Container = list<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T& front() const { return _con.front(); } const T& back() const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }
C++之stack 和 queue（下）：https://developer.aliyun.com/article/1625002
