前言

前言：刷「栈和队列」高频面试题。

文章目录

• • 前言
  • 一. 基础回顾
  • • 1. 栈
    • • 1）结构
      • 2）定义
      • 3）题型
    • 2. 队列
    • • 1）结构
      • 2）定义
  • 二. 高频面试题
  • • 1. 例题
    • • 例题1：LeetCode 20 有效的括号
      • • 1）题目链接
        • 2）算法思路
        • 3）源码剖析
        • 4）时间复杂度
      • 例题2：LeetCode 155. 最小栈
      • • 1）题目链接
        • 2）算法思路
        • 3）源码剖析
        • 4）时间复杂度
      • 例题3：：LeetCode 225 用队列实现栈
      • • 2）算法思路
        • 3）源码剖析
    • 2. 习题
    • • 习题1：LeetCode 232 用栈实现队列
      • • 1）题目链接
        • 2）源码剖析
      • 习题2：LeetCode 150 逆波兰表达式
      • • 1）题目链接
        • 2）算法思路
        • 3）源码剖析

一. 基础回顾

详细介绍参考 06 讲： 栈和队列简析 （点击链接直达）

1. 栈

1）结构

栈类比羽毛球筒，具有后进先出的性质，只在 栈顶 进行相关操作。

2）定义

栈顶下标初始化为 0 表示栈空。

3）题型

• 栈的问题一般分类两类
  • 最近相关性问题：例如，有效的括号。
  • 前缀最小值：因为栈只能从尾部进出，栈中维护的是对前缀维护的信息，开一个新栈维护前缀信息。例如，最小栈。

2. 队列

1）结构

队列类比排队买票，具有先进先出的性质，在 队尾插入 元素，在 队头弹出 元素。

2）定义

队头下标为 0，队尾下标为 -1，表示队列为空。

二. 高频面试题

1. 例题

例题1：LeetCode 20 有效的括号

1）题目链接

原题链接：有效的括号（点击链接直达）

2）算法思路

• 明确不合法的情况：多左括号，左右括号不匹配，多右括号；
• 从前往后遍历字符串中的每个字符。
• 如果遇到左括号，将左括号压栈，继续往后遍历；
• 如果遇到右括号，判断当前遍历元素和栈顶元素是否匹配，如果匹配，将栈顶元素弹出，继续往后遍历，不匹配则不合法；
• 遍历完字符串，判断栈是否为空，如果栈为空则合法，否则不合法；

3）源码剖析

class Solution {
public:bool isValid(string s) {stack stack;													//（1）for (char c : s)													//（2）{if (c == '(' || c == '{' || c == '[') stack.push(c);			//（3）else {if (stack.size() && abs(c - stack.top()) <= 2) stack.pop();	//（4）else return false;											//（5）}}return stack.empty();												//（6）}
};

• （1）定义一个栈；
• （2）遍历字符串中的每个字符；
• （3）判断当前字符如果是左括号，则入栈；
• （4）如果当前字符是右括号，判断栈是否为空，判断当前字符和栈顶元素是否匹配（通过 ASCII 对照表，左括号和右括号绝对值相差 <= 2）；
• （5）如果此时栈为空则说明右括号多了，不合法。左括号和右括号绝对值相差 > 2 说明左右括号不匹配，不合法；
• （6）遍历完左右字符，判断栈是否为空。如果栈为空说明所有括号都匹配，返回 true，否则说明左括号多了，返回 false；

4）时间复杂度

        O(n)O(n)O(n)

例题2：LeetCode 155. 最小栈

1）题目链接

原题链接：最小栈（点击链接直达）

2）算法思路

• 明确栈的作用：不仅可以存储值，也可以存储一些额外信息，本题用栈来存前缀最小值；
• 开一个新栈存前缀最小值（原栈中当前元素为第 i 个，维护前 i 个数的最小值），全局最小值就是新栈的栈顶元素；
• 当原栈插入一个数时，新栈与当前栈顶元素取 min 然后插入新栈。原栈弹出一个数时，新栈同时也弹出一个数；
• 栈的实现用数组来模拟；

3）源码剖析

class MinStack {
public:vector preMin;													//（1）vector stk;													//（2）MinStack() {}void push(int val) {												preMin.push_back(stk.empty() ? val : min(val, preMin.back()));  //（3）stk.push_back(val);												//（4）}void pop() {preMin.pop_back();												//（5）stk.pop_back();													//（6）}	int top() {return stk.back();												//（7）}int getMin() {return preMin.back();											//（8）}
};

• （1）preMin 为新栈，用来维护前缀最小值；
• （2）stk 为原栈，用来维护原栈的一些信息；
• （3）新栈中插入元素，需要考虑初始边界情况，如果新栈为空，直接插入当前元素；否则和当前元素取最小值再插入；
• （4）原栈中插入元素；
• （5）新栈弹出元素；
• （6）原栈弹出元素；
• （7）返回栈顶元素；
• （8）返回原栈最小值；

4）时间复杂度

        O(1)O(1)O(1)

例题3：：LeetCode 225 用队列实现栈

原题链接：用队列实现栈（点击链接直达）

2）算法思路

• 队列： -> [ 3 2 1 ] ->，其中只能从红色箭头插入一个元素，从蓝色箭头弹出一个元素；
• 栈： -> / <- 3 2 1 ]，其中只能从绿色箭头插入或弹出一个元素；
• 压入：队列 a 中压入一个元素，队列和栈的实现相同。例如，压入元素 4   ->[4 3 2 1]；
• 弹出：弹出一个元素，如果按照栈的弹出方式应该将 4 弹出，而按队列的弹出方式应该将 1 弹出。如果要通过队列实现栈的弹出，应该先将 4 找到，然后将 4 弹出。实现方式是先将 1 2 3 先弹出，此时，需要一个缓存队列 b 存储 1 2 3，然后将 4 弹出。弹出之后，再将 1 2 3 放回到队列 a 中。
• 返回栈顶元素：同理和弹出一样，先将 4 找到，然后返回。注意：返回之后，需要将 4 弹出，然后压入队列 b 中，然后再将队列 b 中的 1 2 3 4 放回队列 a 中，目的是为了保证数据原有的顺序；
• 判空：判断队列 a 是否为空；

3）源码剖析

class MyStack {
public:queue a;  // 队列queue b;  // 缓存队列MyStack() {}void push(int x) {a.push(x);}int pop() {while (a.size() > 1) b.push(a.front()), a.pop();int t = a.front();a.pop();while (b.size()) a.push(b.front()), b.pop();return t;}int top() {while (a.size() > 1) b.push(a.front()), a.pop();int t = a.front();a.pop();b.push(t);while (b.size()) a.push(b.front()), b.pop();return t;}bool empty() {return a.empty();}
};

2. 习题

习题1：LeetCode 232 用栈实现队列

1）题目链接

原题链接：用栈实现队列（点击链接直达）

2）源码剖析

class MyQueue {
public:stack a, b;MyQueue() {}void push(int x) {a.push(x);}int pop() {while (a.size() > 1) b.push(a.top()), a.pop();auto t = a.top();a.pop();while (b.size()) a.push(b.top()), b.pop();return t;}int peek() {while (a.size() > 1) b.push(a.top()), a.pop();auto t = a.top();while (b.size()) a.push(b.top()), b.pop();return t;}bool empty() {return a.empty();}
};

习题2：LeetCode 150 逆波兰表达式

1）题目链接

原题链接：逆波兰表达式（点击链接直达）

2）算法思路

• 后缀表达式的优点是在作运算时不需要考虑括号和优先级；
• 不断地遍历，将字符加到栈中，如果遇到操作符，将栈顶的两个元素用这个操作符进行运算，将结果放回到栈中，最后栈顶元素就是最终的结果；
• 注意： 取整和下取整只对于负数而言是不同的。例如，−1.2-1.2−1.2 下取整是 −2-2−2，取整是 −1-1−1，C++ 中的除法是取整；

3）源码剖析

class Solution {
public:int evalRPN(vector& tokens) {stack stk;for (auto c : tokens) {if (c == "+" || c == "-" || c == "*" || c == "/") {  // 运算符int b = stk.top(); stk.pop();  // 先弹出的是 bint a = stk.top(); stk.pop();  // 后弹出的是 aif (c == "+") a = a + b;else if (c == "-") a = a - b;else if (c == "*") a = a * b;else a = a / b;stk.push(a); }else {  // 数stk.push(stoi(c));}}return stk.top();}
};