跳转至

8、栈和队列的应用介绍

1、栈

​ 栈（Stack）是一种具有后入先出（LIFO）特性的数据结构。它类似于现实生活中的堆叠物体，最新放入的物体在顶部，而最先放入的物体在底部。栈的操作只能在栈顶进行，包括入栈（push）、出栈（pop）、查看栈顶元素（top）和判断栈是否为空（empty）。

常见的应用场景包括函数调用栈、表达式求值、深度优先搜索等。

​ 以下是使用C++实现栈的代码示例：

C++
 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
#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> myStack;

    // 入栈操作
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);

    // 查看栈顶元素
    cout << "Top: " << myStack.top() << endl;  // 输出：Top: 3

    // 出栈操作
    myStack.pop();

    // 再次查看栈顶元素
    cout << "Top: " << myStack.top() << endl;  // 输出：Top: 2

    // 判断栈是否为空
    cout << "Empty: " << (myStack.empty() ? "true" : "false") << endl;  // 输出：Empty: false

    return 0;
}
​ 以上代码使用C++ STL中的stack模板类来实现栈的功能。通过push将元素入栈，通过pop将栈顶元素出栈，通过top查看栈顶元素，通过empty判断栈是否为空。

2、队列

​ 队列（Queue）是一种具有先入先出（FIFO）特性的数据结构。它类似于现实生活中排队等待的场景，最早进入队列的元素首先被处理，而最后进入队列的元素则需要等待前面的元素处理完毕后才能被处理。

​ 队列的基本操作包括入队（enqueue）、出队（dequeue）、查询队首元素（front）和判断队列是否为空（empty）。

​ 常见的应用场景包括任务调度、消息传递、广度优先搜索等。

​ 队列可以使用数组或链表来实现。数组实现的队列使用循环缓冲区来解决数据搬移的问题，链表实现的队列通过指针来连接节点。

队列的时间复杂度如下：

​ 入队（enqueue）操作的时间复杂度为O(1)。 ​ 出队（dequeue）操作的时间复杂度为O(1)。 ​ 查询队首元素（front）操作的时间复杂度为O(1)。 ​ 判断队列是否为空（empty）的时间复杂度为O(1)。

以下是使用C++ STL中的queue模板类来实现队列的代码示例：

C++
 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
#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> myQueue;

    // 入队操作
    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    // 查询队首元素
    cout << "Front: " << myQueue.front() << endl;  // 输出：Front: 1

    // 出队操作
    myQueue.pop();

    // 再次查询队首元素
    cout << "Front: " << myQueue.front() << endl;  // 输出：Front: 2

    // 判断队列是否为空
    cout << "Empty: " << (myQueue.empty() ? "true" : "false") << endl;  // 输出：Empty: false

    return 0;
}

3、使用队列模拟栈

使用两个队列来模拟栈的原理是通过一个"主队列"和一个"辅助队列"来实现栈的后入先出（LIFO）特性。具体步骤如下：

  1. 当需要入栈时，直接将元素插入"主队列"。

  2. 当需要出栈时，先将"主队列"中的元素依次移动到"辅助队列"，直到只剩下一个元素。然后将最后一个元素弹出作为出栈元素。

  3. 在以上操作过程中，如果需要查询栈顶元素，则直接返回"主队列"的队尾元素即可。

下面是用C++实现的代码示例：

C++
 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
59
#include <iostream>
#include <queue>

using namespace std;

class MyStack {
private:
    queue<int> mainQueue;   // 主队列
    queue<int> tempQueue;   // 辅助队列

public:
    void push(int x) {
        mainQueue.push(x);  // 直接将元素插入主队列
    }

    int pop() {
        while (mainQueue.size() > 1) {
            tempQueue.push(mainQueue.front());  // 将主队列中的元素移动到辅助队列，除了队尾元素
            mainQueue.pop();
        }

        int top = mainQueue.front();  // 弹出队尾元素作为出栈元素
        mainQueue.pop();

        swap(mainQueue, tempQueue);  // 交换主队列和辅助队列，使主队列恢复正常顺序

        return top;
    }

    int top() {
        return mainQueue.back();  // 返回主队列的队尾元素作为栈顶元素
    }

    bool empty() {
        return mainQueue.empty();  // 栈为空的条件是主队列为空
    }
};

int main() {
    MyStack s;

    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.top() << endl;  // 输出：3

    s.pop();

    cout << s.top() << endl;  // 输出：2

    s.push(4);

    cout << s.pop() << endl;   // 输出：4

    cout << s.empty() << endl; // 输出：0

    return 0;
}

4、使用栈模拟队列

使用两个栈来模拟队列的原理是通过一个"输入栈"和一个"输出栈"来实现队列的先入先出（FIFO）特性。具体步骤如下：

  1. 当需要入队时，将元素直接压入"输入栈"。

  2. 当需要出队时，先判断"输出栈"是否为空，如果不为空，则直接从"输出栈"弹出栈顶元素；如果为空，则将"输入栈"中的所有元素依次弹出并压入"输出栈"，然后再从"输出栈"弹出栈顶元素。

  3. 在以上操作过程中，如果需要查询队列的头部元素（队首），则同样需要进行第二步的判断和操作。

下面是用C++实现的代码示例：

C++
 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
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <stack>

using namespace std;

class MyQueue {
private:
    stack<int> inputStack;  // 输入栈
    stack<int> outputStack; // 输出栈

public:
    void push(int x) {
        inputStack.push(x);  // 直接将元素压入输入栈
    }

    int pop() {
        if (outputStack.empty()) {
            // 如果输出栈为空，则将输入栈中的元素全部转移到输出栈
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }

        int front = outputStack.top();  // 弹出输出栈的栈顶元素作为出队元素
        outputStack.pop();
        return front;
    }

    int peek() {
        if (outputStack.empty()) {
            // 如果输出栈为空，则将输入栈中的元素全部转移到输出栈
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }

        return outputStack.top();  // 返回输出栈的栈顶元素作为队首元素
    }

    bool empty() {
        return inputStack.empty() && outputStack.empty();  // 队列为空的条件是输入栈和输出栈都为空
    }
};

int main() {
    MyQueue q;

    q.push(1);
    q.push(2);
    q.push(3);

    cout << q.peek() << endl;  // 输出：1

    q.pop();

    cout << q.peek() << endl;  // 输出：2

    q.push(4);

    cout << q.pop() << endl;   // 输出：2

    cout << q.empty() << endl; // 输出：0

    return 0;
}

5、单调栈

单调栈（Monotonic Stack）是一种特殊的栈数据结构，它具有以下特点：

1.栈内元素保持单调递增或单调递减的顺序。 2.当要入栈一个元素时，会先将栈内所有不满足单调性的元素弹出，以保持栈的单调性。 3.单调栈常用于解决与单调性相关的问题，例如寻找下一个更大元素、下一个更小元素等。通过维护一个单调递增栈或单调递减栈，可以高效地找到符合特定条件的元素。

以下是使用单调栈解决寻找下一个更大元素的问题的示例：

C++
 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
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<int> findNextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);  // 初始化结果向量为-1

    stack<int> monStack;  // 单调递增栈，存储元素的索引

    for (int i = 0; i < n; i++) {
        while (!monStack.empty() && nums[i] > nums[monStack.top()]) {
            // 如果当前元素比栈顶元素大，则更新栈顶元素对应的结果为当前元素
            result[monStack.top()] = nums[i];
            monStack.pop();
        }
        monStack.push(i);
    }

    return result;
}

int main() {
    vector<int> nums = {2, 1, 3, 4, 5};

    vector<int> nextGreater = findNextGreaterElement(nums);

    cout << "Next Greater Elements: ";
    for (int i = 0; i < nextGreater.size(); i++) {
        cout << nextGreater[i] << " ";
    }
    cout << endl;

    return 0;
}

​ 以上代码使用单调递增栈找到每个元素的下一个更大元素。对于给定的数组 [2, 1, 3, 4, 5]，程序输出的结果为：[3, 3, 4, 5, -1]，表示每个元素的下一个更大元素。

​ 在实现中，通过维护一个栈monStack，遍历数组nums。如果当前元素比栈顶元素大，则更新栈顶元素对应的结果为当前元素，并将栈顶元素出栈，直到栈为空或当前元素不再大于栈顶元素。最后，若栈中还有剩余元素，则它们没有下一个更大元素，结果初始化为-1。

单调栈的其他应用：

1.柱状图中最大矩形面积：给定一个柱状图，要求找到其中的最大矩形面积。使用单调递增栈可以高效地解决这个问题，通过遍历柱状图中的每个柱子，维护一个单调递增栈来记录柱子的索引，并计算以每个柱子为高度所能构成的最大矩形面积。

2.下一个更小元素：给定一个数组，要求找到每个元素的下一个更小元素。使用单调递减栈可以高效地解决这个问题，从右到左遍历数组，维护一个单调递减栈来记录尚未找到下一个更小元素的索引。

3.删除字符串中的重复字符：给定一个字符串，要求删除其中的重复字符，使得每个字符只出现一次并保持相对顺序不变。使用单调递减栈可以高效地解决这个问题，遍历字符串中的每个字符，维护一个单调递减栈来记录尚未删除的字符。

4.表达式求值：给定一个包含加号、减号、乘号、除号和括号的表达式，要求计算其值。使用单调递增栈可以高效地解决这个问题，通过转换表达式为逆波兰表达式，并利用栈进行运算。具体代码如下：

C++
  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
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <stack>
#include <string>

using namespace std;

int evaluateExpression(const string& expression) {
    stack<int> numStack;  // 存储操作数的栈
    stack<char> opStack;  // 存储运算符的栈

    for (int i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (isdigit(c)) {
            // 如果是数字字符，则读取完整的数字并入栈
            int num = 0;
            while (i < expression.length() && isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            numStack.push(num);
            i--;  // 回退一个字符，以便正确处理下一个字符
        } else if (c == '(') {
            // 左括号直接入栈
            opStack.push(c);
        } else if (c == ')') {
            // 右括号执行计算，直到遇到左括号
            while (!opStack.empty() && opStack.top() != '(') {
                int b = numStack.top();
                numStack.pop();
                int a = numStack.top();
                numStack.pop();

                char op = opStack.top();
                opStack.pop();

                int result = 0;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                numStack.push(result);
            }
            opStack.pop();  // 弹出左括号
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            // 遇到运算符，将其与栈顶的运算符进行比较优先级
            while (!opStack.empty() && opStack.top() != '(' &&
                   ((c == '*' || c == '/') ||
                    (c == '+' || c == '-') && (opStack.top() == '*' || opStack.top() == '/'))) {
                int b = numStack.top();
                numStack.pop();
                int a = numStack.top();
                numStack.pop();

                char op = opStack.top();
                opStack.pop();

                int result = 0;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                numStack.push(result);
            }
            opStack.push(c);  // 当前运算符入栈
        }
    }

    // 执行剩余的计算
    while (!opStack.empty()) {
        int b = numStack.top();
        numStack.pop();
        int a = numStack.top();
        numStack.pop();

        char op = opStack.top();
        opStack.pop();

        int result = 0;
        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
        }
        numStack.push(result);
    }

    return numStack.top();
}

int main() {
    string expression = "((2+3)*4)-(5/2)";
    int result = evaluateExpression(expression);

    cout << "Expression: " << expression << endl;
    cout << "Result: " << result << endl;

    return 0;
}

6、单调队列

​ 单调队列（Monotonic Queue），也称为双向队列（Deque），是一种特殊的队列数据结构，具有以下特点：

1.队列中元素保持单调递增或单调递减的顺序。 2.具有在队首和队尾进行插入和删除操作的能力。

​ 单调队列常用于解决与单调性相关的问题，特别是滑动窗口问题，例如找到滑动窗口中的最大值或最小值。通过维护一个单调递增队列或单调递减队列，可以高效地找到满足特定条件的元素。

以下是使用单调队列解决滑动窗口中的最大值问题的示例：

C++
 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
#include <iostream>
#include <deque>
#include <vector>

using namespace std;

vector<int> findMaxSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;

    deque<int> monoQueue;  // 单调递减队列，存储元素的索引

    for (int i = 0; i < n; i++) {
        while (!monoQueue.empty() && nums[i] >= nums[monoQueue.back()]) {
            // 如果当前元素大于等于队尾元素，则删除队尾元素
            monoQueue.pop_back();
        }
        monoQueue.push_back(i);

        // 窗口移动时，判断队首元素是否还在窗口内
        if (i - monoQueue.front() >= k) {
            monoQueue.pop_front();
        }

        // 当窗口大小达到k时，将队首元素加入结果
        if (i >= k - 1) {
            result.push_back(nums[monoQueue.front()]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    vector<int> maxSlidingWindow = findMaxSlidingWindow(nums, k);

    cout << "Max Sliding Window: ";
    for (int i = 0; i < maxSlidingWindow.size(); i++) {
        cout << maxSlidingWindow[i] << " ";
    }
    cout << endl;

    return 0;
}

​ 以上代码使用单调递减队列找到滑动窗口中的最大值。对于给定的数组 [1, 3, -1, -3, 5, 3, 6, 7] 和窗口大小k=3，程序输出的结果为：[3, 3, 5, 5, 6, 7]，表示每个滑动窗口的最大值。

​ 在实现中，通过维护一个双向队列monoQueue，遍历数组nums。如果当前元素大于等于队尾元素，则删除队尾元素，以保持队列的单调性。然后，判断队首元素是否还在窗口内，并将满足条件的队首元素加入结果。最后，返回结果即可。

单调队列的其他应用：

1.温度计算问题：给定一系列天气温度的序列，要求计算每一天之后的第一个比当天温度更高的日期。使用单调递减队列可以解决这个问题，从左到右遍历温度序列，维护一个单调递减队列，以记录未找到更高温度的日期。

2.股票价格问题：给定一系列股票价格，要求计算每一天之后的第一个较高价格出现的日期。通过维护一个单调递减队列来解决这个问题，将每一天的价格与队尾元素进行比较，将较小的价格出队，并记录出队日期。

3.寻找数组中的局部极值：对于给定的数组，要求找到所有的局部最大或最小值。通过维护一个单调递增队列或单调递减队列，可以高效地找到所有的极值。

4.最大连续子数组和问题：给定一个整数数组，要求找到和最大的连续子数组。使用单调队列可以在线性时间复杂度内解决这个问题，通过维护一个单调递增队列来记录当前的最大连续子数组和。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用