C++stack和queue模拟实现以及deque的介绍

1.stack

1.1stack的介绍

stack的文档介绍

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

1.2stack的使用

stack的接口现在看起来对于前面已经学过string，vector，list已经是很简单的了。

这里就不再对接口进行详细介绍。来写几道题对stack的接口有更熟悉的使用。

最小栈

思路一
这道题大部分人的思路，可能是这样的，再申请一个变量，每次都和插入的数据进行比较，如果比新插入的数据小就更新。

思路二
申请两个栈，其中一个栈记录，插入最小的元素。

会初始化的，那为什么会初始化呢？
这个成员变量会走初始化列表，对内置类型不处理，对自定义类型调用它的构造函数。
那如果把这个Minstack()删掉，成员变量会不会初始化？
同样也是会的，系统默认生成的构造函数，对内置类型不处理，除非给内置类型缺省值，对自定义类型调用它的构造函数。

因此这里也没有析构函数。

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        _min.push(val);
        //这里必须判空在前面，否则_count.top()会报错
        if(_count.empty() || _count.top() >= _min.top())
            _count.push(val);
    }
    
    void pop() {
        if(_count.top() == _min.top())
            _count.pop();
        _min.pop();
    }
    
    int top() {
        return _min.top();
    }
    
    int getMin() {
        return _count.top();
    }

    stack<int> _min;
    stack<int> _count;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

JZ31 栈的压入、弹出序列

思路
这道题穷举是不可能的，
其实可以这样想，第一个是入栈序列，第二个是出栈序列，如果第一个的出栈序列可以和第二个出栈序列互相匹配，那不就是true了吗，不能匹配，return false；

这里就不再演示不匹配了，

写法1，返回条件以push1，pop1来进行判断。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> _st;
        int i=0,j=0;
        _st.push(pushV[i++]);
        while(1)
        {
            //相等就出栈
            if(!_st.empty() && _st.top() == popV[j])
            {
                _st.pop();
                ++j;
                if(j == popV.size())
                    return true;
            }
            //不相等/栈为空就入栈
            else 
            {
                if(i == pushV.size() && j != popV.size() )
                    return false;
                _st.push(pushV[i++]);
            }

        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

写法2，返回条件以循环结构，st栈是否为空来判断

class Solution {
public:

    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> _st;
        size_t pop1=0;
        for(size_t push1=0;push1<pushV.size();++push1)
        {
            _st.push(pushV[push1]);
            while(!_st.empty() &&_st.top() == popV[pop1])
            {
                _st.pop();
                ++pop1;
            }
        }
        return _st.empty();
    }
};         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

150. 逆波兰表达式求值

逆波兰表达式，就在后缀表达式。

后缀转中缀思路
遇见操作数直接入栈，遇到运算符"+“，”-“，”*“，”/“，出栈，先出的是右操作数，这是因为”-“，”/"，要分左右。然后把结果入栈。最后栈中剩下的元素就是最终结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> _st;

        for(auto& str : tokens)
        {
            if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                int right=_st.top();
                _st.pop();
                int 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;
                    default:
                    break;
                }
            }
            else
            {
                //字符串转为int,stoi函数
                _st.push(stoi(str));
            }
        }
        return _st.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

这里介绍一下C++把字符串变成各种类型的接口；

前面是把后缀变成中缀，这里再提供把中缀变成后缀的思路。

申请一个存放运算符的栈
1.操作数直接输出
2.栈空时，碰见运算符直接入栈，栈不空时，碰见运算符，需要外面运算符和栈顶的运算符比较。如果栈里面运算符优先级比外面的高或者相等，就一直出栈，直到栈空或者碰见优先级低于外面的运算符就停止。这个时候再把外面的运算符入栈。当遍历完之后，再把栈里面所有运算符依次出栈。

这个有兴趣可以写一下。
232. 用栈实现队列

提示：用两个栈。一个入栈，一个出栈。

2.queue

2.1queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   empty：检测队列是否为空
   size：返回队列中有效元素的个数
   front：返回队头元素的引用
   back：返回队尾元素的引用
   push_back：在队列尾部入队列
   pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2.2queue的使用

关于队列的题这里就不再讲解。
有兴趣可以写下面这道题
225. 用队列实现栈

提示：用两个队列。

3.容器适配器

3.1什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

其实到目前为止，我们已经接触了两种设计模式：
1.适配器模式
把已有的东西封装起来，转换出你想要的东西。
2.迭代器模式
不暴露底层实现细节，封装后提供统一的方式访问容器。

如果我们还是按照以往的想法，实现一个栈（如果是顺序栈），肯定是申请一个变长数组，一个size，一个capacity，再写一些成员函数。

template<class T>
class stack
{
public:
	//成员函数
private:
	T* _a;
	size_t _size;
	size_t _capacity;
};
1
2
3
4
5
6
7
8
9
10

但是stack，queue都是适配器模式，我们可以不再自己写，而是可以用已有的东西封装起来，转换成自己想要的东西。

4.stack模拟实现

既然stack即可以用vector/list封装，因此模板我们给两个参数

#include
#include
#include
using namespace std;

namespace bit
{
	template<class T,class container>
	class stack
	{
	public:
		//自定义类型也可以不写构造
		stack() {};

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

发现stack的模拟实现就是这么简单。。。

stack用list封装也是没有问题。

有人可能会说不对啊，我自己使用的stack可没有你传参这么麻烦

这里解决方法给第二个容器参数一个缺省值就行了。

5.queue的模拟实现

namespace bit
{
	template<class T,class container=list<T>>
	class queue
	{
	public:
		queue() {};

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& front()
		{
			return _con.front();
		}

		const T& back()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

6.deque（双端队列）

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

但是deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。

可能有人看了官方库发现，我们这里和库里面使用的容器不一样。

为什么库里面用的是deque（双端队列）

这里就不得不提到vector，list的缺点了

deque兼容了vector和list的优点

看起来deque这么好，那我们就只学这一种容器不就好了，还要学vector和list干吗，但是到现在我们还是在学vector和list，从这一方面就证明了，deque并不是那么完美。

deque底层结构
deque底层是由多个buffer数组，以及一个中控（指针数组）所组成。

deque这样的底层，才会即支持下标随机访问，又支持尾插尾删头插头删。

deque的缺点:

1.下标随机访问。
要算下标在第几个buffer，在这个buffer种第几个位置，因此下标随机访问有一定的时间消耗，不如vector快。

2.中间插入和删除。
也有一定的时间消耗，相比list中间插入删除不够极致，没有list快。

虽然deque有这些缺点，但是队友栈和队列是够用了。

那什么地方可以用deque（双端队列）呢？

中间插入和删除少，头尾插入删除多，偶尔下标随机访问。