队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表，在具体应用中通常用链表或者数组来实现，队列只允许在后端（称为 rear ）进行插入操作，在前端（称为 front ）进行删除操作，队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。来自维基百科
1484793256.png
抽象数据描述如下：
ADT Queue:
Queue(self) # 创建空队列
is_empty(self) # 判断队列是否为空
enqueue(self, elem) # 将元素elem加入队列
dequeue(self) # 删除队列中最先加入的元素并将其返回
peek(self) # 取得队列中最早进入的元素，不删除
由于通过顺序表来实现队列存在假性溢出或者O(n)操作，所以这里实现通过循环表实现：
# -*- coding: UTF-8 -*-
class QueueUnderflow(ValueError):
pass
# 循环顺序表实现队列,头部删除和查看O(1),尾部加入O(1)
class SQueue(object):
def __init__(self, init_num=8):
self._len = init_num # 存储区长度
self._elems = [0] * init_num
self._head = 0 # 表头元素下标
self._num = 0 # 元素个数
def is_empty(self):
return self._num == 0
def peek(self):
if self.is_empty():
raise QueueUnderflow
return self._elems[self._head]
def dequeue(self):
if self.is_empty():
raise QueueUnderflow
result = self._elems[self._head]
self._head = (self._head + 1) % self._len
self._num -= 1
return result
def enqueue(self, elem):
if self._num == self._len:
self.__extand()
self._elems[(self._head + self._num) % self._len] = elem
self._num += 1
def __extand(self): # 当入队的时候如果 list长度不够，动态增加2倍
old_len = self._len
self._len *= 2
new_elems = [0] * self._len
for i in range(old_len):
new_elems[i] = self._elems[(self._head + i) % old_len]
self._elems, self._head = new_elems, 0
if __name__ == "__main__":
q = SQueue()
for i in range(8):
q.enqueue(i)
# for i in range(8):
# print(q.dequeue())
# print(q._num)
q.enqueue(3)
print(q._num)
