解密数据结构：栈的约束之美与应用实战

在后端架构设计中，我们经常需要处理各种各样的数据。数据结构入门是每一位工程师的必修课，而栈（Stack）作为一种基础但极其重要的数据结构，它所蕴含的“约束”思想，在实际应用中反而能爆发出强大的力量。例如，函数调用栈、浏览器的前进后退功能、以及表达式求值等，都离不开栈的巧妙运用。理解栈的特性，有助于我们更好地解决实际问题，提高代码质量，甚至优化系统性能。

栈的核心概念：LIFO

栈最核心的概念就是 LIFO (Last In First Out)，即后进先出。想象一下我们叠放盘子，最后放上去的盘子总是最先被拿走。 栈只有两种基本操作：

• 压栈（Push）: 将元素放入栈顶。
• 弹栈（Pop）: 从栈顶移除元素。

不允许直接访问栈中间的元素，只能操作栈顶，这就是栈的“约束”。这种约束看似限制了灵活性，但同时也简化了操作，降低了出错的概率，使栈在某些特定场景下表现出极高的效率。

栈的实现方式

栈可以使用数组或链表来实现。 使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。

顺序栈（数组实现）

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity # 栈的容量
        self.stack = [None] * capacity # 使用数组存储元素
        self.top = -1 # 栈顶指针，初始值为 -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 # 将栈顶元素置为 None，方便垃圾回收
        self.top -= 1 # 栈顶指针减一
        return item

    def peek(self):
        if self.is_empty():
            return None
        return self.stack[self.top] # 返回栈顶元素，不移除

优势： 访问速度快，因为数组在内存中是连续存储的。 劣势： 容量固定，可能出现栈溢出。 在初始化时需要预先分配内存，如果分配过大，则浪费空间。

链式栈（链表实现）

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 # 新节点的 next 指向原来的栈顶
        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():
            return None
        return self.top.data # 返回栈顶元素，不移除

优势： 容量可以动态扩展，不容易出现栈溢出。 内存利用率高，不需要预先分配内存。 劣势： 访问速度相对较慢，因为链表在内存中不是连续存储的。

栈的常见应用场景

1. 函数调用栈: 这是栈最经典的应用之一。 当一个函数被调用时，会将函数的参数、返回地址等信息压入栈中，当函数执行完毕后，再从栈中弹出这些信息，返回到调用函数的地方。 我们可以用 gdb 命令查看调用栈，帮助我们调试程序。

   

2. 表达式求值: 编译器通常使用栈来实现表达式求值。 将中缀表达式转换为后缀表达式，然后使用栈进行计算。

3. 浏览器的前进后退: 浏览器的前进后退功能也是通过栈来实现的。 每次访问一个新的页面，就将该页面的 URL 压入栈中。 点击后退按钮时，就从栈中弹出一个 URL，并加载该页面。

   

4. 撤销操作: 许多编辑器和软件都支持撤销操作， 这也是通过栈来实现的。 每次执行一个操作，就将该操作的信息压入栈中。 点击撤销按钮时，就从栈中弹出一个操作，并执行相反的操作。

5. 括号匹配: 检查代码中的括号是否匹配，可以使用栈来完成。 遇到左括号就压入栈中， 遇到右括号就从栈中弹出一个左括号，如果匹配则继续，否则表示括号不匹配。

实战避坑经验

• 注意栈溢出: 使用数组实现栈时，需要预先分配内存，并且容量是固定的。 如果压入栈的元素过多，就可能导致栈溢出。因此，在设计系统时，需要仔细评估栈的容量，并采取相应的措施，例如动态扩容或者使用链式栈。
• 避免空栈弹出: 在执行弹栈操作之前，务必检查栈是否为空。 如果栈为空，则执行弹栈操作会抛出异常。
• 合理选择实现方式: 根据实际需求选择合适的栈实现方式。 如果需要频繁进行压栈和弹栈操作，并且对内存利用率要求较高，则可以选择链式栈。 如果对访问速度要求较高，则可以选择顺序栈。

掌握好栈这种基础数据结构入门知识，并灵活运用，可以帮助我们构建更健壮、更高效的系统。在复杂的后端架构中，小小的栈，也能发挥大作用。