Python实现的数据结构:栈
在Python中,可以使用列表(list
)来实现一个简单的栈数据结构。栈是一种遵循后进先出(LIFO, Last In First Out)原则的集合。以下是一个简单的栈实现示例:
class Stack:
def __init__(self):
"""初始化一个空栈"""
self.items = []
def is_empty(self):
"""检查栈是否为空"""
return len(self.items) == 0
def push(self, item):
"""将一个元素入栈"""
self.items.append(item)
def pop(self):
"""从栈中移除并返回栈顶元素"""
if self.is_empty():
raise IndexError("pop from empty stack")
return self.items.pop()
def peek(self):
"""返回栈顶元素但不移除它"""
if self.is_empty():
raise IndexError("peek from empty stack")
return self.items[-1]
def size(self):
"""返回栈中的元素个数"""
return len(self.items)
def __str__(self):
"""返回栈的字符串表示"""
return str(self.items)
# 使用示例
stack = Stack()
print("Stack empty?", stack.is_empty()) # 输出: True
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack after pushes:", stack) # 输出: [1, 2, 3]
print("Peek:", stack.peek()) # 输出: 3
print("Pop:", stack.pop()) # 输出: 3
print("Stack after pop:", stack) # 输出: [1, 2]
print("Stack size:", stack.size()) # 输出: 2
print("Stack empty?", stack.is_empty()) # 输出: False
解释
- 初始化:
__init__
函数创建一个空列表items
,用来存储栈中的元素。 - is_empty:检查栈是否为空。
- push:使用
append
方法将一个元素添加到栈顶。 - pop:使用
pop
方法从栈顶移除元素并返回它。注意,这里需要检查栈是否为空,以避免在空栈上调用pop
引发错误。 - peek:返回栈顶的元素而不移除它。这同样需要检查栈是否为空。
- size:返回栈中元素的个数。
- __str__:返回栈的字符串表示,使其更易于打印和调试。
这种实现可以满足大多数简单的栈操作需求。如果需要更高效的栈操作(例如,复杂度为O(1)的所有操作),可以使用 collections.deque
。