基础数据结构 2.3 栈的应用与实现

1. 栈的定义

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。它的基本操作包括入栈（push）、出栈（pop）和查看栈顶元素（peek）。栈的特点是只能在一端进行插入和删除操作，这使得栈在某些特定场景下非常有用。

1.1 栈的基本操作

入栈（Push）：将一个元素添加到栈顶。
出栈（Pop）：移除并返回栈顶元素。
查看栈顶元素（Peek）：返回栈顶元素但不移除它。
判断栈是否为空（IsEmpty）：检查栈中是否有元素。

2. 栈的实现

栈可以通过数组或链表来实现。下面分别介绍这两种实现方式。

2.1 数组实现栈

使用数组实现栈的基本思路是维护一个数组和一个指向栈顶的指针。以下是用 Python 实现的栈类：

class ArrayStack:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1  # 栈顶指针

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, item):
        if self.is_full():
            raise Exception("Stack is full")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        item = self.stack[self.top]
        self.stack[self.top] = None  # 清空栈顶元素
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.stack[self.top]

    def size(self):
        return self.top + 1

    def __str__(self):
        return str(self.stack[:self.top + 1])

优点

快速访问：由于数组的随机访问特性，栈顶元素的访问速度非常快。
内存局部性：数组在内存中是连续存储的，具有良好的缓存性能。

缺点

固定大小：栈的大小在创建时就固定，可能会导致空间浪费或溢出。
扩展性差：如果需要动态扩展，必须手动实现扩展逻辑。

2.2 链表实现栈

链表实现栈的基本思路是使用节点（Node）来存储数据，每个节点指向下一个节点。以下是用 Python 实现的链表栈类：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.top = None  # 栈顶指针
        self.size = 0

    def is_empty(self):
        return self.top is None

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self.size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        item = self.top.data
        self.top = self.top.next
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.top.data

    def get_size(self):
        return self.size

    def __str__(self):
        current = self.top
        elements = []
        while current:
            elements.append(current.data)
            current = current.next
        return str(elements)

优点

动态大小：链表可以根据需要动态扩展，避免了固定大小的限制。
内存利用率高：只在需要时分配内存，避免了空间浪费。

缺点

额外的内存开销：每个节点需要额外存储指针，导致内存开销增加。
访问速度较慢：由于链表的非连续存储，访问速度可能不如数组快。

3. 栈的应用

栈在计算机科学中有广泛的应用，以下是一些常见的应用场景：

3.1 表达式求值

栈常用于求解中缀表达式、后缀表达式（逆波兰表示法）等。通过使用栈，可以有效地处理运算符的优先级和括号匹配。

示例代码：后缀表达式求值

def evaluate_postfix(expression):
    stack = ArrayStack()
    for token in expression.split():
        if token.isdigit():
            stack.push(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(a / b)
    return stack.pop()

# 示例
expression = "3 4 + 2 * 7 /"
result = evaluate_postfix(expression)
print(f"后缀表达式 {expression} 的结果是: {result}")

3.2 括号匹配

在编译器中，栈用于检查括号是否匹配。通过遍历字符串，将左括号入栈，遇到右括号时出栈进行匹配。

示例代码：括号匹配

def is_balanced(expression):
    stack = ArrayStack()
    brackets = {')': '(', '}': '{', ']': '['}
    for char in expression:
        if char in brackets.values():
            stack.push(char)
        elif char in brackets.keys():
            if stack.is_empty() or stack.pop() != brackets[char]:
                return False
    return stack.is_empty()

# 示例
expression = "{[()()]}"
print(f"表达式 {expression} 是否平衡: {is_balanced(expression)}")

3.3 深度优先搜索（DFS）

在图的遍历中，栈可以用于实现深度优先搜索。通过使用栈来存储待访问的节点，可以有效地实现图的遍历。

示例代码：深度优先搜索

def dfs(graph, start):
    stack = ArrayStack()
    visited = set()
    stack.push(start)

    while not stack.is_empty():
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            for neighbor in graph[vertex]:
                stack.push(neighbor)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("深度优先搜索结果:")
dfs(graph, 'A')

4. 注意事项

栈溢出：在使用数组实现栈时，需注意栈的大小限制，避免栈溢出。
内存管理：在链表实现中，需注意内存的分配和释放，避免内存泄漏。
异常处理：在出栈和查看栈顶元素时，需处理栈空的异常情况。
性能考虑：在选择栈的实现方式时，需根据具体应用场景考虑性能和内存使用。

5. 总结

栈是一种重要的基础数据结构，具有简单而强大的特性。通过理解栈的基本操作及其实现方式，我们可以在多种场景中有效地应用栈。无论是表达式求值、括号匹配还是图的遍历，栈都能提供优雅的解决方案。希望本教程能帮助你深入理解栈的应用与实现。