python环形队列_Python实现循环队列（基于list）

目标

用python实现循环队列，与python list以及python的Queue模块进行运行速度上的对比

队列：

顾名思义，可以将它理解为现实生活中的排队，我们去KFC排队点餐，永远都是先排队的先点餐，后排队的后点餐(如果世界美好，没人插队)

对于队首：比如现在处于队首的是小明，排在小明后面的是小红，小明点完了餐，离开了队伍，排在小明后面的所有顾客前进一步，此时小红就成了队首

对于队尾：比如现在处于队尾的是大雄，这时来了一个胖虎，由于世界和平，不许插队，胖虎只能乖乖排在大雄后面，队尾就变成了胖虎

image.png

可以看到，入队的时间复杂度为O(1)，出队以后，为了维护队列的队首，后面所有成员都需要往前挪一位，此时时间复杂度为O(n)，这种效率显然是不可以接受的，那么能不能不让所有成员都往前挪一位呢？因此就有了循环队列

循环队列：

对于循环队列，我们需要定义一个变量(front)指向队首，同样需要定义(tail)指向下一个元素入队的位置

当队列为空时，front == tail

对于队首：比如现在处于队首的是小明，front就指向小明，小明点完了餐，离开了队伍，排在小明后面的是小红，那么就将front指向小红(front += 1)。

对于队尾：比如现在处于队尾的是大雄，tail就指向大雄后一个位置，这时来了一个胖虎，由于世界和平，不许插队，胖虎只能乖乖排在大雄后面，队尾就变成了胖虎后一个位置，此时tail指向胖虎后一个位置(tail += 1)

image.png

乍一看，似乎不将后面所有成员往前挪，只需维护一下front的指向(front += 1)就可以保证队首，但是我们可以想象下，如果一直只有出队操作，却没有入队操作，在这种情况下，会发生什么？

image.png

根据队列的特性，如果我们需要再添加成员，只能在胖虎后面添加了，那么胖虎前面的这一打空间很显然就浪费了。

然而事实上并不像看到的那么简单，我们不仅仅是浪费了空间，由于这个队列是基于list实现的，所以这个队列实际上是有一个初始容量存在的，不过我们平时使用python list的时候是看不到的(关于python list的底层实现，这里有篇伯乐在线的文章：http://python.jobbole.com/82549/)，当我们将元素入队的时候，如果元素个数达到了这个初始容量，即可判断队列为满，此时如果将元素入队，就需要进行扩容，以便装下更多的元素，同理，若元素出队较多，元素个数降低到某个程度(我们可以自己定义)，就进行缩容，以此节省空间，下图是python list的列表空间分配策略：

image.png

OK，现在假设胖虎所在的队列已经满了，由于只能往后面添加元素，也就是说，哪怕队列里只有一个胖虎，我们也要进行扩容，扩容的原理是重新定义一个容量更大的列表，将原列表的元素遍历赋值给新列表，这是个O(n)复杂度的操作，因此我们需要将前面浪费的空间重新利用起来，一方面减少空间的浪费，另一方面减少扩容的次数，从而提升入队操作的运行速度，这就是循环队列的意义所在了。

我们继续将元素入队，不进行扩容，当队列最后一个位置入队元素后，我们从队列最开始的位置继续入队元素

image.png

由于当tail == front时，我们判断队列为空，所以当出现上图这种情况时，我们判断队列为满，也就是说我们特意浪费了一个空间以维护队列

利用取余，我们判断队列为满的条件如下：

class LoopQueue(object):

def __init__(self, n=10):

self.arr = [None] * (n+1) # 由于特意浪费了一个空间，所以arr的实际大小应该是用户传入的容量+1

self.front = 0

self.tail = 0

self.size = 0

def is_full(self):

return (self.tail+1) % len(self.arr) == self.front

何时扩容、缩容？

扩容方法(resize)：

def resize(self, new_capacity):

new_arr = [None] * (new_capacity+1)

for i in range(self.size):

new_arr[i] = self.arr[(i+self.front) % len(self.arr)]

self.arr = new_arr

self.front = 0

self.tail = self.size

resize方法的时间复杂度为O(n)

这里我定义为，当队列满时，以当前队列容积的2倍进行扩容(这里的容积指的是队列实际可存储的元素个数)

当元素个数少于容积的1/4并且元素个数>1时，以当前队列容积的1/2倍进行扩容(也就是缩容)

注意：

在没有触发扩容、缩容条件的时候，我们的入队、出队操作的时间复杂度仅仅为O(1)，我们只需要维护front和tail即可，但是一旦触发扩容、缩容条件，就需要执行一次resize这个时间复杂度为O(n)的操作

缩容操作之所以定义在当元素个数少于容积的1/4时才进行，而不是1/2，是因为存在一种极端情况：

比如我们的队列此时已经满了，入队一个元素，我们需要扩容(2倍)，如果缩容条件仅仅是容积(2倍扩容后)的1/2，那么此时我们出队一个元素，就需要进行一次缩容操作，也就是说...当队列满的时候，无限入队一个元素，无限出队一个元素，就要无限进行resize这个时间复杂度为O(n)的操作，因此这里选择牺牲了一点空间来避免这种极端情况的出现

时间复杂度

现在假设我们的容积capacity为n，我们用enqueue方法n+1次，才会触发一次resize，而一次resize，进行了n次操作，也就是说，平均每次enqueue，我们执行的基本操作次数为： (n+1)+n/n+1 ≈ 2，enqueue操作的时间复杂度为O(1)，同理，dequeue(出队)方法也是O(1)级别的时间复杂度

Python实现循环队列的代码

import datetime

class LoopQueue(object):

def __init__(self, n=10):

self.arr = [None] * (n+1) # 由于特意浪费了一个空间，所以arr的实际大小应该是用户传入的容量+1

self.front = 0

self.tail = 0

self.size = 0

def __str__(self):

return str(self.arr)

def __len__(self):

return len(self.arr)

def __iter__(self):

return iter(self.arr)

def get_size(self):

# 获取队列元素个数

return self.size

def get_capaticty(self):

# 获取队列容积(实际可存储元素个数)

return self.__len__() - 1

def is_full(self):

# 判断队列是否为满

return (self.tail+1) % len(self.arr) == self.front

def is_empty(self):

# 判断队列是否为空

return self.size == 0

def get_front(self):

# 获取队首

return self.arr[self.front]

def enqueue(self, e):

# 入队

if self.is_full():

self.resize(self.get_capaticty() * 2) # 如果队列满，以当前队列容积的2倍进行扩容

self.arr[self.tail] = e

self.tail = (self.tail+1) % len(self.arr)

self.size += 1

def dequeue(self):

# 出队

if self.is_empty():

raise Exception("Cannot dequeue from en empty queue")

result = self.arr[self.front]

self.arr[self.front] = None

self.front = (self.front+1) % len(self.arr)

self.size -= 1

# 如果元素个数少于容积的1/4并且元素个数

if self.size < self.get_capaticty() // 4 and self.get_capaticty() > 1:

self.resize(self.get_capaticty() // 2)

return result

def resize(self, new_capacity):

new_arr = [None] * (new_capacity+1)

for i in range(self.size):

new_arr[i] = self.arr[(i+self.front) % len(self.arr)]

self.arr = new_arr

self.front = 0

self.tail = self.size

def main(self):

loop_queue = LoopQueue()

start_time = datetime.datetime.now()

for i in range(5000000):

loop_queue.enqueue(i)

print('n---------测试enqueue----------')

print('Loop_Queue： size = {0} , capacity = {1}n'.format(loop_queue.get_size(), loop_queue.get_capaticty()), loop_queue)

print('is_empty：', loop_queue.is_empty())

print('is_full：', loop_queue.is_full())

print('get_front：', loop_queue.get_front())

for i in range(5000000):

loop_queue.dequeue()

last_time = datetime.datetime.now() - start_time

print('n---------测试dequeue----------')

print('Loop_Queue： size = {0} , capacity = {1}n'.format(loop_queue.get_size(), loop_queue.get_capaticty()),

loop_queue)

print('is_empty：', loop_queue.is_empty())

print('is_full：', loop_queue.is_full())

print('get_front：', loop_queue.get_front())

print('Loop_Queue运行时间：', last_time)

if __name__ == '__main__':

loop_queue = LoopQueue()

loop_queue.main()

与List，python自带的Queue模块进行运行速度的对比

自己实现的循环队列

出入队各5000000次，测试运行时间

def main(self):

loop_queue = LoopQueue()

start_time = datetime.datetime.now()

for i in range(5000000):

loop_queue.enqueue(i)

print('n---------测试enqueue----------')

print('Loop_Queue： size = {0} , capacity = {1}n'.format(loop_queue.get_size(), loop_queue.get_capaticty()), loop_queue)

print('is_empty：', loop_queue.is_empty())

print('is_full：', loop_queue.is_full())

print('get_front：', loop_queue.get_front())

for i in range(5000000):

loop_queue.dequeue()

last_time = datetime.datetime.now() - start_time

print('n---------测试dequeue----------')

print('Loop_Queue： size = {0} , capacity = {1}n'.format(loop_queue.get_size(), loop_queue.get_capaticty()),

loop_queue)

print('is_empty：', loop_queue.is_empty())

print('is_full：', loop_queue.is_full())

print('get_front：', loop_queue.get_front())

print('Loop_Queue运行时间：', last_time)

image.png

Python List

由于实在太慢，将出入队改为各1000000次...

import datetime

a = []

start = datetime.datetime.now()

for i in range(1000000):

a.append(i)

for i in range(1000000):

a.remove(i)

last_time = datetime.datetime.now() - start

print(a)

print(last_time)

image.png

Python Queue

同样是出入队各5000000次

image.png