---

栈（Stack）的数组与链表实现 📚

在计算机科学中，栈是一种基本且强大的数据结构，遵循后进先出（LIFO） 的原则。它就像一叠盘子：你只能从顶部添加或移除盘子。栈在编程中无处不在，从函数调用、表达式求值到浏览器历史记录。本文将深入探讨栈的两种常见实现方式：使用数组和链表。我会提供详细的代码示例、性能分析，并通过 mermaid 图表可视化其操作。让我们开始吧！🚀

什么是栈？🤔

栈是一种线性数据结构，支持两种主要操作：

• Push: 将元素添加到栈顶。
• Pop: 从栈顶移除元素。

其他常见操作包括 peek（查看栈顶元素而不移除它）和 isEmpty（检查栈是否为空）。栈常用于需要临时存储和检索数据的场景，例如在递归算法、括号匹配或撤销功能中。

想了解更多基础概念，可以参考这个外部资源 on data structures（一个权威的计算机科学教育网站）。

数组实现 🧩

使用数组实现栈简单直观。数组提供连续的存储空间，允许通过索引快速访问元素。以下是使用 Python 的代码示例。

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity  # 栈的最大容量
        self.stack = [None] * capacity  # 初始化数组
        self.top = -1  # 栈顶指针，初始为-1表示空栈

    def push(self, item):
        if self.top == self.capacity - 1:
            raise Exception("Stack Overflow! 😱")  # 栈已满
        self.top += 1
        self.stack[self.top] = item
        print(f"Pushed {item} to stack. ✅")

    def pop(self):
        if self.is_empty():
            raise Exception("Stack Underflow! 😵")  # 栈为空
        item = self.stack[self.top]
        self.top -= 1
        print(f"Popped {item} from stack. ❌")
        return item

    def peek(self):
        if self.is_empty():
            return None
        return self.stack[self.top]

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

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

# 示例使用
stack = ArrayStack(3)
stack.push(10)
stack.push(20)
stack.push(30)
print("Top element:", stack.peek())  # 输出 30
stack.pop()
print("Stack size:", stack.size())   # 输出 2

数组实现的优点是简单和高速的访问（O(1) 时间复杂度的 push 和 pop），但缺点是有固定容量，可能导致栈溢出。🔒

下面是一个 mermaid 图表，展示了数组栈的 push 操作流程：

链表实现 🔗

链表实现使用动态内存分配，避免了数组的固定大小限制。每个节点包含数据和指向下一个节点的指针。以下是使用 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 push(self, item):
        new_node = Node(item)
        new_node.next = self.top  # 新节点指向当前栈顶
        self.top = new_node       # 更新栈顶为新节点
        self.size += 1
        print(f"Pushed {item} to stack. ✅")

    def pop(self):
        if self.is_empty():
            raise Exception("Stack Underflow! 😵")
        item = self.top.data
        self.top = self.top.next  # 移动栈顶到下一个节点
        self.size -= 1
        print(f"Popped {item} from stack. ❌")
        return item

    def peek(self):
        if self.is_empty():
            return None
        return self.top.data

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

    def get_size(self):
        return self.size

# 示例使用
ll_stack = LinkedListStack()
ll_stack.push(5)
ll_stack.push(15)
ll_stack.push(25)
print("Top element:", ll_stack.peek())  # 输出 25
ll_stack.pop()
print("Stack size:", ll_stack.get_size())  # 输出 2

链表实现的优点是动态大小（无溢出风险，除非内存耗尽），但每个操作需要额外内存用于节点指针，可能稍慢于数组。🔄

参考这个外部文章 on linked lists 来更深入理解链表结构。

下面是一个 mermaid 图表，可视化链表栈的结构 after push 操作：

性能比较 ⚡

两种实现各有优劣：

• 数组栈: 更快的内存访问，但大小固定。适合已知最大大小的场景。
• 链表栈: 动态扩展，但每个操作有额外开销。适合大小变化大的应用。

在大多数语言中，数组实现更常见，因为硬件缓存友好。例如，在 Java 的 Stack 类就是用数组实现的。你可以在这个外部性能分析指南查看更多数据结构比较。

实际应用案例 🌍

栈在现实中应用广泛：

• 浏览器历史: 后退按钮使用栈来存储访问的页面。
• 表达式求值: 编译器用栈处理括号和运算符优先级。
• 递归管理: 函数调用在内存中通过栈帧管理。

尝试在你下一个项目中实现一个栈来解决这些问题！💡

结论 🎉

栈是一个简单但强大的工具，数组和链表实现提供了灵活的选择。数组适合性能关键且大小固定的情况，而链表适合动态需求。掌握两者将帮助你在编程中做出更好的设计决策。继续探索和实践吧！如果你对更多数据结构感兴趣，可以访问这个综合教程网站。

Happy coding! 😊