Question

循环队列-实现

Answer 1

姓名：张钰 学号：21011210154 学院：通信工程学院

【嵌牛导读】循环队列是对前文提出的简单队列的改进，能减少对存储空间的浪费。

【嵌牛鼻子】循环队列

【嵌牛提问】循环队列如何实现

【嵌牛正文】

循环队列也是一种线性数据结构，其操作表现基于先进先出原则，并且队尾被连接在队首之后以形成一个循环。循环队列的一个好处是可以利用这个队列之前用过的空间。在上文提出的队列中，只要队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值，减少对存储空间的浪费。

我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置，来实现循环队列，基本思路如下：

1、队列为空状态时，两个指针 head = tail = -1

2、入队操作：如果入队前是空的，则将head 和 tail 都向右移一位，使得下标变为为0；否则只需右移tail

3、出队操作：如果出队时队列不为空，且只剩最后一个元素，即head == tail，则令head = tail = -1；否则只需右移head

4、队列首元素：只要队不为空，head指向队首元素

5、队列尾元素：只要队不为空，tail指向队尾元素

6、判定队列为空：指针 head = tail = -1，此时为空

7、判定队列为满：tail右移发现与head重合，则没有地方放入新的元素，此时为满

python实现：