# 栈的应用：经典算法与例题解析
[[栈]]
在理解了栈的基本概念和实现后，我们来看看它在算法中的一些经典应用。栈的“后进先出”（LIFO）特性使其成为处理具有递归结构或需要“暂存”和“回溯”状态问题的理想工具。
算法一：括号匹配
1. 算法思想
这是栈最经典的应用之一。给定一个只包含 (), [], {} 的字符串，判断字符串中的括号是否有效匹配。
有效匹配的条件：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
解决思路：
- 遍历字符串，当遇到一个左括号时，我们将其压入栈中。这相当于“暂存”了这个待匹配的左括号。
- 当遇到一个右括号时，我们需要检查栈顶的左括号是否与之匹配：
- 如果此时栈是空的，说明没有左括号与之对应，直接判定为无效。
- 如果栈不为空，取出（
pop）栈顶元素，判断这两个括号是否是同一类型。
- 如果是，则匹配成功，继续遍历。
- 如果不是，则判定为无效。
- 遍历完整个字符串后，如果栈是空的，说明所有左括号都找到了对应的右括号，判定为有效。如果栈不为空，则说明有未被匹配的左括号，判定为无效。
2. 例题讲解：有效的括号 (LeetCode 20)
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例：
- 输入:
s = "()[]{}"
输出: true
输入: s = "(]"
输出: false
输入: s = "{[]}"
- 输出:
true
代码实现 (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
| #include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
class Solution {
public:
bool isValid(std::string s) {
if (s.length() % 2 != 0) {
return false;
}
std::stack<char> st;
std::unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char ch : s) {
if (pairs.count(ch)) {
if (st.empty() || st.top() != pairs[ch]) {
return false;
}
st.pop();
} else {
st.push(ch);
}
}
return st.empty();
}
};
int main() {
Solution sol;
std::string test1 = "()[]{}";
std::string test2 = "([)]";
std::string test3 = "{[]}";
std::cout << test1 << " is " << (sol.isValid(test1) ? "valid" : "invalid") << std::endl;
std::cout << test2 << " is " << (sol.isValid(test2) ? "valid" : "invalid") << std::endl;
std::cout << test3 << " is " << (sol.isValid(test3) ? "valid" : "invalid") << std::endl;
return 0;
}
|
算法二：最小栈
1. 算法思想
设计一个栈，除了支持常规的 push, pop, top 操作外，还需支持一个 getMin 操作，该操作能在常数时间 O(1) 内返回栈中最小的元素。
解决思路： 直接遍历整个栈来找最小值是不可取的，因为这会使 getMin 的时间复杂度变为 O(n)。
为了实现 O(1) 的查询，我们需要用空间换时间。一个常见的方法是使用两个栈：
data_stack：一个普通的数据栈，用于存储所有压入的元素，行为和普通栈完全一样。
min_stack：一个辅助的最小栈。这个栈的栈顶永远保存着当前 data_stack 中所有元素的最小值。
操作规则：
push(x):
data_stack 正常压入 x。
对于 min_stack：
- 如果
min_stack 为空，或者 x 小于等于 min_stack 的栈顶元素，则也将 x 压入 min_stack。这表示一个新的最小值出现了。
pop():
getMin():
2. 例题讲解：最小栈 (LeetCode 155)
题目描述： 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
代码实现 (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
| #include <iostream>
#include <stack>
#include <algorithm>
class MinStack {
private:
std::stack<int> data_stack;
std::stack<int> min_stack;
public:
MinStack() {
}
void push(int val) {
data_stack.push(val);
if (min_stack.empty() || val <= min_stack.top()) {
min_stack.push(val);
}
}
void pop() {
if (data_stack.top() == min_stack.top()) {
min_stack.pop();
}
data_stack.pop();
}
int top() {
return data_stack.top();
}
int getMin() {
return min_stack.top();
}
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
std::cout << "Min element: " << minStack.getMin() << std::endl;
minStack.pop();
std::cout << "Top element: " << minStack.top() << std::endl;
std::cout << "Min element: " << minStack.getMin() << std::endl;
return 0;
}
|
算法三：用栈实现队列
1. 算法思想
我们知道，栈是 LIFO (后进先出)，而队列是 FIFO (先进先出)。如何用两个栈来模拟队列的行为呢？
解决思路： 使用两个栈，一个作为输入栈 (in_stack)，一个作为输出栈 (out_stack)。
入队 (Enqueue / push):
出队 (Dequeue / pop):
2. 例题讲解：用栈实现队列 (LeetCode 232)
题目描述： 请你仅使用两个栈实现一个先入先出（FIFO）队列。队列应当支持一般队列的所有功能（push, pop, peek, empty）。
代码实现 (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
| #include <iostream>
#include <stack>
class MyQueue {
private:
std::stack<int> in_stack;
std::stack<int> out_stack;
void transfer() {
while (!in_stack.empty()) {
out_stack.push(in_stack.top());
in_stack.pop();
}
}
public:
MyQueue() {
}
void push(int x) {
in_stack.push(x);
}
int pop() {
if (out_stack.empty()) {
transfer();
}
int val = out_stack.top();
out_stack.pop();
return val;
}
int peek() {
if (out_stack.empty()) {
transfer();
}
return out_stack.top();
}
bool empty() {
return in_stack.empty() && out_stack.empty();
}
};
int main() {
MyQueue myQueue;
myQueue.push(1);
myQueue.push(2);
std::cout << "Peek: " << myQueue.peek() << std::endl;
std::cout << "Pop: " << myQueue.pop() << std::endl;
std::cout << "Is empty? " << (myQueue.empty() ? "Yes" : "No") << std::endl;
return 0;
}
|
