Python 中的队列

队列是一种遵循先进先出（FIFO）原则的线性数据结构。

队列

可以将队列想象成人们在超市里排队。

第一个排队的人也是第一个可以付款并离开超市的人。

我们可以在队列上执行的基本操作包括：

  • 入队（Enqueue）：向队列中添加一个新元素。
  • 出队（Dequeue）：从队列中移除并返回第一个（队首）元素。
  • 查看队首元素（Peek）：返回队列中的第一个元素。
  • 判断队列是否为空（isEmpty）：检查队列是否为空。
  • 队列大小（Size）：找出队列中的元素数量。

队列可以通过数组或链表来实现。

队列可用于实现办公室打印机的作业调度、电子票务的订单处理，或创建图中的广度优先搜索算法。

队列经常与栈一起提及，栈是上一页描述的一种类似的数据结构。

使用 Python 列表实现队列

对于 Python 列表（和数组）而言，队列的外观和行为可以如下所示：





添加：
移除：






由于 Python 列表对实现队列所需的功能提供了良好的支持，因此我们可以从创建队列开始，并仅用几行代码就能执行队列操作：



实例



使用 Python 列表作为队列：



queue = []

# 入队
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)

# 查看队首元素
frontElement = queue[0]
print("Peek: ", frontElement)

# 出队
poppedElement = queue.pop(0)
print("Dequeue: ", poppedElement)

print("Queue after Dequeue: ", queue)

# 判断队列是否为空
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)

# 队列大小
print("Size: ", len(queue))




亲自试一试



注意：虽然使用列表很简单，但从列表开头移除元素（出队操作）需要移动所有剩余元素，这使得对于大型队列来说效率较低。









实现队列类



以下是队列类的完整实现：



实例



使用 Python 类作为队列：



class Queue:
  def __init__(self):
    self.queue = []
    
  def enqueue(self, element):
    self.queue.append(element)

  def dequeue(self):
    if self.isEmpty():
      return "Queue is empty"
    return self.queue.pop(0)

  def peek(self):
    if self.isEmpty():
      return "Queue is empty"
    return self.queue[0]

  def isEmpty(self):
    return len(self.queue) == 0

  def size(self):
    return len(self.queue)

# 创建一个队列
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')

print("Queue: ", myQueue.queue)
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", myQueue.queue)
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())




亲自试一试









使用链表实现队列



链表由包含某种数据的节点以及指向下一个节点的指针组成。


单链表


使用链表的一个主要好处是，节点可以存储在内存中的任何空闲位置，不像数组中的元素那样必须连续存储。链表的另一个优点是，在添加或删除节点时，列表中的其他节点不需要移动。



为了更好地理解使用数组或链表实现队列的优缺点，你应该查看这个页面，它解释了数组和链表在内存中的存储方式。



以下是使用链表实现队列的方法：



实例



使用链表创建队列：



class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class Queue:
  def __init__(self):
    self.front = None
    self.rear = None
    self.length = 0

  def enqueue(self, element):
    new_node = Node(element)
    if self.rear is None:
      self.front = self.rear = new_node
      self.length += 1
      return
    self.rear.next = new_node
    self.rear = new_node
    self.length += 1

  def dequeue(self):
    if self.isEmpty():
      return "Queue is empty"

  def isEmpty(self):
    return self.length == 0

  def size(self):
    return self.length

  def printQueue(self):
    temp = self.front
    while temp:
      print(temp.data, end=" ")
      temp = temp.next
    print()

  def dequeue(self):
    if self.isEmpty():
      return "Queue is empty"
    temp = self.front
    self.front = temp.next
    self.length -= 1
    if self.front is None:
      self.rear = None
    return temp.data

  def peek(self):
    if self.isEmpty():
      return "Queue is empty"
    return self.front.data

  def isEmpty(self):
    return self.length == 0

  def size(self):
    return self.length

  def printQueue(self):
    temp = self.front
    while temp:
      print(temp.data, end=" -> ")
      temp = temp.next
    print()

# 创建一个队列
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')

print("Queue: ", end="")
myQueue.printQueue()
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", end="")
myQueue.printQueue()
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())




亲自试一试



使用链表实现队列的原因：



    

  • 动态大小：与数组不同，队列可以动态地增长和缩小。
    • 

  • 无需移动：队列的队首元素可以移除（出队）而无需移动内存中的其他元素。
    • 




不使用链表实现队列的原因：



    

  • 额外内存：每个队列元素必须包含指向下一个元素的地址（即下一个链表节点）。
    • 

  • 可读性：对于某些人来说，代码可能更难阅读和编写，因为它更长且更复杂。
    • 










队列的常见应用



队列在许多现实场景中都有应用：



    

  • 操作系统中的任务调度
    • 

  • 图中的广度优先搜索
    • 

  • 分布式系统中的消息队列
    •