提示信息

Python实现的数据结构:栈

浮生未歇 已关注

在Python中,可以使用列表(list)来实现一个简单的栈数据结构。栈是一种遵循后进先出(LIFO, Last In First Out)原则的集合。以下是一个简单的栈实现示例:

  1. class Stack:
  2. def __init__(self):
  3. """初始化一个空栈"""
  4. self.items = []
  5. def is_empty(self):
  6. """检查栈是否为空"""
  7. return len(self.items) == 0
  8. def push(self, item):
  9. """将一个元素入栈"""
  10. self.items.append(item)
  11. def pop(self):
  12. """从栈中移除并返回栈顶元素"""
  13. if self.is_empty():
  14. raise IndexError("pop from empty stack")
  15. return self.items.pop()
  16. def peek(self):
  17. """返回栈顶元素但不移除它"""
  18. if self.is_empty():
  19. raise IndexError("peek from empty stack")
  20. return self.items[-1]
  21. def size(self):
  22. """返回栈中的元素个数"""
  23. return len(self.items)
  24. def __str__(self):
  25. """返回栈的字符串表示"""
  26. return str(self.items)
  27. # 使用示例
  28. stack = Stack()
  29. print("Stack empty?", stack.is_empty()) # 输出: True
  30. stack.push(1)
  31. stack.push(2)
  32. stack.push(3)
  33. print("Stack after pushes:", stack) # 输出: [1, 2, 3]
  34. print("Peek:", stack.peek()) # 输出: 3
  35. print("Pop:", stack.pop()) # 输出: 3
  36. print("Stack after pop:", stack) # 输出: [1, 2]
  37. print("Stack size:", stack.size()) # 输出: 2
  38. print("Stack empty?", stack.is_empty()) # 输出: False

解释

  • 初始化__init__ 函数创建一个空列表 items,用来存储栈中的元素。
  • is_empty:检查栈是否为空。
  • push:使用 append 方法将一个元素添加到栈顶。
  • pop:使用 pop 方法从栈顶移除元素并返回它。注意,这里需要检查栈是否为空,以避免在空栈上调用 pop 引发错误。
  • peek:返回栈顶的元素而不移除它。这同样需要检查栈是否为空。
  • size:返回栈中元素的个数。
  • __str__:返回栈的字符串表示,使其更易于打印和调试。

这种实现可以满足大多数简单的栈操作需求。如果需要更高效的栈操作(例如,复杂度为O(1)的所有操作),可以使用 collections.deque

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
浮生未歇 关注 已关注

最近一次登录:2024-11-20 21:10:49   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图