栈是先入后出，与之相反的是队列，队列是先进先出的线性结构。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。
图1 队列的定义 队列的存储结构中使用的最多的是循环队列。循环队列包括两个指针， front 指针指向队头元素， rear 指针指向队尾元素的下一个位置。 队列为空的判断条件是： front == rear
队列满的判断条件是： (rear 1)%maxsize == front
队列长度的计算公式： (rear-front maxsize)%maxsize
具体的python实现代码如下：
代码语言：javascript复制class SqQueue(object):
def __init__(self, maxsize):
self.queue = [None] * maxsize
self.maxsize = maxsize
self.front = 0
self.rear = 0
# 返回当前队列的长度
def QueueLength(self):
return (self.rear - self.front self.maxsize) % self.maxsize
# 如果队列未满，则在队尾插入元素，时间复杂度O(1)
def EnQueue(self, data):
if (self.rear 1) % self.maxsize == self.front:
print("The queue is full!")
else:
self.queue[self.rear] = data
# self.queue.insert(self.rear,data)
self.rear = (self.rear 1) % self.maxsize
# 如果队列不为空，则删除队头的元素,时间复杂度O(1)
def DeQueue(self):
if self.rear == self.front:
print("The queue is empty!")
else:
data = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front 1) % self.maxsize
return data
# 输出队列中的元素
def ShowQueue(self):
for i in range(self.maxsize):
print(self.queue[i],end=',')
print(' ')
# 测试程序
if __name__ == "__main__":
# 建立大小为15的循环队列
q = SqQueue(15)
# 0~9入队列
for i in range(10):
q.EnQueue(i)
q.ShowQueue()
# 删除队头的5个元素：0~4
for i in range(5):
q.DeQueue()
q.ShowQueue()
# 从队尾增加8个元素：0~7
for i in range(8):
q.EnQueue(i)
q.ShowQueue()程序输出的结果为：
0,1,2,3,4,5,6,7,8,9,None,None,None,None,None, None,None,None,None,None,5,6,7,8,9,None,None,None,None,None, 5,6,7,None,None,5,6,7,8,9,0,1,2,3,4,
