六、栈————相关概念详解

---

前言

• 本篇文章，我们一起来学习栈的知识。

---

一、栈(stack)

1.1 栈是什么?

• 栈（stack）是一种遵循先入后出逻辑的线性数据结构。

1.2 栈的类比

• 我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

• 如下图所示，我们演示栈的先入后出的规则。

  • 我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。
  • 将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。
  • 

二、栈的常用操作

• Python 中没有专门提供的栈类，我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

2.1 初始化栈

代码演示：

# 初始化栈
# Python 没有内置的栈类，可以把 list 当作栈来使用
stack: list[int] = []

2.2 元素入栈

代码演示：

# 元素入栈
stack.append(9)
stack.append(7)
stack.append(0)
stack.append(1)
stack.append(1)

2.3 访问栈顶元素

代码演示：

# 访问栈顶元素
peek: int = stack[-1]

2.4 元素出栈

代码演示：

# 元素出栈
pop: int = stack.pop()

2.5 获取栈的长度

代码演示：

# 获取栈的长度
size: int = len(stack)

2.6 判断是否为空

代码演示：

# 判断是否为空
is_empty: bool = len(stack) == 0

三、栈的实现

• 栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。
• 然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。换句话说，我们可以“屏蔽”数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

3.1 基于数组实现栈

3.1.1 代码演示

代码演示：

class Stack:  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  # 在栈顶插入一个元素。如果栈已满，则抛出OverflowErrordef push(self, item):  if self.is_full():  raise OverflowError("Stack is full")  self.top += 1  self.stack[self.top] = item  print(f"Pushed {item} onto stack.")  # 从栈顶删除一个元素并返回它。如果栈为空，则抛出IndexErrordef pop(self):  if self.is_empty():  raise IndexError("Stack is empty")  item = self.stack[self.top]  self.stack[self.top] = None  # 清除引用，有助于垃圾回收  self.top -= 1  print(f"Popped {item} from stack.")  return item  # 返回栈顶元素但不删除它。如果栈为空，则抛出IndexError  def peek(self):  if self.is_empty():  raise IndexError("Stack is empty")  return self.stack[self.top]  # 返回栈中的元素数量def size(self):  return self.top + 1  if __name__ == '__main__':      # 使用示例  stack = Stack(5)  # 创建一个容量为5的栈  stack.push(10)  stack.push(20)  stack.push(30)  print("Top element is:", stack.peek())  stack.pop()  stack.pop()  print("Top element is:", stack.peek())  stack.push(40)  stack.push(50)  stack.push(60)  # 这将会引发OverflowError，因为栈已满

3.1.2 上述代码不足

• 容量限制：基于数组的栈有固定的容量，如果栈满了，再尝试插入元素会引发错误。
• 动态数组：如果需要动态大小的栈，可以使用Python的列表(list)，它会自动调整大小，但这样可能会失去固定大小数组带来的性能优势。
• 异常处理：在实际应用中，应该妥善处理栈满和栈空的情况，避免程序崩溃。

3.2 基于链表实现栈

• 由于链表的动态特性，这个实现可以高效地管理栈的操作，并且没有容量限制。

3.2.1 基于头插法实现

代码演示：

class Node:  """Node类：表示链表中的一个节点，包含值（value）和指向下一个节点的指针（next）"""def __init__(self, value):  self.value = value  self.next = None  class Stack:  # 初始化栈顶指针（top）为None。def __init__(self):  self.top = None  # 栈顶指针，初始化为None  # 检查栈是否为空def is_empty(self):  return self.top is None  # 使用头插法将新节点插入到链表头部，并更新栈顶指针。# 这正是头插法的体现，新节点总是成为新的栈顶。def push(self, value):  new_node = Node(value)  new_node.next = self.top  # 新节点的next指向当前的栈顶（如果有的话）  self.top = new_node  # 更新栈顶指针为新节点  print(f"Pushed {value} onto stack.")  # 移除并返回栈顶元素，如果栈为空则抛出异常  def pop(self):  if self.is_empty():  raise IndexError("pop from empty stack")  popped_value = self.top.value  self.top = self.top.next  # 栈顶指针移动到下一个节点  print(f"Popped {popped_value} from stack.")  return popped_value  # 返回栈顶元素但不移除它，如果栈为空则抛出异常  def peek(self):  if self.is_empty():  raise IndexError("peek from empty stack")  return self.top.value  # 遍历链表并打印栈的元素，从栈顶到底部的顺序  def display(self):  # 使用栈的特性，从栈顶到底部打印元素  elements = []  current = self.top  while current:  elements.append(current.value)  current = current.next  print("Stack elements (top to bottom):", elements)  # 测试栈  
if __name__ == "__main__":  stack = Stack()  stack.push(10)  stack.push(20)  stack.push(30)  stack.display()  # 输出栈元素，从栈顶到底部  print(f"Top element is {stack.peek()}")  stack.pop()  stack.display()  stack.pop()  stack.pop()  # 尝试从空栈弹出元素会引发异常  # stack.pop()  # 取消注释此行将引发IndexError

3.2.2 基于尾巴插法实现

代码演示：

# 定义的节点类
class Node:  """Node类：表示链表中的一个节点，包含值（value）和指向下一个节点的指针（next）。"""def __init__(self, value):  self.value = value  self.next = None  
# 定义栈类  
class Stack:  # 初始化栈顶指针（top）为Nonedef __init__(self):  self.top = None  # 栈顶指针，初始化为None  # 检查栈是否为空def is_empty(self):  return self.top is None  # 使用尾插法将新节点插入到链表头部，并更新栈顶指针def push(self, value):  new_node = Node(value)  new_node.next = self.top  # 新节点的next指向当前的栈顶  self.top = new_node  # 栈顶更新为新节点  print(f"Pushed {value} onto stack.")  # 移除并返回栈顶元素，如果栈为空则抛出异常def pop(self):  if self.is_empty():  raise IndexError("pop from empty stack")  popped_value = self.top.value  self.top = self.top.next  # 栈顶指针移动到下一个节点  print(f"Popped {popped_value} from stack.")  return popped_value  # 返回栈顶元素但不移除它，如果栈为空则抛出异常def peek(self):  if self.is_empty():  raise IndexError("peek from empty stack")  return self.top.value  # 遍历链表并打印栈的元素，从栈顶到底部的顺序（注意反转列表以显示正确的顺序）def display(self):  current = self.top  stack_elements = []  while current:  stack_elements.append(current.value)  current = current.next  print("Stack elements (top to bottom):", stack_elements[::-1])  # 反转列表以显示正确的顺序  # 测试栈  
if __name__ == "__main__":  stack = Stack()  stack.push(10)  stack.push(20)  stack.push(30)  stack.display()  print(f"Top element is {stack.peek()}")  stack.pop()  stack.display()  stack.pop()  stack.pop()  # 尝试从空栈弹出元素会引发异常  # stack.pop()  # Uncommenting this line will raise an IndexError

四、栈的典型应用

• 浏览器中的后退与前进、软件中的撤销与反撤销。
  • 每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
• 程序内存管理。
  • 每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

---

总结

• 我们总结了栈中常用的几种操作，因为 Python 中没有直接的栈类，我们基于数组和链表实现了栈类，但是我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。