一、stack的相关概念
stack是一种容器适配器，专门用在具有后进先出的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作；
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部（即栈顶）被压入和弹出；
stack的底层容器可以是任何标准的容器类模板或一些其他特定的容器类，这些容器类应该支持以下操作：
- empty：判空操作
- back：获取尾部操作元素
- push_back：尾部插入元素操作
- pop_back：尾部删除元素操作
注：标准容器vector、deque和list 均符合这些需求。
二、STL中stack的使用
stack的模板的使用相对简单，只要掌握empty()、size()、top()、**push()及pop()**这几个stack类成员方法。下图的使用案例结合结果能够清晰地看出上述成员方法的功能：
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
三、stack的模拟实现
容器适配器（亦称“配接器”）是一个封装了序列容器的类模板，下面使用适配器模式来实现stack：
namespace joes
{
template<class T,class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
return _con.push_back(x);
}
void pop()
{
return _con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
链式栈测试:
void test_stack01()
{
stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout<<"st's size:"<<st.size()<<endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
数组构建的栈
void test_stack02()
{
stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout<<"st's size:"<<st.size()<<endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
测试结果：
