C++STL之stack和queue以及deque详解

• stack和queue以及deque
• • stack的使用
  • queue的使用
  • 栈的OJ题练习
  • • 最小栈
    • 栈的压入、弹出序列
    • 逆波兰表达式求值
  • 什么是适配器？
  • 栈和队列的模拟实现
  • • 栈的模拟实现
    • 队列的模拟实现
  • deque
  • • deque的使用
    • deque的底层实现
    • deque的优缺点

翻译：

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行
   元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下
   操作：
   empty：判空操作
   back：获取尾部元素操作
   push_back：尾部插入元素操作
   pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，
   默认情况下使用deque。

栈和队列都叫做适配器/配接器，不是直接实现的，而是封装其他容器，包装转换实现出来的

#include
#include
#include
using namespace std;
void test_stack()
{
    stack st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    cout< 
 
queue的使用 
void test_queue()
{
    queue q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
       cout << q.empty() << endl;
    cout << q.size() << endl;
    while(!q.empty())
    {
        cout< 
 
栈的OJ题练习 
最小栈 
题目链接：
 
最小栈
 
题目描述：
 
 
 
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
 
 
push(x) —— 将元素 x 推入栈中。
 pop() —— 删除栈顶的元素。
 top() —— 获取栈顶元素。
 getMin() —— 检索栈中的最小元素。
 
 
解题思路：
 
 
解题代码：
 
class MinStack
{
public:
    void push(int val)
    {
        _st.push(val);
        if(_minst.empty() || val<=_minst.top())
        {
            _minst.push(val);
        }
    }
    void pop()
    {
        if(_st.top()==_minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    int top()
    {
        return _st.top();
    }
    int getMin()
    {
        return _minst.top();
    }
    stack _st;
    stack _minst;
};
 
栈的压入、弹出序列 
题目链接：
 
栈的压入、弹出序列
 
题目描述：
 
 
 
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 
 
 
0<=pushV.length == popV.length <=1000
 
 
-1000<=pushv[i]<=1000
 
 
popV的所有数字均在pushV里面出现过
 
 
pushV的所有数字均不相同
 
 
 
解题思路：
 
 
 
所有数据是入栈后才能出栈的，我们创建一个栈对象，首先将pushV里面的第一个元素入栈，pushi++，当栈顶元素和popi指向元素相等时，pop该栈顶元素，popi++，如果不相等继续将pushv后面的元素入栈
 
 
 
解题代码：
 
class Solution()
{
public:
	bool IsPopOrder(vector pushV,vector popV)
    {
        stack st;
        size_t pushi = 0,popi = 0;
        while(pushi 
逆波兰表达式求值 
题目描述：
 
 
 
根据 逆波兰表示法，求表达式的值。
 
 
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 
 
逆波兰表示法：
 
 
 
逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）
 
 
在计算机程序处理中缀表达式不方便进行计算，因为优先级的问题
 
 
 
1、中缀表达式转换成后缀表达式(逆波兰表达式)，后缀表达式：操作数在前，操作符在后
 
 
2、用后缀表达式进行运算(运算符到操作数的后面)
 
 
如何将中缀表达式转后缀表达式？
 
中缀转后缀，这里需要借助一个栈：
 
 
 
一个一个开始走，遇到操作数输出/存储容器中，遇到操作符，如果栈为空或者操作符优先级高于栈顶运算符将它入栈(运算符优先级高的先运算)，如果栈不为空，操作符比栈顶运算符优先级低或者相等，出栈顶的运算符，中缀表达式走完后将栈里面的运算符出栈
 
 
后缀表达式进行运算：
 
 
 
1、遇到操作数入栈
 
 
2、遇到操作符，连续取两个栈顶的数据进行运算，运算结果入栈
 
 
class Solution {
public:
    int evalRPN(vector& tokens) {
		stack st;
        for(const auto& str:tokens)
        {
            int left,right;
            if(str == "+"||str == "-"||str == "*"||str == "/")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                switch(str[0])
                {
                case '+': 
                	st.push(left+right);
                    break;
                case '-': 
                	st.push(left-right);
                    break;
                case '*': 
                	st.push(left*right);
                    break;
                case '/': 
                	st.push(left/right);
                    break;
                }
            }
            if(str == "+")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left+right);
            }
            else if(str == "-")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left-right);
            }
            else if(str == "*")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left*right);
            }
            else if(str == "/")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left/right);
            }
            else
            {
                //操作数
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};
 
什么是适配器？ 
假设一个代码模块 A，它的构成如下所示：
 
class A{
public:
    void f1(){}
    void f2(){}
    void f3(){}
    void f4(){}
};
 
现在我们需要设计一个模板 B，但发现，其实只需要组合一下模块 A 中的 f1()、f2()、f3()，就可以实现模板 B 需要的功能。其中 f1() 单独使用即可，而 f2() 和 f3() 需要组合起来使用，如下所示：
 
class B{
private:
    A _a;//封装A
public:
    void g1(){
        _a->f1();
    }
    void g2(){
        _a->f2();
        _a->f3();
    }
};
 
模板 B 将不适合直接拿来用的模板 A 变得适用了，因此我们可以将模板 B 称为 B 适配器。
 
容器适配器也是同样的道理，简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。容器适配器的底层实现和模板 A、B 的关系是完全相同的，即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。
 
栈和队列都是容器适配器
 
栈和队列的模拟实现 
栈的模拟实现 
栈满足后进先出的特性，在数据结构当中，我们可以使用顺序表和链表实现它，显然顺序表实现更优一些，因为顺序表进行尾插尾插的效率很高，而栈就是在一个方向上进行插入和删除。而无论是顺序表还是链表，都是可以实现栈这个数据结构的，所以我们可以封装容器，组合该容器中包含的成员函数。
 
#include
#include
#include
using namespace std;
//Stack
namespace Z
{    
    template
    class stack
    {
    private:
        Container _con;
    };
}
 
 
 
经过上面的介绍我们知道栈这个适配器也是一个模板，我们给栈这个适配器模板两个参数，一个是数据类型，一个是容器类型，成员是容器对象，通过它调用该容器的成员函数完成栈的功能
 
 
#include
#include
#include
using namespace std;
//Stack
namespace Z
{    
    class stack
    {
        //stack是一个Container适配(封装转换)出来的
        //template>//可以给缺省类型
        template>//可以给缺省类型
        //Container 尾认为是栈顶
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_back();
        }
        const T& top()
        {
            return _con.back();
        }
        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }
	private:
        Container _con;
    };
}
 
我们就可以这样显式实例化创建栈对象：
 
stack> st; 
 
或者使用链表来构造栈数据结构：
 
stack> st; 
 
我们为了还可以这样创建栈对象，不显式实例化不传第二个参数：
 
stack st; 
 
为了可以这样我们在定义模板参数那里，给第二个参数缺省值：
 
template>//可以给缺省类型
//template>//可以给缺省类型
//template>//可以给缺省类型
 
 
 
这里给vector也可以，list也可以，deque也可以。deque是双端队列，下面会讲解deque容器。
 
 
我们来测试一下：
 
void test_stack1()
{
    stack> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    stack st1;
    st1.push(10);
    st1.push(20);
    st1.push(30);
    st1.push(40);
    cout << "st:";
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    cout << "st1:";
    while (!st1.empty())
    {
        cout << st1.top() << " ";
        st1.pop();
    }
    cout << endl;
}

 
 
 
 
可以看到我们实现的栈适配器是正确的
 
 
队列的模拟实现 
经过了栈适配器的模拟实现，实现队列适配器就是举手之劳了，只需要注意Queue是队头出数据，队尾入数据，相当于是头删和尾插，因为vector容器没有实现头删，所以Queue不能封装vector：
 
//Queue
#include
#include
#include
#include
using namespace std;
namespace Z
{
    //Queue是一个Container适配(封装转换)出来的
    //template>//可以给缺省类型
    template>//可以给缺省类型
    class queue
    {
        //Container 尾认为是队尾，头认为是队头，队头出数据，队尾入数据
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_front();
        }
        const T& front()
        {
            return _con.front();
        }
        const T& back()
        {
            return _con.back();
        }
        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }
    private:
        Container _con;
    };
}
 
我们对队列进行测试：
 
void test_queue()
{
	//queue> q;//error,vector不支持头删头插，所以vector不能
    queue> q;
    q.push(1);
    q.push(2);
   	q.push(3);
   	q.push(4);
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}
int main()
{
    Z::test_queue();
    return 0;
}
 
 
上面接触到了deque，接下来我们了解一下deque：
 
deque 
 
 
双端队列，虽然它名字里有队列，但是他并不是队列，他并不要求先进先出
 
 
deque的使用 
#include
#include
using namespace std;

void test_deque()
{
	deque dp;
	//尾插
	dp.push_back(1);
	dp.push_back(2);
	dp.push_back(3);
	dp.push_back(4);
	//头插
	dp.push_front(10);
	dp.push_front(20);
	dp.push_front(30);
	dp.push_front(40);

	//尾删
	dp.pop_back();
	//头删
	dp.pop_front();
	//随机访问
	for (size_t i = 0; i < dp.size(); i++)
	{
		cout << dp[i] <<" ";
	}
	cout << endl;
}
int main()
{
	test_deque();
	return 0;
}
 
 
可以看到它既支持头插尾插，又支持头删尾删，还支持随机访问，它融合了vector和list的优点，从使用的角度，避开了它们各自的缺点：
 
list的缺点：不支持随机访问
 
vector的缺点：头部和中间插入删除效率低
 
看起来deque是一个非常完美的，那么真的有那么完美吗？我们来看deque的底层实现
 
deque的底层实现 
分析：如果deque真的像上面说的那么优秀，那么vector和list可能就被淘汰了，他还是有缺陷的，它的底层怎么实现的呢？
 
首先我们来看一下vector的优缺点：
 
vector
 
 
 
使用连续的物理空间
 
 
优点：
 
1、支持随机访问
 
2、CPU高速缓存命中率很高
 
缺点：
 
1、空间不够就需要增容，增容代价大，还存在一定空间浪费
 
2、头部和中间插入删除，效率低。O(N)
 
list
 
 
 
使用不连续的物理空间
 
 
优点：
 
1、按需申请释放空间
 
2、任意位置插入删除数据都是O(1)，效率高
 
缺点：
 
1、不支持随机访问
 
2、cpu高速缓存命中率低
 
结合vector和list优缺点，进行设计：
 
 
我们创建一个能够存储10个元素的数组，头插或者尾插时，当10个元素满了时，再开辟一个数组来存储，我们还需要一个中控数组存放来数组指针指向这一个个的数组，当是头插时，元素满了时，指向新开辟的数组的指针需要存储在中控数组中的那个指向满了的数组的前面，当是尾插时，元素满了时，指向新开辟的数组的指针需要存储在中控数组中的那个指向满了的数组的后面，当中控数组满了的时候就需要增容，但是代价较小
 
它的迭代器很复杂，迭代器封装了四个指针来维护结构，first是指向buff数组的起始位置，last是指向buff数组的结束位置，cur指向当前迭代器指向数组中的值的位置，node指向存储buff的指针数组的对应中控位置的指针：
 
 
iterator begin()
{
    return start;
}
iterator end()
{
    return finish;
}
deque dp;
iterator it = dp.begin();
while(it!=dp.end())
{
    *it;
    ++it;
}
 
尝试分析遍历deque时的迭代器遍历的操作：
 
 
 
start和finish都是iterator类型，deque的迭代器封装了四个指针：first是指向buff数组的起始位置，last是指向buff数组的结束位置，cur指向当前迭代器指向数组中的值的位置，node指向存储buff的指针数组的对应中控位置的指针。it!=dp.end()是怎么实现的？用迭代器中的cur指针去比较即可，那么*it呢？取得是*cur的值，++it相当于是，++cur，当cur等于last时，重置it的四个指针，指向下一个buff数组。
 
 
deque的优缺点 
1、双端队列，他很适合头插头删，尾插尾删，他去做stack和queue的默认适配容器很适合
 
2、双端队列中间插入删除数据，非常麻烦。效率不高
 
实现方案1：挪动整体数据
 
实现方案2：插入或者删除数据时，只挪动当前buff数据，搞一个变量记录每个buff数组的大小，但是这样会导致每个buff数组大小不一致，此时随机访问就会麻烦：
 
 
 
比如我们想要访问第15个数据，怎么找到它的数据呢？(i-1)/10可以算出它在第几个buff中，10为每个buff数组的大小，(i-1)%10就可以算出它在该buff中的位置(即下标)，当数组大小不一样时，随机访问就变得非常麻烦。
 
 
3、deque是一种折中(妥协)方案设计，不够极致，随机访问效率不及vector，任意位置插入删除不及list