【C++】STL——stack&queue的基本使用

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( )

*常用函数说明*stack()构造空的栈empty()检查stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()**将stack中尾部的元素弹出

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( )

*常用函数说明*queue()构造空的队列empty()检查队列是否为空size()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列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的结构示意图：**