一、栈
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、初始化
def __init__(self):
"""初始化一个空栈，使用列表作为存储容器。"""
self.__list = [] 2.2、入栈
def push(self, data):
"""将数据压入栈中。
Args:
data: 要压入栈中的数据。
"""
self.__list.append(data) 2.3、出栈
def pop(self):
"""从栈中弹出数据。如果栈为空，打印提示信息。
Returns:
弹出的数据，如果栈为空则返回 None。
"""
if self.is_empty():
print('空空如也') # 栈为空，无法弹出数据
return None # 返回 None，指示无数据可弹出
return self.__list.pop() # 弹出栈顶元素并返回 2.4、获取栈长度
def size(self):
"""返回栈中元素的数量。
Returns:
栈中元素的数量。
"""
return self.__list.__len__() # 返回栈的大小 2.5、判断是否为空
def is_empty(self):
"""检查栈是否为空。
Returns:
如果栈为空返回 True，否则返回 False。
"""
return self.__list == [] # 返回是否为真空栈 2.6、访问栈顶元素
def peek(self):
"""查看栈顶数据但不弹出。如果栈为空，返回 None。
Returns:
栈顶的数据，如果栈为空则返回 None。
"""
if self.__list:
return self.__list[-1] # 返回栈顶元素
else:
return None # 栈为空，返回 None 2.7、完整代码
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、初始化
class Node:
def __init__(self, data):
"""初始化节点，包含数据和指向下一个节点的指针。
Args:
data: 节点存储的数据。
"""
self.data = data
self.next = None # 初始时，节点的 next 指向 None def __init__(self):
"""初始化一个空栈，使用头节点作为哨兵。"""
self.head = Node(0) # 哨兵节点，方便操作3.2、入栈
def push(self, data):
"""将数据压入栈中。
Args:
data: 要压入栈中的数据。
"""
new_node = Node(data) # 创建新节点
new_node.next = self.head.next # 新节点的 next 指向当前栈顶
self.head.next = new_node # 更新栈顶为新节点
3.3、出栈
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、获取栈长度
def size(self):
"""返回栈中元素的数量。
Returns:
栈中元素的数量。
"""
count = 0
current = self.head.next # 从第一个有效节点开始
while current is not None:
count += 1
current = current.next # 移动到下一个节点
return count # 返回计数
3.5、判断是否为空
def is_empty(self):
"""检查栈是否为空。
Returns:
如果栈为空返回 True，否则返回 False。
"""
return self.head.next is None # 如果头节点的 next 为 None，栈为空3.6、访问栈顶元素
def peek(self):
"""查看栈顶元素但不弹出。如果栈为空，返回 None。
Returns:
栈顶的数据，如果栈为空则返回 None。
"""
if self.is_empty():
return None # 如果栈为空，返回 None
return self.head.next.data # 返回栈顶元素3.7、完整代码
class Node:
def __init__(self, data):
"""初始化节点，包含数据和指向下一个节点的指针。
Args:
data: 节点存储的数据。
"""
self.data = data
self.next = None # 初始时，节点的 next 指向 None
class 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 = 0
current = self.head.next # 从第一个有效节点开始
while current is not None:
count += 1
current = 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 # 如果栈为空，返回 None
return 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) # 压入 10
s.push(20) # 压入 20
s.push(30) # 压入 30
s.push(40) # 压入 40
s.push(50) # 压入 50
s.travel() # 打印当前栈的所有元素
print("Popped:", s.pop()) # 弹出栈顶元素并打印
s.travel() # 打印弹出后的栈元素四、思维导图
