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中文網其他相關文章！