先进后出
栈是一个 LIFO 数据结构。通常,插入操作在栈中被称作入栈 push 。与队列类似,总是在堆栈的 末尾添加一个新元素。但是,删除操作,退栈 pop ,将始终删除队列中相对于它的最后一个元素。
栈的实现
动态数组 实现栈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
class MyStack {
private:
vector<int> data; // store elements
public:
/** Insert an element into the stack. */
void push(int x) {
data.push_back(x);
}
/** Checks whether the queue is empty or not. */
bool isEmpty() {
return data.empty();
}
/** Get the top item from the queue. */
int top() {
return data.back();
}
/** Delete an element from the queue. Return true if the operation is successful. */
bool pop() {
if (isEmpty()) {
return false;
}
data.pop_back();
return true;
}
};
int main() {
MyStack s;
s.push(1);
s.push(2);
s.push(3);
for (int i = 0; i < 4; ++i) {
if (!s.isEmpty()) {
cout << s.top() << endl;
}
cout << (s.pop() ? "true" : "false") << endl;
}
}
栈和深度优先搜索
在我们到达最深的结点之后,我们只会回溯并尝试另一条路径。
当到达终点时,并不一定是最短路径。
我们首先将根结点推入到栈中;当我们回溯时,我们将从栈中 弹出最深的结点,这实际上是推入到栈中的最后一个结点。
1. 递归实现
1 | /* |
当我们递归地实现 DFS 时,似乎不需要使用任何栈。但实际上,我们使用的是由系统提供的 隐式栈,也称为调用栈(Call Stack)。
每个元素都需要固定的空间。栈的大小正好是 DFS 的深度。因此,在最坏的情况下,维护系统栈需要 O(h),其中 h 是 DFS 的最大深度。在计算空间复杂度时,永远不要忘记考虑系统栈。
2. 栈实现
如果递归的深度太高,会产生堆栈溢出。 在这种情况下,可以使用 BFS,或使用显式栈实现 DFS。
1 | /* |
该逻辑与递归解决方案完全相同。 但我们使用 while 循环和 栈 来模拟递归期间的 系统调用栈。