Python数据结构与算法中的队列详解(1)
时间：2022-09-12 10:13:51 | 栏目：Python代码 | 点击：次
什么是队列？
队列，与栈类似，是有序集合。添加操作发生在 “尾部”，移除操作只发生在 “头部”。新元素只从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。?
最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作FIFO（first-in first-out），即先进先出，也称先到先得。在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要排队，买咖啡也要排队。好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。?
构建一个队列
如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 FIFO，它支持以下操作。
- 创建一个空队列。它不需要参数，且会返回一个空队列。
Queue() - 在队列的尾部添加一个元素。 它需要一个元素作为参数，不返回任何值。
enqueue(item) - 从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列的内容。
dequeue() - 检查队列是否为空。它不需要参数， 且会返回一个布尔值。
isEmpty() - 返回队列中元素的数目。它不需要参数，且会返回一个整数。
size()?
与构建栈一样，我们利用简洁强大的列表来实现队列。?
需要确定列表的哪一端是队列的尾部，哪一端是头部。 我们假设队列的尾部在列表的位置0处。 如此一来，便可以使用 insert 函数向队列的尾部添加新元素。pop 则可用于移除队列头部的元素（列表中的最后一个元素）。这意味着添加操作的时间复杂度是O(n)，移除操作则是O(1)。?
队列实现代码如下：
class Queue:
def __init__(self):
self.items = [] # 构建空队列
print("你创建了一个队列")
def isEmpty(self):
return self.items ==[] # 判断是否为空
def enqueue(self,item):
self.items.insert(0, item) # 在队列尾部(列表左端)插入元素
print("你在队列尾部插入了一个%s" % item)
def dequeue(self):
print("你在队列头部移除了一个元素")
return self.items.pop() # 在队列头部(列表右端)移出元素
def size(self):
return len(self.items) # 队列(列表)长度
def look(self):
print(self.items)
下图展示了队列的操作及其返回结果：
