循環佇列的優點
普通隊列出隊操作開銷大：在出隊操作時，索引為0後面的所有元素，都需要往前移動一位，元素越多，消耗的時間也越多，時間複雜度為O(N)。
循環隊列的邏輯：
1、當元素較少時（tail位置在front後面），循環隊列與普通隊列出隊操作一樣，入隊的元素將會放在tail的位置上，隨後執行tail 操作；出隊時front位置上的元素將會置null，隨後執行front 操作；此時仍能保持著tail位置在front後面的狀態，如下圖中所示：
2、當元素繼續添加，最後一個元素將放到索引為7的位置，此時tail位置將會移動到隊首前面索引為0的位置上，此時tail在陣列的索引為變為：(tail 1 )% capacity如下圖所示：
程式碼實作：（相關影片教學分享：java影片教學）
package dataStructure.chapter3;
/**
* @Author: zjtMeng
* @Date: 2019/12/28 20:13
* @Version 1.0
*/
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front,tail;
private int size;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity+1];
}
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length-1;
}
/**
* 循环队列入队操作
* @param e
*/
@Override
public void enqueue(E e) {
//循环队列元素满的判断条件,如果满了就进行扩容操作，扩大两倍
if ((tail+1)%data.length == front)
resize(2 * getCapacity());
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
/**
* 循环队列扩容
* @param newCapacity
*/
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity+1];
//循环队列第一种遍历方式
for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素与data[]中的元素，一方面存在着front的偏移量，另一方面，data[]中的元素，
//可能在有部分处于front前面，因此此处采用对数组长度取余，来判断元素的位置
newData[i] = data[(i+front)%data.length];
}
data = newData;
front =0;
tail = size;
}
@Override
public E dequeue() {
//首先判断队列是否为空，如果为空则抛出异常
if (isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
//引用地址需要置空，否则JVM不能及时回收空间，从而可能会出现OOM异常
data[front] = null;
front = (front + 1 )% data.length;
size--;
//如果元素数量达到队列容积的1/4，且队列容积/2 不等于0时，进行缩容操作
if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )
resize(getCapacity() / 2);
return ret;
}
/**
* 查看队首元素
* @return
*/
@Override
public E getFront() {
if (isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
@Override
public int getSize() {
return size;
}
/**
* 判断循队列是否为空
* @return
*/
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d, capacity = %d\n",size, getCapacity()));
res.append("front[");
//循环队列遍历的第二种方法
for (int i = front; i != tail; i = (i + 1) % data.length){
res.append(data[i]);
//循环队列未遍历到队尾的标志
if ((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
}以上是java實作循環隊列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
