【代码随想录】栈与队列

发表于 更新于 分类于 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 13 分钟

栈与队列理论基础

栈是后进先出，队列是先进先出。

在C++中，栈与队列是底层容器双端队列的适配器。详细可参看博客中关于STL源码的解析。

用栈实现队列

题目：232

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

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

思路：栈1用于输入，当需要弹出元素时将所有元素入栈2，这样栈1的栈底元素就是栈2的栈顶元素。

push(x)：将元素入栈1

pop()：如果栈2不为空，则出栈2；否则将栈1所有元素逐一入栈2，然后再出栈2

peek()：如果栈2不为空，则top栈2；否则将栈1所有元素逐一入栈2，然后top栈2；

empty()：只有当栈1和栈2都为空时才为空。

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
44
45
46
47
48
49
50
51
class MyQueue {
private:
    stack<int> st1, st2;

public:
    // 构造函数
    MyQueue() {

    }
    
    void push(int x) {
        st1.push(x); // 栈1作为输入栈
    }
    
    int pop() {
        // 如果栈2是空的就将栈1所有元素入栈2
        if (st2.empty()) {
            while (!st1.empty()) {
                st2.push(st1.top());
                st1.pop();
            }
        }
        // 栈2作为输出栈
        int result = st2.top();
        st2.pop();

        return result;
    }
    
    int peek() {
        // 先弹出元素
        int result = pop();
        // 再将元素放回栈顶
        st2.push(result);

        return result;
    }
    
    bool empty() {
        return st1.empty() && st2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

收获：peek用到了pop函数，即实现了代码复用。

在代码开发时一定要注意复用，忌讳实现类似的函数，即把一段代码复制粘贴稍微修改。

使用队列实现栈

题目：225

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路1：哪个队列不为空就入哪个队列（如果都为空随便入）；出队就是将有元素的队列的前面所有元素入另一个队列，最后一个元素为出队元素

push(x)：入一个不为空的队列

pop()：要取最后一个入队的元素就需要将所有的元素全都取出这个队列，将前面元素全部入另一个队列，然后取最后一个元素

top()：先用pop，再push

empty()：两个队列都为空则为空

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class MyStack {
private:
    queue<int> que1, que2;
public:
    MyStack() {

    }
    
    void push(int x) {
        if (!que1.empty()) que1.push(x);
        else que2.push(x); 
    }
    
    int pop() {
        queue<int> *filled_que, *empty_que;
        if (!que1.empty()) {
            filled_que = &que1;
            empty_que = &que2;
        } else {
            filled_que = &que2;
            empty_que = &que1;
        }

        // 将有元素的队列前面元素都入空队列
        // 只保留最后队尾元素
        int result;
        while (filled_que->size() > 1) {
            result = filled_que->front();
            filled_que->pop();
            empty_que->push(result);
        }

        result = filled_que->front();
        filled_que->pop();

        return result;
    }
    
    int top() {
        int result = pop();
        push(result);
        
        return result;
    }
    
    bool empty() {
        return que1.empty() && que2.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

收获：作者提供使用一个队列的思路，即每次出队时候都再次入队。

有效的括号

题目：20.有效的括号

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

有效字符串需满足：

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

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

3.每个右括号都有一个对应的相同类型的左括号。

思路：匹配时需要将左括号保存起来，出现右括号进行匹配时，需要与最后保存的左括号进行匹配。因此左括号的存储应该是后进先出，即使用栈结构。

遍历所有字符，遇到左括号就入栈，遇到右括号就进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c== '{') {
                st.push(c);
            } else {
                char top_c;
                if (c == ')') top_c = '(';
                else if (c == ']') top_c = '[';
                else top_c = '{';

                // 判断栈顶元素是否匹配
                if (st.empty() || top_c != st.top()) return false;
                st.pop();
            }
        }
        if (!st.empty()) return false;
        return true;
    }
};

时间复杂度O(n)；空间复杂度O(n)

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

题目：1047

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

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

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

思路：如果从前向后遍历字符串，那么当出现字符串时，与先前记录的最后的字符进行匹配，也就是后进先出。因此使用栈结构。

遍历所有字符，如果栈空就入栈；否则新元素与栈顶元素进行比较，如果相同则两个元素就都删除，否则就入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st; // 栈用于保存历史字符
        // 遍历所有字符
        for (char c : s) {
            // 如果栈空就直接入栈
            if (st.empty() || st.top() != c) {
                st.push(c);
            } else {
                st.pop();
            }
        }
        // 保存结果
        string result(st.size(), ' ');
        for (int i = st.size() - 1; i >= 0; i--) {
            result[i] = st.top();
            st.pop();
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

收获：1.string的构造函数，并且string的长度不计算空字符

2.递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）

逆波兰表达式求值

题目：150

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

逆波兰式就是数字都在前面，符号在后面。

思路：使用栈存储数据，当遇到运算符时就出栈两个元素并将结果入栈。

这里需要处理的是取出的结果是两个字符表示数字，参与运算需要整数类型。如果不使用库函数就是与字符’0’和’9’进行比较。如果使用库函数就是stoi。

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
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;

        for (string s : tokens) {
            // 如果字符串是运算符
            // 一起判断结构更加清晰
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                // 错误检查
                if (st.size() < 2) exit(-1);

                int rhs = st.top(); st.pop();
                int lhs = st.top(); st.pop();
                if (s == "+") 
                    st.push(lhs + rhs);
                else if (s == "-") 
                    st.push(lhs - rhs);
                else if (s == "*")
                    st.push(lhs * rhs);
                else 
                    st.push(lhs / rhs);

            } else {
                // 字符串转换为整型，时间复杂度O(n)
                int temp = stoi(s);
                st.push(temp);
            }
        } // end for s in tokens

        return st.top();
    }
};

时间复杂度O(n)；空间复杂度O(n)

收获：1.逆波兰表达式相当于是二叉树中的后序遍历。 可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。

2.stoi、stol、stoll函数：在头文件string中，将字符串转换为int、long、long long类型的整数。

int stoi(const std::string& str, std::size_t* pos = 0, int base = 10);

注意默认base是10。

滑动窗口最大值

题目：239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

思路：分析可知，每次向后移动窗口时，需要移除第一个元素和添加一个新元素，如果只记录最大元素，那么当移除元素就是最大元素时，就需要重新选择。所以保存时，不能仅仅只保存最大元素。

此外，如果对K个元素进行排序，那么需要移除元素时就无法知道移除元素的位置，也不能简答对K个元素进行排序。

分析可知，每次向后移动，只删除一个元素，最差的情况是这个元素刚还是最大值，那么就需要知道之前K个元素的第二大值，因此最多只需保留较大值即可。

因此维持这样一个队列：（push）队列中的元素仍然按照数组中顺序进，但是每次进的时候只有当元素大于或者等于队尾元素时才能进，并且如果队尾更小，则弹出队尾，直到队尾元素大于或者等于当前元素。

（pop）出队的时候，也就是删除元素时，如果删除的元素不是队首，那么就不需要弹出队首。

这样的队列中队首始终是K个元素的最大值，后面的元素依次小于等于前面的元素。

这样，每次窗口移动时先尝试弹出元素，队列中一定是有元素的，因为后面还有添加一个元素操作；添加元素时，如果队列为空则直接进队（保证结束两个操作时至少有一个元素），否则就按照上面的比较规则进行入队（保证结束时至少有一个元素）。

每次循环结束只需要记录队首即可。

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
44
45
46
47
class Solution {
private:
    class MaxQueue {
    private:
        deque<int> de;
    public:
        // 使用默认构造和析构函数
        // 修改规则的push
        void push(int value) {
            while (!de.empty() && de.back() < value) de.pop_back();
            de.push_back(value);
        }
        // 修改规则的pop
        void pop(int value) {
            if (value == de.front()) de.pop_front();
        }
        // 取队首元素
        int front() {
            return de.front();
        }
    };


public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MaxQueue que; // 创建一个单调队列，最大值在前面
        int n = nums.size();
        if (n < k) exit(-1);
        // 首先记录前k个元素的最大值
        for (int i = 0; i < k; i++) que.push(nums[i]);
        vector<int> result;
        result.push_back(que.front());
        
        // 模拟滑动窗口移动
        for (int last_start = 0, new_end = k; new_end < n; last_start++, new_end++) {
            // 弹出前K个元素的第一个值
            que.pop(nums[last_start]);
            // 添加当前K个元素的最后一个值
            que.push(nums[new_end]);

            // 记录当前K个值的最大值
            result.push_back(que.front());
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

收获：

1.作者给出的思路是：并不需要保持所有元素，而是保持一个单调队列，即还是按照原始顺序，但是保持最大元素在队列头，并且按照单调递减的顺序保留数据，删除其他元素。这样保持一个单调队列，push和pop方法改为：

1.pop(value):如果要弹出的元素不是头元素，那么队列不做任何操作

2.push(value):入队时与队尾元素相比，如果队尾更小，就从队尾弹出元素，保持是一个单调的状态。并且从队尾进页保持了原始顺序。

这个队列是按照原始顺序进队和出队的，只是由于最大值不同队列内元素个数不同。

2.了解双端队列dequeue

前 K 个高频元素

题目：347.前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

  • 输入: nums = [1,1,1,2,2,3], k = 2
  • 输出: [1,2]

示例 2:

  • 输入: nums = [1], k = 1
  • 输出: [1]

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。

思路：首先遍历数组记录每个数组出现的频率，使用map，时间复杂度O(n)；接着对(数字，频率)根据频率排序(时间复杂度O(nlogn))；最后取出前k个即可。

这里根据频率排序，实际上存在一个优先级队列，实际上就是堆的概念，堆中每添加一个元素，就会进行一次堆结构调整，这个调整的时间复杂度是O(log(n))，这里的n是堆的大小，因为调整的操作实际上是遍历一个（近似有序，按照堆的规则）二叉树，因此最多会进行log次的比较。

然后这里的思路是保持一个小顶堆，当堆的大小超过k时，就弹出队首元素，否则就一直入堆。

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
class Solution {
public:
    class Compare {
    public:
        bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) {
            return lhs.second > rhs.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map; // 记录数字和对应的频率
        // 遍历数组记录频率
        for (int x : nums) map[x]++;

        // 创建一个优先级队列，小顶堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pri_que;
        // 遍历map，逐渐将元素加入小顶堆
        for (auto it = map.begin(); it != map.end(); ++it) {
            pri_que.push(*it);
            if (pri_que.size() > k) pri_que.pop();
        }

        vector<int> result;
        while (!pri_que.empty()) {
            result.push_back(pri_que.top().first);
            pri_que.pop();
        }

        return result;
    }
};

时间复杂度O(nlogk)；空间复杂度O(k)

收获：1.优先级队列表示大顶堆、小顶堆

2.使用小顶堆删除最小的，保留下来的就是k个最大的。

总结

在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。

使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。

我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。

通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。