Java動態循環隊列是如何實現的
一、隊列
1.1 定義
隊列 (Queue) 是一種限定性的有序線性表，它隻允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出 (Fist In Fist Out，縮寫為FIFO)的特性。
- 在隊列中，允許插入的一端叫做隊尾(rear)；
- 允許刪除的一端則稱為隊頭(front)。
- 隊列是一個有序列表，可以用數組或是鏈表來實現。
- 遵循先進先出的原則。即:先存入隊列的數據，要先取出。
1.2 抽象數據類型
數據元素：可以是任意類型的數據，但必須屬於同一個數據對象。
關系：隊列中數據元素之間是線性關系。
基本操作:
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():隊列銷毀操作。釋放隊列的空間。
1.3 順序存儲
隊列的一種順序存儲稱為順序隊列。與順序棧類似，在隊列的順序存儲結構中，用一組地址連續的存儲單元依次存放從隊頭到隊尾的元素，如一維數組Queue[maxSize]。
二、數組隊列
由於隊列中隊頭和隊尾的位置都是動態變化的，因此需要附設兩個指針 front和 rear。
- front：指示隊頭元素在數組中的位置;
- rear：指示真實隊尾元素相鄰的下一個位置。
2.1 思路分析
- 初始化隊列時，令
front = rear = 0。 - 判斷隊空的條件：
front == rear。 - 判斷隊滿的條件：
rear == maxSize。 - 入隊時，若尾指針rear 小於隊列的最大下標
maxSize,則將數據存入rear所指的數組元素中,否則無法存入數據；然後將尾指針往後移:rear + 1。 - 出隊時，若隊列不為空，取出隊頭指針front所指的元素；然後將尾指針往後移:
front + 1。
2.2 代碼實現
定義接口方法：
/**
* 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();
}
2.3 數組隊列實現
/**
* 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("程序退出");
}
}
2.4 分析
假溢出現象
在非空順序隊列中，隊頭指針始終指向當前的隊頭元素，而隊尾指針始終指向真正隊尾元素。當rear == maxSize - 1 時，認為隊滿。但此時不一定是真的隊滿，因為隨著部分元素的出隊，數組前面會出現一些空單元，如下圖所示。由於隻能在隊尾入隊，使得上述空單元無法使用。把這種現象稱為假溢出。
問題：目前這個數組使用一次就不能用（出隊的空間），沒有達到復用的效果。可使用算法將其改造成環形隊列（取模：%）。
三、環形隊列
為瞭解決假溢出現象並使得隊列空間得到充分利用,一個較巧妙的辦法是將順序隊列的數組看成一個環狀的空間，即規定最後一個單元的後繼為第一個單元，我們形象地稱之為循環隊列。
3.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。
下圖給出瞭循環隊列的幾種情況：
3.2 代碼實現
/**
* 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("程序退出");
}
}
3.3 分析
相比數組隊列來說，循環隊列解決瞭數組空間不能再次利用的問題。但依然存在一些問題：
- 當隊列真的滿的時候就不能再進行入隊操作瞭。但是從我們常用的
ArrayList來分析，在存儲空間允許的條件下是可以一直添加元素的。 - 當數組元素頻繁進行入隊或者出隊操作時，可能造成空間的浪費。循環隊列其實隻利用瞭有限的存儲空間，但是在最初實例化循環隊列的時候，如果空間聲明的很大，那麼會造成一定程度上的空間浪費。
- 假設，聲明一個容量為20的循環隊列，但每次入隊2個元素後，又出隊2個元素，那麼實際隻利用瞭很有限的空間，造成瞭空間浪費，但又不能聲明的空間太小，並不能保證未來每次隻入隊或者出隊2個元素。
因此，是否可以實現動態的將循環隊列進行擴容或者縮容，上述兩個問題，可以利用下面的動態循環隊列來實現。
當然，上述的數組隊列，也可以改造成動態的，但是出隊元素的空間依然會浪費，所以沒必要進行實現。
四、動態循環隊列
為瞭解決循環隊列，隊滿不能入隊，以及頻繁入隊出隊引起的空間浪費，而引出動態循環隊列的概念。即在隊滿時進行擴容，在隊列元素個數下降到一定情況下進行縮容。
4.1 思路分析
- 除瞭入隊和出隊操作，其他操作均與循環隊列相同。
- 循環隊列存儲元素的數組容量變更思路：使用擴容一倍/縮容一倍的新數組接收原來循環隊列存儲的元素。接收後，將
front指針置為0；將rear指針值到最後一個元素的位置（即存儲有效元素的數量）。 - 什麼時候擴容：隊滿
- 什麼時候縮容：隊列元素隻有1/4，並且縮容後容量不為0。
- 數組容量為0時，縮容會出現異常
- 為什麼不在隊列元素隻有1/2時縮容？當數組元素為一半的時候一次添加，一次刪除，造成的一直擴容和減小的操作。
4.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動態循環隊列是如何實現的的文章就介紹到這瞭,更多相關Java動態循環隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Java基礎之數組模擬循環隊列
- java數據結構循環隊列的空滿判斷及長度計算
- Java隊列數據結構的實現
- Java隊列篇之實現數組模擬隊列及可復用環形隊列詳解
- java數據結構基礎:順序隊列和循環隊列