1. 栈的定义
栈（Stack）是一种后进先出（Last In First Out，LIFO）的数据结构。我们把栈中允许插入和删除的一端称为栈顶，另一端称为栈底。当栈中没有数据元素时，称为空栈。
栈中的元素离底端越近，代表其在栈中的时间越长，因此栈的底端具有非常重要的意义。最新添加的元素将被最先移除。
2. 栈的基本操作
栈的基本操作有：
- 入栈（push）：将一个数据元素压入栈顶。
- 出栈（pop）：将栈顶的数据元素弹出。
- 查看栈顶元素（peek）：查看栈顶的数据元素。
- 判断栈是否为空（is_empty）：判断栈是否为空。
- 获取栈的大小（size）：获取栈的大小。
3. 使用 Python 实现栈
3.1 顺序栈
在 Python 中我们可以借助列表 list 来实现栈的顺序存储结构。这种采用顺序存储结构的栈也被称为顺序栈
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
| class Stack:
def __init__(self):
self.stack = []
def push(self, item):
"""入栈操作"""
self.stack.append(item)
def pop(self):
"""出栈操作"""
if self.is_empty():
raise Exception("Stack is empty")
return self.stack.pop()
def peek(self):
"""查看栈顶元素"""
if self.is_empty():
raise Exception("Stack is empty")
return self.stack[-1]
def is_empty(self):
"""判断栈是否为空"""
return len(self.stack) == 0
def size(self):
"""获取栈的大小"""
return len(self.stack)
|
3.2 链栈
链栈是一种采用链式存储结构的栈。在 Python 中我们可以借助链表来实现链栈。
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
| class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkStack:
def __init__(self):
self.head = None
def push(self, val):
"""入栈操作"""
curr = Node(val)
curr.next = self.head
self.head = curr
def pop(self):
"""出栈操作"""
if self.is_empty():
raise Exception("Stack is empty")
curr = self.head
self.head = self.head.next
return curr.val
def is_empty(self):
"""判断栈是否为空"""
return self.head is None
def size(self):
"""获取栈的大小"""
count = 0
curr = self.head
while curr:
count += 1
curr = curr.next
return count
def peek(self):
"""查看栈顶元素"""
if self.is_empty():
raise Exception("Stack is empty")
return self.head.val
|
4. 栈的应用场景
栈在计算机科学中有广泛的应用，主要包括以下几个方面：
- 函数调用：在函数调用过程中，系统会使用栈来存储函数调用的信息，包括函数的参数、返回地址等。
- 表达式求值：在表达式求值过程中，系统会使用栈来存储操作数和运算符。
- 深度优先搜索（DFS）：在深度优先搜索过程中，系统会使用栈来存储节点信息。
- 回溯算法：在回溯算法中，系统会使用栈来存储状态信息。
- 浏览器历史记录：在浏览器中，我们可以使用栈来存储用户访问过的页面。
5. 栈的练习
5.1 括号匹配问题
描述： 定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s
要求： 判断字符串 s 是否有效（即括号是否匹配）。
示例：
1
2
3
4
5
6
| >>> s = "()[]{}"
>>> print(is_valid(s))
True
>>> s = "([)]"
>>> print(is_valid(s))
False
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def is_valid(s: str) -> bool:
"""判断括号是否匹配"""
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in '({[':
stack.append(char)
else:
if (
stack and stack[-1] == mapping[char]
):
stack.pop()
else:
return False
return not stack
|
5.2 最小栈问题
描述： 设计一个栈，支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
要求： 实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素 val 推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例：
1
2
3
4
5
6
7
8
9
10
11
| >>> minStack = MinStack()
>>> minStack.push(-2)
>>> minStack.push(0)
>>> minStack.push(-3)
>>> print(minStack.getMin())
-3
>>> minStack.pop()
>>> print(minStack.top())
0
>>> print(minStack.getMin())
-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
| class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
if self.stack:
return self.stack[-1]
else:
raise Exception("Stack is empty")
def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
else:
raise Exception("Stack is empty")
|