python算法学习之栈

栈#

栈是一种 Last In First Out（LIFO）的线数据结构，它遵循后进先出的原则，即新添加的元素会排在栈的顶部，而访问的元素会排在栈的底部。栈可以用数组或链表实现。栈的实现可以使用数组或链表，栈的核心操作：

入栈（Push）：添加元素到栈顶
出栈（Pop）：移除栈顶元素
查看栈顶（Peek/Top）：查看但不移除栈顶元素
判断空（isEmpty）：检查栈是否为空

栈就像一叠盘子：

你只能从最上面取盘子（后进先出）
新盘子只能放在最上面

例如

数组实现（顺序栈） - 使用列表

1
stack = []           # 底部       顶部
2
stack.append(1)      # [1]
3
stack.append(2)      # [1, 2]      ← 顶部
4
stack.append(3)      # [1, 2, 3]   ← 顶部
5
stack.pop()          # 移除3 → [1, 2]

链表实现（链式栈） - 使用链表节点

1
class Node:
2
    def __init__(self, value):
3
        self.value = value
4
        self.next = None

二、栈的实现方式#

1. 数组实现#

1
class ArrayStack:
2
    """基于数组的栈实现"""
3
    def __init__(self, capacity=10):
4
        self.capacity = capacity
5
        self.stack = [None] * capacity  # 预分配固定大小
6
        self.top = -1  # 栈顶指针，-1表示空栈
7

8
    def __str__(self):
9
        if self.is_empty():
10
            return "Stack: []"
11
        return f"Stack: {self.stack[:self.top + 1]}"
12

13
    def is_empty(self):
14
        """判断栈是否为空"""
15
        return self.top == -1
16

17
    def is_full(self):
18
        """判断栈是否已满"""
19
        return self.top == self.capacity - 1
20

21
    def push(self, value):
22
        """入栈操作 - O(1)"""
23
        if self.is_full():
24
            self._resize()  # 动态扩容
25
        self.top += 1
26
        self.stack[self.top] = value
27

28
    def pop(self):
29
        """出栈操作 - O(1)"""
30
        if self.is_empty():
31
            raise IndexError("Pop from empty stack")
32
        value = self.stack[self.top]
33
        self.stack[self.top] = None  # 可选：帮助垃圾回收
34
        self.top -= 1
35
        return value
36

37
    def peek(self):
38
        """查看栈顶元素 - O(1)"""
39
        if self.is_empty():
40
            raise IndexError("Peek from empty stack")
41
        return self.stack[self.top]
42

43
    def size(self):
44
        """获取栈的大小 - O(1)"""
45
        return self.top + 1
46

47
    def _resize(self):
48
        """动态扩容 - O(n)"""
49
        self.capacity *= 2
50
        new_stack = [None] * self.capacity
51
        for i in range(self.top + 1):
52
            new_stack[i] = self.stack[i]
53
        self.stack = new_stack

测试数组栈

1
arr_stack = ArrayStack(3)
2
arr_stack.push(1)
3
arr_stack.push(2)
4
arr_stack.push(3)
5
print(arr_stack)  # Stack: [1, 2, 3]
6
print("栈顶:", arr_stack.peek())  # 3
7
print("出栈:", arr_stack.pop())   # 3
8
print(arr_stack)  # Stack: [1, 2]

2. 链表实现#

1
class Node:
2
    """链表节点"""
3
    def __init__(self, value):
4
        self.value = value
5
        self.next = None
6

7
class LinkedListStack:
8
    """基于链表的栈实现"""
9
    def __init__(self):
10
        self.top = None  # 栈顶节点
11
        self._size = 0
12

13
    def __str__(self):
14
        values = []
15
        current = self.top
16
        while current:
17
            values.append(str(current.value))
18
            current = current.next
19
        return " → ".join(reversed(values)) + " → None" if values else "Empty Stack"
20

21
    def is_empty(self):
22
        return self.top is None
23

24
    def push(self, value):
25
        """入栈 - O(1)"""
26
        new_node = Node(value)
27
        new_node.next = self.top  # 新节点指向原栈顶
28
        self.top = new_node       # 更新栈顶
29
        self._size += 1
30

31
    def pop(self):
32
        """出栈 - O(1)"""
33
        if self.is_empty():
34
            raise IndexError("Pop from empty stack")
35
        value = self.top.value
36
        self.top = self.top.next  # 更新栈顶
37
        self._size -= 1
38
        return value
39

40
    def peek(self):
41
        """查看栈顶 - O(1)"""
42
        if self.is_empty():
43
            raise IndexError("Peek from empty stack")
44
        return self.top.value
45

46
    def size(self):
47
        return self._size

测试链表栈

1
ll_stack = LinkedListStack()
2
ll_stack.push(1)
3
ll_stack.push(2)
4
ll_stack.push(3)
5
print("链表栈:", ll_stack)  # 1 → 2 → 3 → None
6
print("栈顶:", ll_stack.peek())  # 3
7
print("出栈:", ll_stack.pop())   # 3
8
print("链表栈:", ll_stack)  # 1 → 2 → None

三、栈的应用#

1. 括号匹配#

1
def is_valid_parentheses(s: str) -> bool:
2
    """LeetCode 20: 有效的括号"""
3
    stack = []
4
    mapping = {')': '(', ']': '[', '}': '{'}
5

6
    for char in s:
7
        if char in mapping.values():  # 左括号
8
            stack.append(char)
9
        elif char in mapping.keys():  # 右括号
10
            if not stack or stack[-1] != mapping[char]:
11
                return False
12
            stack.pop()
13
        else:
14
            continue  # 忽略其他字符
15

16
    return not stack  # 栈空则所有括号匹配

测试

1
test_cases = [
2
    ("()", True),
3
    ("()[]{}", True),
4
    ("(]", False),
5
    ("([)]", False),
6
    ("{[]}", True),
7
    ]
8

9
for s, expected in test_cases:
10
    result = is_valid_parentheses(s)
11
    print(f"'{s}': {result} (预期: {expected})")

2. 表达式求值#

1
def evaluate_expression(expression: str) -> float:
2
    """计算表达式值（支持 + - * /）"""
3
    def apply_operator(operators, values):
4
        op = operators.pop()
5
        right = values.pop()
6
        left = values.pop()
7
        if op == '+':
8
            values.append(left + right)
9
        elif op == '-':
10
            values.append(left - right)
11
        elif op == '*':
12
            values.append(left * right)
13
        elif op == '/':
14
            values.append(left / right)
15

16
    def precedence(op):
17
        if op in ('+', '-'):
18
            return 1
19
        if op in ('*', '/'):
20
            return 2
21
        return 0
22

23
    operators = []
24
    values = []
25
    i = 0
26

27
    while i < len(expression):
28
        # 跳过空格
29
        if expression[i] == ' ':
30
            i += 1
31
            continue
32

33
        # 处理数字
34
        if expression[i].isdigit():
35
            j = i
36
            while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
37
                j += 1
38
            values.append(float(expression[i:j]))
39
            i = j
40

41
        # 处理左括号
42
        elif expression[i] == '(':
43
            operators.append('(')
44
            i += 1
45

46
        # 处理右括号
47
        elif expression[i] == ')':
48
            while operators and operators[-1] != '(':
49
                apply_operator(operators, values)
50
            operators.pop()  # 移除 '('
51
            i += 1
52

53
        # 处理运算符
54
        else:
55
            while (operators and operators[-1] != '(' and
56
                   precedence(operators[-1]) >= precedence(expression[i])):
57
                apply_operator(operators, values)
58
            operators.append(expression[i])
59
            i += 1
60

61
    # 应用剩余运算符
62
    while operators:
63
        apply_operator(operators, values)
64

65
    return values[-1] if values else 0

测试

1
print("3 + 5 * 2 =", evaluate_expression("3 + 5 * 2"))  # 13.0
2
print("(3 + 5) * 2 =", evaluate_expression("(3 + 5) * 2"))  # 16.0

CodeTailor

栈#

二、栈的实现方式#

1. 数组实现#

2. 链表实现#

三、栈的应用#

1. 括号匹配#

2. 表达式求值#