队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。
队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
队列的另外一项重要操作是读取队头的元素。这个操作叫做peek()。该操作返回队头元素，但不把它从队列中删除。除了读取队头元素，我们还想知道队列中存储了多少元素，可以使用size()满足该需求。
queue通常的操作：
|
1 2 3 4 5 |
Queue() 定义一个空队列，无参数，返回值是空队列。 enqueue(item) 在队列尾部加入一个数据项，参数是数据项，无返回值。 dequeue() 删除队列头部的数据项，不需要参数，返回值是被删除的数据，队列本身有变化。 isEmpty() 检测队列是否为空。无参数，返回布尔值。 size() 返回队列数据项的数量。无参数，返回一个整数。 |
队列操作举例：
| Queue Operation | Queue Contents | Return Value |
|---|---|---|
| q.isEmpty() | [] | True |
| q.enqueue(4) | [4] | |
| q.enqueue(‘dog’) | [‘dog’,4] | |
| q.enqueue(True) | [True,’dog’,4] | |
| q.size() | [True,’dog’,4] | 3 |
| q.isEmpty() | [True,’dog’,4] | False |
| q.enqueue(8.4) | [8.4,True,’dog’,4] | |
| q.dequeue() | [8.4,True,’dog’] | 4 |
| q.dequeue() | [8.4,True] | ‘dog’ |
| q.size() | [8.4,True] | 2 |
Queue 类模拟:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Queue: """模拟队列""" def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) |
以下是测试代码：
|
1 2 3 4 5 6 7 8 9 10 11 |
q=Queue() q.isEmpty() q.enqueue('dog') q.enqueue(4) q=Queue() q.isEmpty() q.enqueue(4) q.enqueue('dog') q.enqueue(True) |
