栈与队列

（1）理论基础

栈：先进后出的数据结构

队列：先进先出的数据结构

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能，STL中栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

（2）栈的常用接口

stack.push(x);//向栈中添加元素x
stack.pop();//移除栈顶元素
/*在使用时需要检查stack是否为空，否则访问到空栈的顶部元素，导致段错误*/
int result=stack.top();//返回栈顶的元素
bool is_empty=stack.empty();//判断栈是否为空
int size=stack.size();//获取栈的大小

（3）队列的常用接口

que.push(x);//向队列中添加元素x
que.pop();//移除队头第一个元素
int result=que.front();//返回第一个元素
int result=que.back();//返回最后一个元素
bool is_empty=que.empty();//判断栈是否为空
int size=que.size();//获取队列的大小