一、栈
1.1、概念
栈（stack)：又名堆栈，它是一种运算受限的线性表，是一种容器，可存入数据元素、访 问元素、删除元素，它的特点在于只能允许在容器的一端（成为栈顶top），进行存入数 据（push）和输出数据（pop）的运算，没有位置概念，保证任何时候都可以访问、删 除元素。栈仅允许在栈顶一端进行操作，因此，栈是按照先进后出（LIFO，Last In First Out）的原理进行运作。
1.2、操作
栈使用两种基本操作：入栈(压栈，push) 和 出栈(弹栈，pop):
入栈：将数据放入栈顶端
出栈：将栈顶端数据移除
1.3、特点
1.先入后出(FILO, First In Last Out)，后入先出(LIFO, Last In First Out)
2.除头尾节点之外，每个元素有一个前驱，一个后继
二、顺序栈
2.1、初始化
python"> def __init__(self): """初始化一个空栈，使用列表作为存储容器。""" self.__list = [] 2.2、入栈
python"> def push(self, data): """将数据压入栈中。 Args: data: 要压入栈中的数据。 """ self.__list.append(data) 2.3、出栈
python"> def pop(self): """从栈中弹出数据。如果栈为空，打印提示信息。 Returns: 弹出的数据，如果栈为空则返回 None。 """ if self.is_empty(): print('空空如也') # 栈为空，无法弹出数据 return None # 返回 None，指示无数据可弹出 return self.__list.pop() # 弹出栈顶元素并返回 2.4、获取栈长度
python"> def size(self): """返回栈中元素的数量。 Returns: 栈中元素的数量。 """ return self.__list.__len__() # 返回栈的大小 2.5、判断是否为空
python"> def is_empty(self): """检查栈是否为空。 Returns: 如果栈为空返回 True，否则返回 False。 """ return self.__list == [] # 返回是否为真空栈 2.6、访问栈顶元素
python"> def peek(self): """查看栈顶数据但不弹出。如果栈为空，返回 None。 Returns: 栈顶的数据，如果栈为空则返回 None。 """ if self.__list: return self.__list[-1] # 返回栈顶元素 else: return None # 栈为空，返回 None 2.7、完整代码
python">class Stack: def __init__(self): """初始化一个空栈，使用列表作为存储容器。""" self.__list = [] def push(self, data): """将数据压入栈中。 Args: data: 要压入栈中的数据。 """ self.__list.append(data) def pop(self): """从栈中弹出数据。如果栈为空，打印提示信息。 Returns: 弹出的数据，如果栈为空则返回 None。 """ if self.is_empty(): print('空空如也') # 栈为空，无法弹出数据 return None # 返回 None，指示无数据可弹出 return self.__list.pop() # 弹出栈顶元素并返回 def peek(self): """查看栈顶数据但不弹出。如果栈为空，返回 None。 Returns: 栈顶的数据，如果栈为空则返回 None。 """ if self.__list: return self.__list[-1] # 返回栈顶元素 else: return None # 栈为空，返回 None def is_empty(self): """检查栈是否为空。 Returns: 如果栈为空返回 True，否则返回 False。 """ return self.__list == [] # 返回是否为真空栈 def size(self): """返回栈中元素的数量。 Returns: 栈中元素的数量。 """ return self.__list.__len__() # 返回栈的大小 if __name__ == '__main__': a = Stack() # 创建一个栈实例 a.push(10) # 将 10 压入栈 a.push(20) # 将 20 压入栈 a.push(30) # 将 30 压入栈 a.push(40) # 将 40 压入栈 a.push(50) # 将 50 压入栈 print() print(a.size()) # 打印栈的大小，应该输出 5 print(a.peek()) # 查看栈顶元素，应该输出 50三、链栈
3.1、初始化
python">class Node:def __init__(self, data):"""初始化节点，包含数据和指向下一个节点的指针。Args:data: 节点存储的数据。"""self.data = dataself.next = None # 初始时，节点的 next 指向 Nonepython"> def __init__(self):"""初始化一个空栈，使用头节点作为哨兵。"""self.head = Node(0) # 哨兵节点，方便操作3.2、入栈
python"> def push(self, data):"""将数据压入栈中。Args:data: 要压入栈中的数据。"""new_node = Node(data) # 创建新节点new_node.next = self.head.next # 新节点的 next 指向当前栈顶self.head.next = new_node # 更新栈顶为新节点
3.3、出栈
python"> def pop(self):"""从栈中弹出数据。如果栈为空，打印提示信息。Returns:弹出的数据，如果栈为空则返回 None。"""if self.is_empty():print('空空如也') # 栈为空，无法弹出数据return None # 返回 None，指示无数据可弹出popped_data = self.head.next.data # 获取栈顶元素self.head.next = self.head.next.next # 移动栈顶指针到下一个节点return popped_data # 返回弹出的数据3.4、获取栈长度
python"> def size(self):"""返回栈中元素的数量。Returns:栈中元素的数量。"""count = 0current = self.head.next # 从第一个有效节点开始while current is not None:count += 1current = current.next # 移动到下一个节点return count # 返回计数
3.5、判断是否为空
python"> def is_empty(self):"""检查栈是否为空。Returns:如果栈为空返回 True，否则返回 False。"""return self.head.next is None # 如果头节点的 next 为 None，栈为空3.6、访问栈顶元素
python"> def peek(self):"""查看栈顶元素但不弹出。如果栈为空，返回 None。Returns:栈顶的数据，如果栈为空则返回 None。"""if self.is_empty():return None # 如果栈为空，返回 Nonereturn self.head.next.data # 返回栈顶元素3.7、完整代码
python">class Node:def __init__(self, data):"""初始化节点，包含数据和指向下一个节点的指针。Args:data: 节点存储的数据。"""self.data = dataself.next = None # 初始时，节点的 next 指向 Noneclass StackLink:def __init__(self):"""初始化一个空栈，使用头节点作为哨兵。"""self.head = Node(0) # 哨兵节点，方便操作def is_empty(self):"""检查栈是否为空。Returns:如果栈为空返回 True，否则返回 False。"""return self.head.next is None # 如果头节点的 next 为 None，栈为空def size(self):"""返回栈中元素的数量。Returns:栈中元素的数量。"""count = 0current = self.head.next # 从第一个有效节点开始while current is not None:count += 1current = current.next # 移动到下一个节点return count # 返回计数def push(self, data):"""将数据压入栈中。Args:data: 要压入栈中的数据。"""new_node = Node(data) # 创建新节点new_node.next = self.head.next # 新节点的 next 指向当前栈顶self.head.next = new_node # 更新栈顶为新节点def peek(self):"""查看栈顶元素但不弹出。如果栈为空，返回 None。Returns:栈顶的数据，如果栈为空则返回 None。"""if self.is_empty():return None # 如果栈为空，返回 Nonereturn self.head.next.data # 返回栈顶元素def pop(self):"""从栈中弹出数据。如果栈为空，打印提示信息。Returns:弹出的数据，如果栈为空则返回 None。"""if self.is_empty():print('空空如也') # 栈为空，无法弹出数据return None # 返回 None，指示无数据可弹出popped_data = self.head.next.data # 获取栈顶元素self.head.next = self.head.next.next # 移动栈顶指针到下一个节点return popped_data # 返回弹出的数据def travel(self):"""遍历栈并打印所有元素。"""current = self.head.next # 从第一个有效节点开始while current is not None:print(current.data, end=' ') # 打印当前节点的数据current = current.next # 移动到下一个节点print() # 换行if __name__ == '__main__':s = StackLink() # 创建一个栈实例s.push(10) # 压入 10s.push(20) # 压入 20s.push(30) # 压入 30s.push(40) # 压入 40s.push(50) # 压入 50s.travel() # 打印当前栈的所有元素print("Popped:", s.pop()) # 弹出栈顶元素并打印s.travel() # 打印弹出后的栈元素四、思维导图
