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>

以上是java怎么实现环形队列的详细内容。更多信息请关注PHP中文网其他相关文章！