队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,新来的人只能在后面排队,直到轮到他们为止。

队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。队列被用在很多地方,比如提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

队列的两种主要操作是:向队列中插入新元素和删除队列中的元素。插入操作也叫做入队,删除操作也叫做出队。入队操作在队尾插入新元素,出队操作删除队头的元素。

队列的另外一项重要操作是读取队头的元素。这个操作叫做peek()。该操作返回队头元素,但不把它从队列中删除。除了读取队头元素,我们还想知道队列中存储了多少元素,可以使用size()满足该需求。

queue通常的操作:

12345 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 类模拟:

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

以下是测试代码:

1234567891011 q=Queue()q.isEmpty() q.enqueue(\’dog\’)q.enqueue(4)q=Queue()q.isEmpty() q.enqueue(4)q.enqueue(\’dog\’)q.enqueue(True)