前言

• 用python实现队列结构可以借助现成的库（Queue）来实现，但是为了理解队列数据结构，决定自己手撸一遍代码。
• 普通的顺序存储队列可以借助Python的列表来实现，只要控制入队和出队的方向即可，在列表满的时候也能动态地分配空间。假设仅有一个有限的存储空间，循环队列则能够更好地利用起剩余空间。

1 循环队列原理

1.1 举个栗子

以一个有5个单位空间的循环队列为例：

1. 首先连接普通队列的首尾，使其成为环状，为了区分首尾，要设置两个索引，front和rear，分别指向当前的队头和队尾。如果front和rear指向同一个数据front=rear，则表明队列为空。需要注意的是rear指向的数据空间必须为None，也就是说队尾不要填数据，原因后面再说。

2. 插入数据后，rear向后移动一位：

3. 当数据插满后，如下图所示，队尾为空：

4. 为了能够插入新数据，就必须出队数据，腾出空间，后续能够让rear指过去。注意front要向后移动：

5. 此时重点来了，插入数据99，入队数据会填充到空位，同时rear循环到第一个位置：

6. 而之后的过程以此类推，先腾出空间，再入队数据，实现了空间的充分利用。

1.2 判别条件

从刚才的例子中可以发现，判别队列是否为空或满是关键，先给出判别依据：

• 判断队列是否为空：front = rear
• 判断队列是否已满：(rear+1) % maxsize == front（maxsize是队列长度）

判读队列是否为空较好理解，就不细说了。但是判断队列是否已满的条件非常巧妙，需要分两种情况来讨论：

1. 当front在rear之前：

代几个数字到条件里去试一试，可以发现仅当front在第一个位置且rear在最后一个位置的时候，等式成立，此时队列为满，当rear在其他位置的时候，实际上(rear+1) % maxsize等价于rear+1，此外rear在最后一个位置的时候，(rear+1) % maxsize会使得rear=0，这也就意味着rear跳到了第一个位置，巧妙地实现了循环~

2. 当front在rear之后：

同样代几个数字到条件里去试一试，可以发现只有当rear后面紧跟front时，等式成立，此时队列为满，同样的，front可以通过(front+1) % maxsize来实现循环~

• 最后再说一下，为什么rear一定要指向空，原因就在于防止判别条件front = rear失效，如果在rear位置插入数据，那么势必就会导致rear索引后移，和front索引重叠，此时队列不为空，判别条件会失效。

2 Python代码实现

2.1 创建循环队列：

根据上述的分析，创建循环队列，队列中的空位用None填充，两个索引初始为0（其他不大于maxsize的数字应该也行）

# 循环队列
class rqueue:
    def __init__(self, maxsize):
        self.queue = [None]*(maxsize)
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0
复制代码

2.2 实现入队、出队和查看

根据上面的分析思路，应该会很容易理解，这里需要说明的是"打印队列"，实现的功能是能按照先后顺序依次显示队列元素，同时不显示None

# 循环队列
class rqueue:
    def __init__(self, maxsize):
        self.queue = [None]*(maxsize)
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0

    # 入队
    def push(self, value):        
        if (self.rear+1) % self.maxsize == self.front:
            print("列表已满")
        else:
            self.queue[self.rear] = value
            self.rear = (self.rear+1) % self.maxsize

    # 出队
    def pop(self):
        if self.front == self.rear:
            print("列表为空")
        else:
            out = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front+1) % self.maxsize
            return out

    # 显示队列的结构
    def traverse(self):
        return self.queue

    # 打印队列
    def show(self):
        alist = []
        if self.front == self.rear:
            return alist
        if self.front < self.rear:
            for i in range(self.front, self.rear+1):
                if self.queue[i] != None:
                    alist.append(self.queue[i])
        else:
            for i in list(range(self.front, self.maxsize)) + list(range(0, self.rear+1)):
                if self.queue[i] != None:
                    alist.append(self.queue[i])
        return alist
复制代码

2.3 测试一下

• 首先创建一个有6个单位空间的循环队列，可以看到最后的队尾为None

# 创建队列并插满元素
a = rqueue(6)
a.push(3)
a.push(5)
a.push(0)
a.push(1)
a.push(9)
复制代码

# 查看队列结构
a.traverse()
> [3, 5, 0, 1, 9, None]
复制代码

# 打印队列
a.show()
> [3, 5, 0, 1, 9]
复制代码

• 出队两个元素后再入队两个元素，可以看到此时队头在0的位置，而队尾在98的位置

a.pop()
a.pop()
a.push(99)
a.push(98)
复制代码

# 查看队列结构
a.traverse()
> [98, None, 0, 1, 9, 99]
复制代码

# 打印队列
a.show()
> [0, 1, 9, 99, 98]
复制代码