目标
用python实现循环队列，与python list以及python的Queue模块进行运行速度上的对比
队列：
顾名思义，可以将它理解为现实生活中的排队，我们去KFC排队点餐，永远都是先排队的先点餐，后排队的后点餐（如果世界美好，没人插队）
对于队首：比如现在处于队首的是小明，排在小明后面的是小红，小明点完了餐，离开了队伍，排在小明后面的所有顾客前进一步，此时小红就成了队首
对于队尾：比如现在处于队尾的是大雄，这时来了一个胖虎，由于世界和平，不许插队，胖虎只能乖乖排在大雄后面，队尾就变成了胖虎
可以看到，入队的时间复杂度为O(1)，出队以后，为了维护队列的队首，后面所有成员都需要往前挪一位，此时时间复杂度为O(n)，这种效率显然是不可以接受的，那么能不能不让所有成员都往前挪一位呢？因此就有了循环队列
循环队列：
对于循环队列，我们需要定义一个变量（front）指向队首，同样需要定义（tail）指向下一个元素入队的位置
当队列为空时，front == tail
对于队首：比如现在处于队首的是小明，front就指向小明，小明点完了餐，离开了队伍，排在小明后面的是小红，那么就将front指向小红（front += 1）。
对于队尾：比如现在处于队尾的是大雄，tail就指向大雄后一个位置，这时来了一个胖虎，由于世界和平，不许插队，胖虎只能乖乖排在大雄后面，队尾就变成了胖虎后一个位置，此时tail指向胖虎后一个位置（tail += 1）
乍一看，似乎不将后面所有成员往前挪，只需维护一下front的指向（front += 1）就可以保证队首，但是我们可以想象下，如果一直只有出队操作，却没有入队操作，在这种情况下，会发生什么？
根据队列的特性，如果我们需要再添加成员，只能在胖虎后面添加了，那么胖虎前面的这一打空间很显然就浪费了。
然而事实上并不像看到的那么简单，我们不仅仅是浪费了空间，由于这个队列是基于list实现的，所以这个队列实际上是有一个初始容量存在的，不过我们平时使用python list的时候是看不到的（关于python list的底层实现，这里有篇伯乐在线的文章：http://python.jobbole.com/82549/），当我们将元素入队的时候，如果元素个数达到了这个初始容量，即可判断队列为满，此时如果将元素入队，就需要进行扩容，以便装下更多的元素，同理，若元素出队较多，元素个数降低到某个程度（我们可以自己定义），就进行缩容，以此节省空间，下图是python list的列表空间分配策略：
OK，现在假设胖虎所在的队列已经满了，由于只能往后面添加元素，也就是说，哪怕队列里只有一个胖虎，我们也要进行扩容，扩容的原理是重新定义一个容量更大的列表，将原列表的元素遍历赋值给新列表，这是个O(n)复杂度的操作，因此我们需要将前面浪费的空间重新利用起来，一方面减少空间的浪费，另一方面减少扩容的次数，从而提升入队操作的运行速度，这就是循环队列的意义所在了。
我们继续将元素入队，不进行扩容，当队列最后一个位置入队元素后，我们从队列最开始的位置继续入队元素
由于当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)
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)
Python Queue
同样是出入队各5000000次
