栈————相关概念详解
前言
- 本篇文章，我们一起来学习栈的知识。
一、栈(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
# 在栈顶插入一个元素。如果栈已满，则抛出OverflowError
def 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.")
# 从栈顶删除一个元素并返回它。如果栈为空，则抛出IndexError
def 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）为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):
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 中没有直接的栈类，我们基于数组和链表实现了栈类，但是我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。