标题：C++初阶 | [十] stack 和 queue

摘要：stack OJ：最小栈、栈的弹出压入序列；queue OJ：二叉树的层序遍历(仅思路，带图解)、逆波兰表达式求值；deque，模拟实现 stack 和 queue

经过对 string、vector、list 的学习，stack 和 queue 上手起来就很快了，因此不再赘述，在使用上有疑问请查看文档。本文将会通过一些OJ题来进一步熟练 stack 和 queue.

1. stack/queue 与 vector/list

• stack/queue——容器适配器（不自己管理数据）

  

• vector/list——容器（自己直接管理数据）

  

•  stack/queue 与 vector/list 的成员函数的区别：
  stack/queue 没有 iterator，因为 stack 是先进后出，queue 是先进先出，不能随机遍历。

2. stack OJ

1）最小栈

155. 最小栈 - 力扣（LeetCode）

思路

我们很容易可以想到用一个变量来存储栈中最小的数据，然而，当pop掉的数据正好是最小数时，那么这个pop操作之后的栈中的最小数就不得而知了，因此，我们不仅要记录栈中数据的当前最小数，而是要记录历史最小数。这里，我们通过使用双栈来实现这个思路。

上述思路图解示例：

代码示例

class MinStack {
public:
    
    void push(int val) {
        st.push(val);
        if(min_st.empty() || val <= min_st.top())
            min_st.push(val);
    }
    
    void pop() {
        if(st.top() == min_st.top())
        {
            st.pop();
            min_st.pop();
        }    
        else
            st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
private:
    stack<int> st;
    stack<int> min_st;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2）栈的压入、弹出序列

JZ31 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

思路

按给定的入栈顺序模拟数据入栈，同时按给定的出栈顺序模拟数据出栈，最终栈中数据全部出完即为该出栈顺序合法。

注意：如下图，如果先判断再入栈这个过程会比较复杂，这里建议先入栈再判断。

代码示例

class Solution {
public:
	/**
	 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	 *
	 *
	 * @param pushV int整型vector
	 * @param popV int整型vector
	 * @return bool布尔型
	 */
	bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
		// write code here
		stack<int> st;
		size_t size = pushV.size();
		for (size_t pushi = 0, popi = 0; pushi < size; ++pushi)
		{
			st.push(pushV[pushi]);

			while (!st.empty() && st.top() == popV[popi])//要先判断是否为空才可以取top
			{
				st.pop();
				++popi;
			}

		}
		return st.empty();
	}
};

3. queue OJ

1）二叉树的层序遍历(仅思路，带图解)

• 思路一：双队列，队列_1 用于遍历二叉树，队列_2 用于记录节点对应的层数。

  

  如图，依次遍历，把遍历结果存储在队列中。当我们开始遍历，遍历到‘3’，记录此时层数为1；接着遍历‘3’的child节点，插入‘9’‘7’到队列中，记录此时的层数，即为上一层+1；如此循环。直到遍历完二叉树。

• 思路二：双队列，队列_1 用于存储 parent 节点，队列_2 用于存储 child 节点。

  

• 思路三：一个队列+一个变量，队列用于遍历二叉树，变量用于记录当前遍历到多少层。

  

2）逆波兰表达式求值

逆波兰表达式就是后缀表达式。逆波兰表达式求值就是后缀表达式的计算。

150. 逆波兰表达式求值 - 力扣（LeetCode）

后缀表达式的计算

• 中缀表达式：1 + 2 * 3
• 后缀表达式：1 2 3 * + （ps.后缀表达式是没有括号的，因为括号的作用是提高操作符的优先级，而后缀表达式的操作符顺序已经表现了优先级）

思路：遍历后缀表达式，遇到操作数入栈，遇到操作符就取栈顶两元素运算，运算结果再入栈，如此循环，直到遍历完后缀表达式。图例如下。

中缀表达式转后缀表达式(仅思路)

• 思路：遍历中缀表达式，遇到操作数输出；遇到操作符，如果 stack 为空，那么 push 操作符入栈，如果 stack 不为空，那么比较栈顶元素与该操作符的优先级，如果该操作符优先级更高，那么 push 操作符入栈，如果栈顶元素优先级更高或两者优先级相等，就 pop 栈顶元素。（ps.遇到括号处理成递归子问题）。

代码示例

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;
                }
            }
            else
            {
                st.push(stoi(str));

            }
        }
        return st.top();

    }
};

4. 模拟实现 stack

库里的实现 → std::stack 

template <class T, class Container = deque<T> > class stack;

1）deque(简单了解)

deque 是一个结合了vector 和 list 功能的容器，但也同时结合了 vector 和 list 的双重优点和缺点。（优点多而优势不高，缺点多而缺陷不深）

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

deque 和 vector 的效率比较（这个操作类似于 list 和 vector 的效率比较）
1.vector sort 的效率约为 deque 的 2倍；
2.通过把 deque 的数据拷贝到 vector 对其排序，都比直接用 deque 排序要快。（ps.通过这个操作我们可以侧面了解到数据拷贝的代价并不高）

sum.实际中 deque 并不常用，综合性比较强，但是优势又并不突出。

为什么选择deque作为stack和queue的底层默认容器：

stack是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可 以作为stack的底层容器，比如vector 和 list 都可以；queue是 先进先出 的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如list。但是STL中对stack和 queue 默认选择 deque 作为其底层容器，主要是因为：

1. stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在 stack 中元素增长时，deque 比 vector 的效率高(扩容时不需要搬移大量数据)；queue 中的元素增长 时，deque不仅效率高，而且内存使用率高。 结合了 deque 的优点，而完美的避开了其缺陷。

2）模拟实现

思路：本质就是复用别的容器的函数接口。注意后进先出的原则。

代码示例

namespace Btl
{
	template<class T, class Con = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}

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

		T& top()
		{
			return _c.back();
		}

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

		size_t size()const
		{
			return _c.size();
		}

		bool empty()const
		{
			return _c.empty();
		}

	private:
		Con _c;
	};
};

5. 模拟实现 queue

同 stack，注意是先进先出的原则。

namespace Btl
{
	template<class T, class Con = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}

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

		T& back()
		{
			return _c.back();
		}

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

		T& front()
		{
			return _c.front();
		}

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

		size_t size()const
		{
			return _c.size();
		}

		bool empty()const
		{
			return _c.empty();
		}

	private:
		Con _c;
	};

};

END