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())

亲自试一试

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

动态大小:与数组不同,队列可以动态地增长和缩小。
无需移动:队列的队首元素可以移除(出队)而无需移动内存中的其他元素。

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

额外内存:每个队列元素必须包含指向下一个元素的地址(即下一个链表节点)。
可读性:对于某些人来说,代码可能更难阅读和编写,因为它更长且更复杂。

队列的常见应用

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

操作系统中的任务调度
图中的广度优先搜索
分布式系统中的消息队列

(追記) (追記ここまで)