stack

一、stack简介

       stack是一种先进后出的数据结构。它只有一个出口，如下图所示。stack允许新增元素、移除元素、取得栈顶元素。但除了最顶端外，没有任何方法可以存取stack的其它元素。换言之，stack不允许有遍历行为（即stack没有迭代器）。

二、stack的定义方式

stack是以某种容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack。默认的底部结构是deque（双端队列），deque是双向开口的数据结构。

       由于stack是以底部容器完成其所有工作的，而具有这种"修改某物接口，形成另一种风貌"之性质者，称之为（adapter）配接器（好比苹果手机的耳机在没有配接器的情况下，是不可以使用圆柱插孔式的耳机的，有了配接器能够很好的适应）；往往stack不被归类为容器，而是容器配接器（容器适配器）。（注：deque示意图在文末）

stack<int> st1;             //默认不写第二个参数，底部容器是基于deque
stack<int,vector<int>> st2; //底部容器是基于vector

三、stack完整结构图

       下图即为stack的完整结构图，底部基于所选择的容器来进行数据的操作，只要选用的容器的功能能够满足stack的使用需求即可；

四、stack常用接口的使用

stack的核心接口由三个成员函数提供：push( )、top( )、pop( )。

push( ) --- 将一个元素压入stack内；

top( ) --- 返回栈顶元素的引用

pop( ) --- 从stack中移除栈顶元素

注意：如果你想移除stack的下一个元素同时返回它，就必须调用top( )和pop( )

void test_stack()
{
  stack<int> st;//实例化出一个栈，会调用它的构造函数 --- stack()
  st.push(1);
  st.push(2);
  st.push(3);
  st.push(4);//将1 2 3 4 压入栈中
  st.size();//返回栈中的元素个数
  while (!st.empty())//判断栈是否为空
  {
    cout << st.top() << " ";//取栈顶的元素
    st.pop();//删除栈顶的元素
  }
  cout << endl;
}

queue

一、queue的简介

       queue是一种先进先出的数据结构，它允许新增元素、移除元素、从队尾插入元素、取队头的元素。但除了队尾可以插入元素、队头取出元素之外，没有任何办法存取其他元素。queue也不允许有遍历行为（即queue没有迭代器）。

二、queue定义方式

queue是以某种容器作为底部结构，将其接口改变，使之符合“先进先出”的特性，形成一个queue。默认的底部结构是deque（双端队列），deque是双向开口的数据结构。

       由于queue是以底部容器完成其所有工作的，而具有这种"修改某物接口，形成另一种风貌"之性质者，称之为（adapter）配接器。往往queue不被归类为容器，而是容器配接器（容器适配器）。（注：deque示意图在文末）

queue<int> q1;           //默认以deque为底部容器
queue<int,list<int>> q2; //以list为底部容器

三、queue完整结构图

       下图即为queue的完整结构图，底部基于所选择的容器来进行数据的操作，只要选用的容器的功能能够满足queue的使用需求即可；

四、queue常用接口的使用

queue的核心接口由四个成员函数提供：push( )、front( )、back( )、pop( )。

push( ) --- 将一个元素压入queue内；

front( ) --- 返回队头的元素

back( ) --- 返回队尾的元素

pop( ) --- 从queue中移除队头元素

注意：如果你想获取队头的数据又想处理掉它，就必须调用front( ) 和pop( )

void test_queue()
{
  queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);//尾插1 2 3 4
  q.size();//返回队列中有效元素的个数
  int qfront = q.front(); //取队头的数据
  int qback = q.back();   //取队尾的数据
  cout << qfront << " " << qback << endl;
  while (!q.empty())//判断队列是否为空
  {
    cout << q.front() << " "; 
    q.pop();//删除队头的数据
  }
  cout << endl;
}

       对于duque并未在这里做介绍，会在后续的stack和queue模拟实现中介绍，以下是deque的结构示意图：