今天小编给大家分享一下java怎么实现环形队列的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。
1、普通队列存在什么问题?
队列大家都知道,有几个重要的属性:
空队列的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、环形队列实现思路:
环形队列中的几个重要属性:
下面是环形队列的一些算法:
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元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4602675/blog/4617238