stack和queue以及deque

stack文档

stack的使用

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void test_stack()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    cout<<st.empty()<<endl;
    cout<<st.size()<<endl;
    while(!st.empty())
    {
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<endl;
}
int main()
{
    test_stack1();
    return 0;
}

queue的使用

void test_queue()
{
    queue<int> 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<<q.front()<<" ";
        q.pop();
    }
    cout<<endl;
}
int main()
{
    test_stack1();
    return 0;
}

栈的OJ题练习

最小栈

题目链接：

最小栈

题目描述：

解题思路：

解题代码：

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<int> _st;
    stack<int> _minst;
};

栈的压入、弹出序列

题目链接：

栈的压入、弹出序列

题目描述：

解题思路：

解题代码：

class Solution()
{
public:
	bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        stack<int> st;
        size_t pushi = 0,popi = 0;
        while(pushi<pushV.size())
        {
            st.push(pushV[pushi++]);
            //栈中出的数据和出栈序列匹配上了
            while(!st.empty() && st.top() == popV[popi])
            {
                ++popi;
                st.pop();
            }
        }
        return st.empty();//st为空，说明全都匹配了
    }
};

逆波兰表达式求值

题目描述：

逆波兰表示法：

在计算机程序处理中缀表达式不方便进行计算，因为优先级的问题

如何将中缀表达式转后缀表达式？

中缀转后缀，这里需要借助一个栈：

后缀表达式进行运算：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
		stack<int> 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<iostream>
#include<list>
#include<deque>
using namespace std;
//Stack
namespace Z
{    
    template<class T,class Container>
    class stack
    {
    private:
        Container _con;
    };
}

#include<iostream>
#include<list>
#include<deque>
using namespace std;
//Stack
namespace Z
{    
    class stack
    {
        //stack是一个Container适配(封装转换)出来的
        //template<class T,class Container = std::vector<T>>//可以给缺省类型
        template<class T,class Container = std::deque<T>>//可以给缺省类型
        //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<int,std::vector<int>> st;

或者使用链表来构造栈数据结构：

stack<int,std::list<int>> st;

我们为了还可以这样创建栈对象，不显式实例化不传第二个参数：

stack<int> st;

为了可以这样我们在定义模板参数那里，给第二个参数缺省值：

template<class T,class Container = std::deque<T>>//可以给缺省类型
//template<class T,class Container = std::vector<T>>//可以给缺省类型
//template<class T,class Container = std::list<T>>//可以给缺省类型

我们来测试一下：

void test_stack1()
{
    stack<int, std::vector<int>> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    stack<int> 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<iostream>
#include<list>
#include<vector>
#include<deque>
using namespace std;
namespace Z
{
    //Queue是一个Container适配(封装转换)出来的
    //template<class T,class Container = std::list<T>>//可以给缺省类型
    template<class T, class Container = std::deque<T>>//可以给缺省类型
    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<int, std::vector<int>> q;//error,vector不支持头删头插，所以vector不能
    queue<int, std::list<int>> 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<deque>
#include<iostream>
using namespace std;

void test_deque()
{
	deque<int> 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<int> dp;
iterator it = dp.begin();
while(it!=dp.end())
{
    *it;
    ++it;
}

尝试分析遍历deque时的迭代器遍历的操作：

deque的优缺点

1、双端队列，他很适合头插头删，尾插尾删，他去做stack和queue的默认适配容器很适合

2、双端队列中间插入删除数据，非常麻烦。效率不高

实现方案1：挪动整体数据

实现方案2：插入或者删除数据时，只挪动当前buff数据，搞一个变量记录每个buff数组的大小，但是这样会导致每个buff数组大小不一致，此时随机访问就会麻烦：

3、deque是一种折中(妥协)方案设计，不够极致，随机访问效率不及vector，任意位置插入删除不及list