溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Java動態循環隊列怎么實現，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
隊列 (Queue) 是一種限定性的有序線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出 (Fist In Fist Out，縮寫為FIFO)的特性。
在隊列中，允許插入的一端叫做隊尾(rear)；
允許刪除的一端則稱為隊頭(front)。
隊列是一個有序列表，可以用數組或是鏈表來實現。
遵循先進先出的原則。即:先存入隊列的數據，要先取出。
數據元素：可以是任意類型的數據，但必須屬于同一個數據對象。
關系：隊列中數據元素之間是線性關系。
基本操作:
1.初始化操作。使用構造方法設置一個空隊列。
2.isEmpty():判空操作。若隊列為空，則返回TRUE，否則返回FALSE。
3.isFull():判滿操作。若隊列為滿,則返回TRUE，否則返回FALSE。
4.getSize():獲取隊列元素個數。
5.add(E e):進隊操作。在隊列Q的隊尾插入e。如果隊滿，拋出異常。
6.poll():出隊操作。使隊列Q的隊頭元素出隊，并用e返回其值。如果隊空，拋出異常。
7.getHead ():取隊頭元素操作。用e取得隊頭元素的值。如果隊列為空，則返回null。
8.clear():隊列置空操作。將隊列Q置為空隊列。
9.destroy():隊列銷毀操作。釋放隊列的空間。
隊列的一種順序存儲稱為順序隊列。與順序棧類似，在隊列的順序存儲結構中，用一組地址連續的存儲單元依次存放從隊頭到隊尾的元素，如一維數組Queue[maxSize]。
由于隊列中隊頭和隊尾的位置都是動態變化的，因此需要附設兩個指針 front和 rear。
front：指示隊頭元素在數組中的位置;
rear：指示真實隊尾元素相鄰的下一個位置。
初始化隊列時，令front = rear = 0。
判斷隊空的條件：front == rear。
判斷隊滿的條件：rear == maxSize。
入隊時，若尾指針rear 小于隊列的最大下標 maxSize,則將數據存入rear所指的數組元素中,否則無法存入數據；然后將尾指針往后移: rear + 1。
出隊時，若隊列不為空，取出隊頭指針front所指的元素；然后將尾指針往后移: front + 1。
定義接口方法：
/**
* description:自定義隊列接口
*
* @author RenShiWei
* Date: 2021/5/29 20:45
**/
public interface Queue<E> {
/**
* @return 是否隊空
*/
boolean isEmpty();
/**
* @return 是否隊滿
*/
boolean isFull();
/**
* @return 隊列的可承載元素個數
*/
int getCapacity();
/**
* @return 隊列元素個數
*/
int getSize();
/**
* 隊尾入隊
*
* @param e 入隊元素
*/
void add(E e);
/**
* 隊首出隊
*
* @return 出隊元素
*/
E poll();
/**
* 獲取隊首元素
*
* @return 隊首元素
*/
E getHead();
}/**
* description:數組隊列
*
* @author RenShiWei
* Date: 2021/5/29 20:41
**/
public class ArrayQueue<E> implements Queue<E> {
/** 表示可存儲元素的最大容量 */
private int maxSize;
/** 隊列頭 */
private int front;
/** 隊列尾 */
private int rear;
/** 該數據用于存放數據，模擬隊列 */
private E[] data;
/**
* 初始化隊列
*
* @param arrMaxSize 初始隊列最大容量
*/
@SuppressWarnings("unchecked")
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
data = (E[]) new Object[maxSize];
front = 0;
rear = 0;
}
/**
* @return 是否隊空
*/
@Override
public boolean isEmpty() {
return front == rear;
}
/**
* @return 是否隊滿
*/
@Override
public boolean isFull() {
return rear == maxSize;
}
/**
* @return 隊列元素個數
*/
@Override
public int getSize() {
return rear - front;
}
/**
* 隊尾入隊
*
* @param e 入隊元素
*/
@Override
public void add(E e) {
if (isFull()) {
throw new IllegalArgumentException("隊列已滿，不能入隊！");
}
data[rear++] = e;
}
/**
* 隊首出隊
*
* @return 出隊元素
*/
@Override
public E poll() {
if (isEmpty()) {
throw new IllegalArgumentException("隊列為空，不能出隊！");
}
//出隊位置置null
E temp = data[front];
data[front++] = null;
return temp;
}
/**
* 獲取隊首元素
* 如果隊空，返回null
*
* @return 隊首元素
*/
@Override
public E getHead() {
return data[front];
}
/**
* @return 隊列的可承載元素個數
*/
@Override
public int getCapacity() {
return data.length - 1;
}
/**
* @return 隊列的有效容量（未使用的空間數量）
*/
public int getEmptyCount() {
return maxSize - rear;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for (int i = front; i < rear; i++) {
res.append(data[i]);
if (i != rear - 1) {
res.append(", ");
}
}
res.append("] rear");
return res.toString();
}
/**
* 隊列測試
*/
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>(5);
Scanner sc = new Scanner(System.in);
char c;
boolean loop = true;
while (loop) {
System.out.println("s(toString):輸出隊列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加數據到隊列");
System.out.println("p(poll):從隊列取出數據");
System.out.println("h(getHead):查看隊列頭的數據");
System.out.println("n(isEmpty):是否隊空");
System.out.println("f(isFull):是否隊滿");
c = sc.next().charAt(0);
switch (c) {
case 's':
System.out.println("當前隊列：" + queue.toString() + "\t元素個數：" + queue.getSize() + "\t有效容量：" + queue.getEmptyCount());
break;
case 'e':
sc.close();
loop = false;
break;
case 'a':
System.out.println("請輸入一個整數");
queue.add(sc.nextInt());
break;
case 'p':
System.out.printf("出隊元素：%d\n", queue.poll());
break;
case 'h':
System.out.printf("隊首元素：%d\n", queue.getHead());
break;
case 'n':
System.out.println("隊空：" + queue.isEmpty());
break;
case 'f':
System.out.println("隊滿：" + queue.isFull());
break;
default:
break;
}
}
System.out.println("程序退出");
}
}假溢出現象
在非空順序隊列中，隊頭指針始終指向當前的隊頭元素，而隊尾指針始終指向真正隊尾元素。當rear == maxSize - 1 時，認為隊滿。但此時不一定是真的隊滿，因為隨著部分元素的出隊，數組前面會出現一些空單元，如下圖所示。由于只能在隊尾入隊，使得上述空單元無法使用。把這種現象稱為假溢出。
問題：目前這個數組使用一次就不能用（出隊的空間），沒有達到復用的效果。可使用算法將其改造成環形隊列（取模：%）。
為了解決假溢出現象并使得隊列空間得到充分利用,一個較巧妙的辦法是將順序隊列的數組看成一個環狀的空間，即規定最后一個單元的后繼為第一個單元，我們形象地稱之為循環隊列。
初始化隊列時，令front = rear = 0。front指向隊列的第一個元素，rear指向隊列最后一個元素的后一個位置（希望損失一個位置作為約定，用來區分隊空和隊滿）。
判斷隊空的條件：front == rear。
判斷隊滿的條件：(rear + 1) % maxSize == front。
隊列中的元素個數：(rear + maxSize - front) % maxSize。
入隊時，將數據存入rear所指的數組元素中，指針變化：rear = ( rear+1) % maxSize。
出隊時，將數據存入front所指的數組元素中，指針變化：front = ( front+1 ) % maxSize。
下圖給出了循環隊列的幾種情況：
/**
* description:循環隊列
*
* @author RenShiWei
* Date: 2021/5/30 16:38
**/
public class LoopQueue<E> implements Queue<E> {
/** 存儲元素 數組的長度（有效長度需要-1） */
private int maxSize;
/** 隊列頭 */
private int front;
/** 隊列尾 */
private int rear;
/** 該數據用于存放數據，模擬隊列 */
private E[] data;
/**
* 初始化環形隊列
*
* @param arrMaxSize 初始隊列容量
*/
@SuppressWarnings("unchecked")
public LoopQueue(int arrMaxSize) {
//循環隊列需要有意識浪費一個空間
maxSize = arrMaxSize + 1;
data = (E[]) new Object[maxSize];
}
/**
* @return 是否隊空
*/
@Override
public boolean isEmpty() {
return front == rear;
}
/**
* @return 是否隊滿
*/
@Override
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
/**
* @return 隊列的可承載元素個數
*/
@Override
public int getCapacity() {
return data.length - 1;
}
/**
* @return 隊列元素個數
*/
@Override
public int getSize() {
return (rear + maxSize - front) % maxSize;
}
/**
* 隊尾入隊
*
* @param e 入隊元素
*/
@Override
public void add(E e) {
if (isFull()) {
throw new IllegalArgumentException("隊列已滿，不能入隊！");
}
data[rear] = e;
//rear指針后移一位
rear = (rear + 1) % maxSize;
}
/**
* 隊首出隊
*
* @return 出隊元素
*/
@Override
public E poll() {
if (isEmpty()) {
throw new IllegalArgumentException("隊列為空，不能出隊！");
}
E temp = data[front];
//出隊位置置null
data[front] = null;
//front指針后移一位
front = (front + 1) % maxSize;
return temp;
}
/**
* 獲取隊首元素
* 如果隊空，返回null
*
* @return 隊首元素
*/
@Override
public E getHead() {
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
res.append("front [");
for (int i = front; i != rear; i = (i + 1) % data.length) {
res.append(data[i]);
if ((i + 1) % data.length != rear) {
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
/**
* 隊列測試
*/
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>(5);
Scanner sc = new Scanner(System.in);
char c;
boolean loop = true;
while (loop) {
System.out.println("s(toString):輸出隊列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加數據到隊列");
System.out.println("p(poll):從隊列取出數據");
System.out.println("h(getHead):查看隊列頭的數據");
System.out.println("n(isEmpty):是否隊空");
System.out.println("f(isFull):是否隊滿");
c = sc.next().charAt(0);
switch (c) {
case 's':
System.out.println("當前隊列：" + queue.toString());
break;
case 'e':
sc.close();
loop = false;
break;
case 'a':
System.out.println("請輸入一個整數");
queue.add(sc.nextInt());
break;
case 'p':
System.out.printf("出隊元素：%d\n", queue.poll());
break;
case 'h':
System.out.printf("隊首元素：%d\n", queue.getHead());
break;
case 'n':
System.out.println("隊空：" + queue.isEmpty());
break;
case 'f':
System.out.println("隊滿：" + queue.isFull());
break;
default:
break;
}
}
System.out.println("程序退出");
}
}相比數組隊列來說，循環隊列解決了數組空間不能再次利用的問題。但依然存在一些問題：
當隊列真的滿的時候就不能再進行入隊操作了。但是從我們常用的ArrayList來分析，在存儲空間允許的條件下是可以一直添加元素的。
當數組元素頻繁進行入隊或者出隊操作時，可能造成空間的浪費。循環隊列其實只利用了有限的存儲空間，但是在最初實例化循環隊列的時候，如果空間聲明的很大，那么會造成一定程度上的空間浪費。
假設，聲明一個容量為20的循環隊列，但每次入隊2個元素后，又出隊2個元素，那么實際只利用了很有限的空間，造成了空間浪費，但又不能聲明的空間太小，并不能保證未來每次只入隊或者出隊2個元素。
因此，是否可以實現動態的將循環隊列進行擴容或者縮容，上述兩個問題，可以利用下面的動態循環隊列來實現。
當然，上述的數組隊列，也可以改造成動態的，但是出隊元素的空間依然會浪費，所以沒必要進行實現。
為了解決循環隊列，隊滿不能入隊，以及頻繁入隊出隊引起的空間浪費，而引出動態循環隊列的概念。即在隊滿時進行擴容，在隊列元素個數下降到一定情況下進行縮容。
除了入隊和出隊操作，其他操作均與循環隊列相同。
循環隊列存儲元素的數組容量變更思路：使用擴容一倍/縮容一倍的新數組接收原來循環隊列存儲的元素。接收后，將front指針置為0；將rear指針值到最后一個元素的位置（即存儲有效元素的數量）。
什么時候擴容：隊滿
什么時候縮容：隊列元素只有1/4，并且縮容后容量不為0。
數組容量為0時，縮容會出現異常
為什么不在隊列元素只有1/2時縮容？當數組元素為一半的時候一次添加，一次刪除，造成的一直擴容和減小的操作。
/**
* description:動態循環
*
* @author RenShiWei
* Date: 2021/5/30 17:06
**/
public class DynamicLoopQueue<E> implements Queue<E> {
/** 存儲元素 數組的長度（有效長度需要-1） */
private int maxSize;
/** 隊列頭 */
private int front;
/** 隊列尾 */
private int rear;
/** 該數據用于存放數據，模擬隊列 */
private E[] data;
/**
* 初始化環形隊列
*
* @param arrMaxSize 初始隊列容量
*/
@SuppressWarnings("unchecked")
public DynamicLoopQueue(int arrMaxSize) {
//循環隊列需要有意識浪費一個空間
maxSize = arrMaxSize + 1;
data = (E[]) new Object[maxSize];
}
/**
* @return 是否隊空
*/
@Override
public boolean isEmpty() {
return front == rear;
}
/**
* @return 是否隊滿
*/
@Override
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
/**
* @return 隊列的可承載元素個數
*/
@Override
public int getCapacity() {
return data.length - 1;
}
/**
* @return 隊列元素個數
*/
@Override
public int getSize() {
return (rear + maxSize - front) % maxSize;
}
/**
* 隊尾入隊
*
* @param e 入隊元素
*/
@Override
public void add(E e) {
if (isFull()) {
//隊滿不再進行報錯，而是進行動態擴容
resize(getCapacity() * 2);
}
data[rear] = e;
//rear指針后移一位
rear = (rear + 1) % maxSize;
}
/**
* 隊首出隊
*
* @return 出隊元素
*/
@Override
public E poll() {
if (isEmpty()) {
throw new IllegalArgumentException("隊列為空，不能出隊！");
}
E temp = data[front];
//出隊位置置null
data[front] = null;
//front指針后移一位
front = (front + 1) % maxSize;
//當數組實際元素減小到空間的一半的時候，對其進行縮小
//if(size == data.length / 2)
/*
解決當一半的時候一次添加，一次刪除，造成的一直擴容和減小的操作，
增加必須要擴容，所以可以讓縮容變得更懶時在進行，即1/4時
data.length / 2 != 0防止數組大小最后變成0，造成異常
*/
if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return temp;
}
/**
* 獲取隊首元素
* 如果隊空，返回null
*
* @return 隊首元素
*/
@Override
public E getHead() {
return data[front];
}
/**
* 擴容方法
*
* @param newCapacity 擴容后的隊列大小
*/
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
//有多個元素循環多少次
for (int i = 0; i < getSize(); i++) {
//循環隊列會發生偏移，重新賦值給新數組
newData[i] = data[(i + front) % data.length];
}
data = newData;
maxSize = data.length;
//重置指針
front = 0;
rear = getSize();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
res.append("front [");
for (int i = front; i != rear; i = (i + 1) % data.length) {
res.append(data[i]);
if ((i + 1) % data.length != rear) {
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
/**
* 隊列測試
*/
public static void main(String[] args) {
DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3);
Scanner sc = new Scanner(System.in);
char c;
boolean loop = true;
while (loop) {
System.out.println("s(toString):輸出隊列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加數據到隊列");
System.out.println("p(poll):從隊列取出數據");
System.out.println("h(getHead):查看隊列頭的數據");
System.out.println("n(isEmpty):是否隊空");
System.out.println("f(isFull):是否隊滿");
c = sc.next().charAt(0);
switch (c) {
case 's':
System.out.println("當前隊列：" + queue.toString());
break;
case 'e':
sc.close();
loop = false;
break;
case 'a':
System.out.println("請輸入一個整數");
queue.add(sc.nextInt());
break;
case 'p':
System.out.printf("出隊元素：%d\n", queue.poll());
break;
case 'h':
System.out.printf("隊首元素：%d\n", queue.getHead());
break;
case 'n':
System.out.println("隊空：" + queue.isEmpty());
break;
case 'f':
System.out.println("隊滿：" + queue.isFull());
break;
default:
break;
}
}
System.out.println("程序退出");
}
}關于“Java動態循環隊列怎么實現”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
