Python 实现栈、队列与双端队列

栈（Stack）的实现

栈是一种运算受限的线性表，其核心特征在于仅允许在表的一端进行插入和删除操作。这一端被称为“栈顶”，而另一端则称为“栈底”。向栈中插入新元素的操作称为“入栈”或“压栈”，此时新元素会覆盖原栈顶元素成为新的栈顶；从栈中删除元素的操作称为“出栈”或“退栈”，删除栈顶元素后，其相邻元素将变为新的栈顶。

在 Python 中，可以使用内置列表（List）作为顺序表来高效实现栈。列表的 append() 和 pop() 方法天然支持栈的后进先出（LIFO）逻辑。

# -*- coding: utf-8 -*-
class Stack(object):
  """栈的实现类"""
  def __init__(self):
    self.__items = []
  # push(item) 添加一个新的元素item到栈顶
  def push(self, item):
    self.__items.append(item)
  # pop() 弹出栈顶元素
  def pop(self):
    return self.__items.pop()
  # peek() 返回栈顶元素
  def peek(self):
    return self.__items[self.size() - 1]
  # is_empty() 判断栈是否为空
  def is_empty(self):
    return self.__items == []
  # size() 返回栈的元素个数
  def size(self):
    return len(self.__items)
if __name__ == '__main__':
  stack = Stack()
  stack.push(2)
  stack.push(3)
  stack.push(4)
  stack.push(5)
  tmp = stack.pop()
  print(tmp)
  print(stack.peek())
  print(stack.size())
  print(stack.is_empty())

队列（Queue）的实现

队列是一种特殊的线性表，遵循先进先出（FIFO）原则。它只允许在表的前端进行删除操作，在表的后端进行插入操作。插入操作的端称为“队尾”，删除操作的端称为“队头”。当队列中没有元素时，称为空队列。

在 Python 实现中，为了模拟队列的 FIFO 特性，通常将列表的头部视为队头。使用 insert(0, item) 在列表头部插入元素（入队），并使用 pop() 移除列表尾部元素（出队）。需要注意的是，在列表头部频繁插入元素的时间复杂度为 O(n)，对于大规模数据场景，建议使用 collections.deque 以获得 O(1) 的性能。

# -*- coding: utf-8 -*-
class Queue(object):
  """队列的实现"""
  def __init__(self):
    self.__items = []
  # push(item) 往队列中添加一个item元素
  def push(self, item):
    self.__items.insert(0, item)
  # pop() 从队列头部删除一个元素
  def pop(self):
    return self.__items.pop()
  # is_empty() 判断一个队列是否为空
  def is_empty(self):
    return self.__items == []
  # size() 返回队列的大小
  def size(self):
    return len(self.__items)
if __name__ == '__main__':
  queue = Queue()
  queue.push(1)
  queue.push(2)
  queue.push(3)
  queue.push(4)
  print(queue.pop())
  print(queue.pop())
  print(queue.pop())
  print(queue.size())
  print(queue.is_empty())

双端队列（Deque）的实现

双端队列（Double-ended Queue，简称 Deque）结合了栈和队列的特性。它允许在表的两端进行插入和删除操作，即元素可以从队头加入或弹出，也可以从队尾加入或弹出。这种结构提供了极大的灵活性，既可以实现栈的 LIFO 逻辑，也可以实现队列的 FIFO 逻辑。

以下代码展示了如何使用列表实现双端队列，支持从队头（add_front）和队尾（add_rear）添加元素，以及从两端删除元素（remove_front 和 remove_rear）。

# -*- coding: utf-8 -*-
class Deque(object):
  """双端队列"""
  def __init__(self):
    self.__items = []
  # add_front(item) 从队头加入一个item元素
  def add_front(self, item):
    self.__items.insert(0, item)
  # add_rear(item) 从队尾加入一个item元素
  def add_rear(self, item):
    self.__items.append(item)
  # remove_front() 从队头删除一个item元素
  def remove_front(self):
    return self.__items.pop(0)
  # remove_rear() 从队尾删除一个item元素
  def remove_rear(self):
    return self.__items.pop()
  # is_empty() 判断双端队列是否为空
  def is_empty(self):
    return self.__items == []
  # size() 返回队列的大小
  def size(self):
    return len(self.__items)
  def print_items(self):
    print(self.__items)
if __name__ == '__main__':
  deque = Deque()
  deque.add_front(1)
  deque.add_front(3)
  deque.add_front(5)
  deque.print_items()
  deque.add_rear(9)
  deque.add_rear(8)
  deque.add_rear(7)
  deque.print_items()
  print(deque.is_empty())
  print(deque.remove_front())
  print(deque.remove_rear())
  deque.print_items()

以上就是 Python 实现栈、队列与双端队列的详细内容，更多关于 Python 数据结构与算法的资料请关注本站其它相关文章！