队列（Queue）作为一种有次序的数据结构，是一种先进先出（FIFO）的线性数据结构，插入操作在队尾（rear）进行，删除操作在队首（front）进行。
队列结构
队列的例子出现我们日常生活中，比如排队，不允许数据项之间插入队中，也不允许从中间移除数据项。
在计算机应用中队列的例子有：
1、打印队列：打印机需要一个一个任务处理，因此打印请求需要排成队列，以FIFO的形式等待被处理。
2、进程调度：操作系统核心采用多个队列来对系统中同时运行的进程进行调度，因为进程数远多于CPU核心数，调度原则综合了“先到先服务”和“资源充分利用”两个点。
3、键盘缓冲：当我们打字太快，就需要有个队列性质的缓冲区，将尚未显示的敲击字符暂存其中，队列先进先出的性质保证字符的输入和显示次序一致。
队列ADT（抽象数据类型）一般提供以下接口：
Queue() ：创建一个空队列，返回值为Queue对象；
enqueue(item) ：向队尾插入项，无返回；
dequeue() ：返回队首的项，并从队列中删除该项；
isEmpty() ：判断队列是否为空
size() ：返回队列中项的个数
我们可以采用List来实现，代码如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(0,item) //每次插入都放在list首端
def dequeue(self):
return self.items.pop()
def empty(self):
return self.size() == 0
def size(self):
return len(self.items)
该算法以List首端作为队列尾端，以list末端作为队列首端，enqueue()复杂度为O(n)，dequeue()复杂度为O(1)。
实际上我们也可以把List首端作为队列首端，以list末端作为队列尾端，则enqueue()复杂度为O(1)，dequeue()复杂度为O(n)。
网友评论