6 线性数据结构之栈

在前一篇中，我们学习了线性数据结构之链表。今天，我们将探讨另一个重要的线性数据结构——栈。栈是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构，它在很多算法和程序中都发挥着重要的作用。

栈的基本概念

栈可以被看作是一系列元素的集合，其操作仅限于一端。入栈（push）操作用于添加新元素，而出栈（pop）操作用于移除并返回栈顶的元素。栈的顶部是最近被添加的元素，底部是最早添加的元素。

栈的操作

栈主要有以下几种基本操作：

1. 入栈（Push）：将一个元素加入栈的顶部。
2. 出栈（Pop）：移除并返回栈顶的元素。
3. 查看栈顶元素（Peek/Top）：返回栈顶的元素，但不移除它。
4. 判断栈是否为空（IsEmpty）：检查栈是否为空。

栈的应用

栈在计算机科学中有很多实际应用，例如：

• 函数调用管理：在程序运行时，调用函数时会将函数信息压入栈中，函数返回后则从栈中弹出相关信息。
• 表达式求值：在计算数学表达式（如后缀表达式）时，可以使用栈来存储操作数。
• 撤销操作：许多应用程序会使用栈来实现撤销操作，例如文本编辑器的删除和重做。

栈的实现

我们可以使用数组或链表来实现栈。在这里，我们将使用 Python 的 列表 来实现一个简单的栈。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def size(self):
        return len(self.items)

# 示例使用
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出 3
print(stack.peek()) # 输出 2
print(stack.size()) # 输出 2

在上面的代码中，我们定义了一个 Stack 类，其中：

• __init__ 方法用于初始化一个空栈。
• is_empty 方法检查栈是否为空。
• push 方法将元素压入栈顶。
• pop 方法从栈顶弹出元素。
• peek 方法返回栈顶元素。
• size 方法返回栈中元素的数量。

栈的优缺点

优点

• 操作简单：栈的操作相对简单，易于实现。
• 内存管理：利用系统调用栈自动管理内存并提供递归能力。

缺点

• 容量有限：如果使用固定大小的数组实现栈，容易出现栈溢出的问题。
• 只能访问栈顶元素：无法随机访问栈中的元素，只能访问栈顶的元素。

小结

今天我们学习了线性数据结构之栈的基本概念、操作及其实现。同时，还了解了栈在实际中的应用场景，并使用代码实现了一个基本的栈。栈作为一种重要的数据结构，与链表的概念相辅相成，接下来我们将在下一篇中深入探讨线性数据结构之队列的内容。希望你能在后续阅读中，学到更多的知识！