在正式进行循环队列学习之前, 我们先来看看在顺序队列中删除队首元素出现的问题
(1)设一个容量为 capacity=8,size=5(a,b,c,d,e)的数组, 左侧为队首, 右侧为队尾.
image.PNG
(2)出队一个元素后, 需整体往前移动一位
-1 出队
image.PNG
-2 整体前移一位
image.PNG
关于该种操作方式我们很容易得出时间复杂度为 O(n).
这时我们就想可不可以在出队元素后, 整体元素不往前移, 而是在数组中记下队首 front 是谁, 同时队尾 tail 指向在下一次元素入队时的位置, 这样当再有出队时只需要维护一下 front 的指向即可, 而不需移动元素. 就这样我们就有了循环队列的情况.
image.PNG
2. 循环队列原理
(1)初始, 数组整体为空时, 队首 front, 队尾 tail 指向同一个位置 (数组索引为 0 的地方) 也即 front==tail 时队列为空
image.PNG
(2)当往数组中添加元素后,
image.PNG
(3)出队一个元素, front 指向新的位置
image.PNG
(4)入队元素, tail 叠加
image.PNG
(5)当 tail 不能再增加时, 数组前面还有空余, 此时循环队列就该出场了.
image.PNG
此时数组应该变为这样:
image.PNG
在往数组中添加一个元素:
image.PNG
这样数组就已经满了(tail+1==front 队列满), 开始出发扩容操作.[capacity 中, 浪费一个空间] .
为了 tail 能返回到数组的前面位置, 将队列满的表达式变为 [(tail+1)%c==front] 这样数组就可以循环移动了.
3. 循环队列代码实现
新建一个类 LoopQueue 并实现接口 Queue.
-1: 接口 Queue 代码如下:
- package Queue;
- public interface Queue<E> {
- // 获取队列中元素个数
- int getSize();
- // 队列中元素是否为空
- boolean isEmpty();
- // 入队列
- void enqueue(E e);
- // 出队列
- E dequeue();
- // 获取队首元素
- E getFront();
- }
-2:LoopQueue 相关代码:
- package Queue;
- // 循环队列
- public class LoopQueue<E> implements Queue<E> {
- private E[] data;
- private int front, tail;
- private int size;// 队列中元素个数
- // 构造函数, 传入队列的容量 capacity 构造函数
- public LoopQueue(int capacity) {
- data = (E[]) new Object[capacity + 1];// 浪费与一个空间
- front = 0;
- tail = 0;
- size = 0;
- }
- // 无参构造函数, 默认队列的容量 capacity=10
- public LoopQueue() {
- this(10);
- }
- // 真正容量
- public int getCapacity() {
- return data.length - 1;
- }
- // 队列是否为空
- @Override
- public boolean isEmpty() {
- return front == tail;
- }
- // 队列中元素个数
- @Override
- public int getSize() {
- return size;
- }
- // 入队列操作
- @Override
- public void enqueue(E e) {
- if ((tail + 1) % data.length == front) {// 队列已满, 需要扩容
- resize(getCapacity() * 2);
- }
- data[tail] = e;
- tail = (tail + 1) % data.length;
- size++;
- }
- // 出队操作
- @Override
- public E dequeue() {
- if (isEmpty()) {
- throw new IllegalArgumentException("队列为空");
- }
- E ret = data[front];
- data[front] = null;// 手动释放
- front = (front + 1) % data.length;
- size--;
- if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
- resize(getCapacity() / 2);
- }
- return ret;
- }
- // 获取队首元素
- @Override
- public E getFront() {
- if (isEmpty()) {
- throw new IllegalArgumentException("队列为空");
- }
- return data[front];
- }
- // 改变容量
- private void resize(int newCapacity) {
- E[] newData = (E[]) new Object[newCapacity + 1];
- for (int i = 0; i <size; i++) {
- newData[i] = data[(front + i) % data.length];// 循环数组防止越界
- }
- data = newData;
- front = 0;
- tail = size;
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- res.append(String.format("Queue:size=%d, capacity=%d\n", size, getCapacity()));
- res.append("front [");
- for (int i = front; i != tail; i = (i + 1) % data.length) {
- res.append(data[i]);
- if ((i + 1) % data.length != tail) {
- res.append(",");
- }
- }
- res.append("] tail");
- return res.toString();
- }
- }
在关于 LoopQueue 类中需要注意的:
(1)data = (E[]) new Object[capacity + 1];// 浪费与一个空间解释
+1 是 capacity 需要浪费一个空间, 故在实例化是多加 1
(2)data.length - 1;
真正的容量是 data.length-1, 这是由于有一个空间是浪费的.
(3)tail = (tail + 1) % data.length;
为了保证入队是循环操作, tail 值的变化规律为
(4)newData[i] = data[(front + i) % data.length];// 循环数组防止越界
取余操作是为了防止循环数组时越界.
-3 直接在 LoopQueue 中添加一个 main 函数进行测试, 相关代码如下:
- // 测试用例
- public static void main(String[] args) {
- LoopQueue<Integer> queue = new LoopQueue<Integer>();
- for (int i = 0; i < 10; i++) {
- queue.enqueue(i);
- System.out.println(queue);
- if(i%3==2){// 每添加 3 个元素出队列一个
- queue.dequeue();
- System.out.println(queue);
- }
- }
- }
结果为:
image.PNG
4. 循环队列时间复杂度
image.PNG
到此我们就实现了一个循环队列操作, 解决了在顺序队列中出队时的时间复杂度为 O(n)的情况, 在循环队列中出队的时间复杂度为 O(1).
源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java
来源: http://www.jianshu.com/p/c466a68d45b4