循环队列

在正式进行循环队列学习之前,我们先来看看在顺序队列中删除队首元素出现的问题

(1)设一个容量为capacity=8,size=5(a,b,c,d,e)的数组,左侧为队首、右侧为队尾。

(2)出队一个元素后,需整体往前移动一位

#出队

#2整体前移一位

关于该种操作方式我们很容易得出时间复杂度为O(n)。

这时我们就想可不可以在出队元素后,整体元素不往前移,而是在数组中记下队首front是谁,同时队尾tail指向在下一次元素入队时的位置,这样当再有出队时只需要维护一下front的指向即可,而不需移动元素。就这样我们就有了循环队列的情况。

2.循环队列原理

(1)初始,数组整体为空时,队首front、队尾tail指向同一个位置(数组索引为0的地方)也即front==tail 时队列为空

(2)当往数组中添加元素后,

(3)出队一个元素,front指向新的位置

(4)入队元素,tail叠加

(5)当tail不能再增加时,数组前面还有空余,此时循环队列就该出场了。

此时数组应该变为这样:

 在往数组中添加一个元素:

这样数组就已经满了(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相关代码:

  1 package Queue;
  2 
  3 //循环队列
  4 public class LoopQueue<E> implements Queue<E> {
  5     private E[] data;
  6     private int front, tail;
  7     private int size;//队列中元素个数
  8 
  9     //构造函数,传入队列的容量capacity构造函数
 10     public LoopQueue(int capacity) {
 11         data = (E[]) new Object[capacity + 1];//浪费与一个空间
 12         front = 0;
 13         tail = 0;
 14         size = 0;
 15     }
 16 
 17     //无参构造函数,默认队列的容量capacity=10
 18     public LoopQueue() {
 19         this(10);
 20     }
 21 
 22     //真正容量
 23     public int getCapacity() {
 24         return data.length - 1;
 25     }
 26 
 27     //队列是否为空
 28     @Override
 29     public boolean isEmpty() {
 30         return front == tail;
 31     }
 32 
 33     //队列中元素个数
 34     @Override
 35     public int getSize() {
 36         return size;
 37     }
 38 
 39     //入队列操作
 40     @Override
 41     public void enqueue(E e) {
 42         if ((tail + 1) % data.length == front) {//队列已满,需要扩容
 43             resize(getCapacity() * 2);
 44         }
 45         data[tail] = e;
 46         tail = (tail + 1) % data.length;
 47         size++;
 48     }
 49 
 50     //出队操作
 51 
 53     @Override
 54     public E dequeue() {
 55         if (isEmpty()) {
 56             throw new IllegalArgumentException("队列为空");
 57         }
 58 
 59         E ret = data[front];
 60         data[front] = null;//手动释放
 61         front = (front + 1) % data.length;
 62         size--;
 63         if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
 64             resize(getCapacity() / 2);
 65         }
 66         return ret;
 67     }
 68 
 69     //获取队首元素
 70     @Override
 71     public E getFront() {
 72         if (isEmpty()) {
 73             throw new IllegalArgumentException("队列为空");
 74         }
 75         return data[front];
 76     }
 77 
 78     //改变容量
 79     private void resize(int newCapacity) {
 80         E[] newData = (E[]) new Object[newCapacity + 1];
 81         for (int i = 0; i < size; i++) {
 82             newData[i] = data[(front + i) % data.length];//循环数组防止越界
 83         }
 84         data = newData;
 85         front = 0;
 86         tail = size;
 87     }
 88 
 89 
 90     @Override
 91     public String toString() {
 92         StringBuilder res = new StringBuilder();
 93         res.append(String.format("Queue:size=%d, capacity=%d\n", size, getCapacity()));
 94         res.append("front [");
 95         for (int i = front; i != tail; i = (i + 1) % data.length) {
 96             res.append(data[i]);
 97             if ((i + 1) % data.length != tail) {
 98                 res.append(",");
 99             }
100         }
101         res.append("] tail");
102         return res.toString();
103     }
104 
105 
10121 
122 }

在关于LoopQueue类中需要注意的:

(1)第11行中的+1是capacity需要浪费一个空间,故在实例化是多加1

 data = (E[]) new Object[capacity + 1];//浪费与一个空间

(2)地24行真正的容量是data.length-1,这是由于有一个空间是浪费的。

data.length - 1;

(3)关于入队中第46行tail值的说明

为了保证入队是循环操作,tail值的变化规律为

 tail = (tail + 1) % data.length;

(4)关于82行的数据迁移操作,取余操作是为了防止循环数组时越界。

   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);
            }

        }

    }

结果为:

4.循环队列时间复杂度

到此我们就实现了一个循环队列操作,解决了在顺序队列中出队时的时间复杂度为O(n)的情况,在循环队列中出队的时间复杂度为O(1)。

源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 委托学习过程及委托、Lambda表达式和匿名方法的关系总结及事件总结

    委托是一个类,它定义了方法的类型,使得可以将方法当作另一个方法的参数来进行传递,这种将方法动态地赋给参数的做法,可以避免在程序中大量使用If-Else(Swit...

    wfaceboss
  • 链表应用--基于链表实现队列--尾指针

    在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为O(1)。

    wfaceboss
  • 数组队列

    (3)只允许在一端插入数据操作,在另一端进行删除数据操作,进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列)

    wfaceboss
  • editormd实现Markdown编辑器写文章功能

    想在项目里引入Markdown编辑器实现写文章功能,网上找到一款开源的插件editormd.js

    用户1208223
  • springboot (六) 多数据源

    IT故事会
  • 设计模式- 策略模式(Strategy Pattern)

    易兒善
  • Spring 中实现事务的方式

    Spring 并不直接支持事务,只有当数据库支持事务时,Spring 才支持事务,Spring 只不过简化了开发人员实现事务的步骤。 Spring 提供了两种...

    水货程序员
  • Java实现微信跳一跳抓包修改分数

    杨逸轩
  • 独家 | 手把手教你用R语言做回归后的残差分析(附代码)

    残差本质上是当一个给定的模型(在文中是线性回归)不完全符合给定的观测值时留下的gap。

    数据派THU
  • SpringCloud技术指南系列(十一)API网关之Zuul使用

    API网关是一个更为智能的应用服务器,它的定义类似于面向对象设计模式中的Facade模式,它的存在就像是整个微服务架构系统的门面一样,所有的外部客户端访问都需要...

    品茗IT

扫码关注云+社区

领取腾讯云代金券