跳到主要内容

栈的实现方式

栈（Stack）是一种常见的线性数据结构，遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后入栈的元素会最先出栈。栈的操作主要包括入栈（Push）和出栈（Pop），以及查看栈顶元素（Peek）。

栈的实现方式主要有两种：基于数组和基于链表。下面我们将详细介绍这两种实现方式，并通过代码示例和实际案例帮助你更好地理解。

1. 基于数组的栈实现​

数组是一种连续的内存结构，适合实现栈。我们可以通过一个数组和一个指向栈顶的指针来实现栈。

实现步骤：​

  1. 定义一个数组来存储栈中的元素。
  2. 使用一个变量（如 top）来记录栈顶的位置。
  3. 入栈时，将元素添加到数组的 top 位置，并将 top 加 1。
  4. 出栈时，返回 top 位置的元素，并将 top 减 1。

代码示例：​

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

    def push(self, item):
        if self.top == self.capacity - 1:
            raise Exception("栈已满")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.top == -1:
            raise Exception("栈为空")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.top == -1:
            raise Exception("栈为空")
        return self.stack[self.top]

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

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

示例运行：​

python
stack = ArrayStack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出: 3
print(stack.peek())  # 输出: 2
备注

基于数组的栈实现简单高效，但需要预先分配固定大小的内存空间。如果栈的大小不确定，可能会导致空间浪费或栈溢出。

2. 基于链表的栈实现​

链表是一种动态数据结构，适合实现栈。我们可以通过链表的头部作为栈顶来实现栈。

实现步骤：​

  1. 定义一个链表节点类，每个节点存储数据和指向下一个节点的指针。
  2. 使用一个指针（如 head）来指向栈顶节点。
  3. 入栈时，将新节点插入链表头部，并更新 head。
  4. 出栈时，返回 head 节点的数据，并将 head 指向下一个节点。

代码示例：​

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

class LinkedListStack:
    def __init__(self):
        self.head = None

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            raise Exception("栈为空")
        item = self.head.data
        self.head = self.head.next
        return item

    def peek(self):
        if self.head is None:
            raise Exception("栈为空")
        return self.head.data

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

示例运行：​

python
stack = LinkedListStack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())  # 输出: 30
print(stack.peek())  # 输出: 20
提示

基于链表的栈实现可以动态调整大小，避免了数组实现中的空间限制问题，但每次操作需要额外的指针操作，性能略低于数组实现。

3. 实际应用场景​

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

  1. 函数调用栈：程序执行时，函数调用和返回的顺序通过栈来管理。
  2. 表达式求值：栈可以用于解析和计算数学表达式，例如中缀表达式转后缀表达式。
  3. 撤销操作：文本编辑器中的撤销功能通常使用栈来存储操作历史。
  4. 浏览器历史记录：浏览器的前进和后退功能可以通过栈实现。

4. 总结​

栈是一种简单但功能强大的数据结构，适用于许多场景。通过数组和链表两种实现方式，我们可以根据具体需求选择合适的方法。数组实现适合固定大小的栈，而链表实现适合动态调整大小的栈。

5. 附加资源与练习​

练习：​

  1. 实现一个栈，支持在常数时间内返回栈中的最小值。
  2. 使用栈实现一个简单的括号匹配检查器。

资源：​

通过学习和实践，你将能够熟练掌握栈的实现方式及其应用场景。继续加油！