【数据结构】环形队列

环形队列

1. 定义

环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。

其实现主要分为两种情况：

1. 浪费空间法
2. 记录空间法

2. 实现

实现要考虑的是成员变量

2.1 记录空间法

使用used标识当前存储了多少元素，如果为空，那么就将head移到0位置处，如果满了，那么就将tail移到0位置处

1. 入队

队列是从队尾入，队头出，所以就是在tail的位置入队，每入一个元素就将tail++，当满的时候就将tail恢复到队头。

普通情况：

队列满了：

这时就需要tail=0，等待某个时候有元素出队，这个时候新插入的元素就又能在tail的位置进行插入。

---

出队操作与入队操作对称，同理。

2. 代码实现

package MyCircleQueue;public class CircleQueue {int size = 5;// 队列最大容量int used = 0;// 队列已使用元素int[] data = new int[size];// 存储队列数据int tail = 0, head = 0;// 队列头尾指针public void offer(int val) {// 满了if (used == size) {tail = 0;System.out.println("满了");return;}// 没满data[tail++] = val;used++;System.out.println("存入"+val);}public int poll() {if (used == 0) {head = 0;System.out.println("空了");return -1;}int ret = data[head++];used--;System.out.println("取出："+ret);return ret;}
}

2.2 浪费空间法

在这种方式中，我们只使用头尾两个指针进行计算，并将 head = tail 的情况记作空，将 (tail+1)%size = head 的情况记作满。

2.2.1实现代码：

package MyCircleQueue;public class CircleQueue2 {int size = 5;int[] data = new int[size];int head= 0, tail = 0;public void offer(int val) {if ((tail+1) % size == head) {System.out.println("满了");return;}data[tail++] = val;System.out.println("入队:"+val);}public int poll() {if (head == tail) {System.out.println("空了");return -1;}int ret = data[head++];System.out.println("出队:"+ret);return ret;}
}

3. 测试代码：

package MyCircleQueue;public class Test {public static void main(String[] args) {CircleQueue queue = new CircleQueue();for (int i = 0; i < 10; i++) {queue.offer(i);}for (int i = 0; i < 10; i++) {int ret = queue.poll();}}
}

4. 结论

环形队列分为两种实现方式：

方法	满的标记	空的标记
浪费空间法	(tail+1)%size == head	head == tail
标记长度法	used == size	used == 0

其中推荐使用标记长度法。