登录
首页 >  文章 >  java教程

java怎么实现环形队列

来源:亿速云

时间:2024-04-01 13:12:38 460浏览 收藏

文章不知道大家是否熟悉?今天我将给大家介绍《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、代码实操:

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

今天带大家了解了的相关知识,希望对你有所帮助;关于文章的技术知识我们会一点点深入介绍,欢迎大家关注golang学习网公众号,一起学习编程~

声明:本文转载于:亿速云 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>