温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java怎么实现环形队列

发布时间:2022-03-22 17:01:43 阅读:182 作者:iii 栏目:大数据
Java开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

今天小编给大家分享一下java怎么实现环形队列的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

1、普通队列存在什么问题?

队列大家都知道,有几个重要的属性:

  • rear:指向队列的尾巴,即最后一个元素所在的位置,初始值为-1
  • front:指向队列的头部的前一个位置,初始值也为-1
  • capacity:队列的容量

空队列的rear和front都等于-1,入队时,front不动,rear++,当 rear == capacity - 1时,队列已满;出队时,rear不动,front++,当front == rear时,队列为空。看起来很完美,但实际上有问题。假如一个队列capacity = 3,入队了三个元素,此时front = -1; rear = 2,然后再将三个元素都出队,此时front = 2, rear = 2。这时队列明明是空的,但是却不能再入队元素的,因为满足rear = capacity - 1,也就是相当于这队列是一次性的,用过之后就不能再用了,即使为空也不能再入队了,造成空间的浪费,所以环形队列就出现了。

2、环形队列实现思路:

环形队列中的几个重要属性:

  • rear:指向队列尾巴的后一个位置,初始值为0
  • front:指向队列的头部,即第一个元素所在的位置,初始值为0
  • capacity:队列的容量

下面是环形队列的一些算法:

  • 队列为空时:      front == rear
  • 队列已满时:      (rear + 1) % capacity == front
  • 获取队列元素个数:      (rear + capacity - front) % capacity
  • 入队操作时:      rear = (rear + 1) % capacity
  • 出队操作时:      front = (front + 1) % capacity;

判断队列是否已满是环形队列中最重要也是最难理解的地方。假如有一个队列capacity = 3,入队操作如下:

  • 第一个元素入队:      front = 0,因为      (rear + 1) % capacity = 1 % 3 != front,所以元素可以入队,元素入队后      rear = 1
  • 第二个元素入队:      front = 0,因为      (rear + 1) % capacity = 2 % 3 != front,所以元素可以入队,元素入队后      rear = 2
  • 第三个元素入队:      front = 0,因为      (rear + 1) % capacity = 3 % 3 == front,所以元素不能入队,队列已满;

队列容量明明是3,只入队了两个元素就告诉我队列满了?没错,这种判断队列是否已满的算法需要牺牲数组的一个空间。

现在进行出队操作:

  • 第一个元素出队:      front = 1,      rear = 2,      (rear + 1) % capacity = 3 % 3 = 0 != front

可以发现,当一个元素出队后,又满足入队条件了,所以数组空间就可以重复利用了。

3、代码实操:

public class CircleQueue<E> {    private int capacity;    private int front;    private int rear;    private Object[] arr;    public CircleQueue(int capacity){        this.capacity = capacity;        this.arr = new Object[capacity];        this.front = 0;        this.rear = 0;    }    public boolean isFull(){        return (rear + 1) % capacity == front;    }    public boolean isEmpty(){        return rear == front;    }    public void addQueue(E e){        if (isFull()){            throw new RuntimeException("队列已满,入队失败");        }        arr[rear] = e;        // rear指针后移        rear = (rear + 1) % capacity;    }    public E getQueue(){        if (isEmpty()){            throw new RuntimeException("队列为空,出队失败");        }        E val = (E) arr[front];        front = (front + 1) % capacity;        return val;    }    public int getSize(){        return (rear + capacity - front) % capacity;    }    // 遍历    public void showQueue(){        if (isEmpty()){            return;        }        for (int i = front; i < front + getSize(); i++) {            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);        }    }    public static void main(String[] args){        CircleQueue<Integer> queue = new CircleQueue<>(3);        queue.addQueue(1);        queue.addQueue(2);        queue.showQueue();        //queue.addQueue(3);        System.out.println(queue.getSize());        System.out.println(queue.getQueue());;        queue.addQueue(3);        queue.showQueue();    }}

以上就是“java怎么实现环形队列”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注亿速云行业资讯频道。

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/4602675/blog/4617238

AI

开发者交流群×