栈与队列小结

一、理论基础

1.队列是先进先出，栈是先进后出

2.栈和队列是STL（C++标准库）里面的两个数据结构。栈提供push和pop等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器。

3.栈是以底层容器完成所有的工作，对外提供统一的接口，所以STL往往不被归类为容器，而被归类为container adpter（容器适配器）

4.我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。deque是一个双向队列，只要封住其中一段，只开通另一端就可以实现栈的逻辑

5.SGI STL中队列实现底层实现缺省情况下一样使用deque实现的

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

所以STL队列也不被归类为容器，也是容器适配器

二、力扣题目

1、使用栈实现队列的下列操作：

push(x) 将一个元素放入队列的尾部

pop() 从队列首部移除元素

peek() 返回队列首部的元素

empty() 返回队列是否为空

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路：

使用栈模拟队列的行为，如果禁用一个栈是不行的，所以需要两个栈一个输入栈，一个输出栈

如果进栈和出栈都为空，说明模拟的队列为空了

class MyQueue {
public:stack<int> stIn;stack<int> stOut;/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）if (stOut.empty()) {// 从stIn导入数据直到stIn为空while(!stIn.empty()) {stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {int res = this->pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() && stOut.empty();}
};

2、用队列实现栈

使用队列实现栈的下列操作：

• push(x) 元素入栈

• pop() 移除栈顶元素 (没有返回值)

• top() 获取栈顶元素

• empty() 返回栈是否为空

• front() 返回队头元素 （可以接收返回值！）

• back() 返回队尾元素

思路：

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2倒回到que1

class MyStack {
public:queue<int> que1;queue<int> que2; // 辅助队列，用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que1.size();size--;while (size--) { // 将que1 导入que2，但要留下最后一个元素que2.push(que1.front());que1.pop();}int result = que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 = que2;            // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};

3、有效的括号

题目：给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。

• 左括号必须以正确的顺序闭合。

• 注意空字符串可被认为是有效字符串。

思路：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符了

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

当字符串遍历完之后，栈是空的，就说明全都匹配了

技巧：在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶是否相等，比左括号先入栈代码实现简单的多

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求stack<char> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') st.push(')');else if (s[i] == '{') st.push('}');else if (s[i] == '[') st.push(']');// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return falseelse if (st.empty() || st.top() != s[i]) return false;else st.pop(); // st.top() 与 s[i]相等，栈弹出元素}// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return truereturn st.empty();}
};

4、删除字符串中的所有相邻重复项

给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除他们。

在S上反复执行删除操作，直到无法删除，在完成所有重复项删除操作后返回最终的字符串

示例：

• 输入："abbaca"

• 输出："ca"

• 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

思路：用栈来存放遍历过的元素，当遍历当前的这个元素的时候，去栈里面看一下我们是不是遍历过相同数值的相邻元素，如果相同，则弹出元素，当栈为空或者元素不相同，则将此元素压入栈中，最后再将栈中元素放到result字符串汇总输出

class Solution {
public:string removeDuplicates(string S) {stack<char> st;for (char s : S) {if (st.empty() || s != st.top()) {  //栈为空或者元素不相等st.push(s);} else {st.pop(); // s 与 st.top()相等的情况}}string result = "";while (!st.empty()) { // 将栈中元素放到result字符串汇总result += st.top();st.pop();//别忘了弹出栈顶的元素}reverse (result.begin(), result.end()); //因为从栈中弹出的元素是倒序的 此时字符串需要反转一下return result;}
};

5、逆波兰表达式求值

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面，平常所使用表达式是中缀表达式

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式，请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。

• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。

• 两个整数之间的除法总是 向零截断 。

• 表达式中不含除零运算。

• 输入是一个根据逆波兰表示法表示的算术表达式。

• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

特点：

• 去掉括号后表达式无歧义

• 适合用栈操作运算，遇到数字则入栈；遇到运算符则取出栈顶两个数字进行运算，并将结果压入栈中

思路：逆波兰表达式相当于二叉树中的后序遍历，大家可以把运算符当作中间节点，按照后序遍历左右中的顺序

如果数组中元素检测到是运算符时，此时要先找到需要运算的两个数字元素，且这两个数字相邻且位于栈顶，取出两个数字进行运算

class Solution {
public:int evalRPN(vector<string>& tokens) {// 力扣修改了后台测试数据，需要用longlongstack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));//检测到是数字则压入栈中}}int result = st.top();  //因为栈中只剩最后一个元素st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）return result;}
};

其中stoll()函数是将字符串强制转换成long long int型

6、滑动窗口最大值

题目：给定一个数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到滑动窗口的k个数字。滑动窗口每次只向右移动一位，返回滑动窗口的最大值

class Solution {
private:class MyQueue { //单调队列（从大到小）public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};