Java動態(tài)循環(huán)隊列是如何實現(xiàn)的
一、隊列
1.1 定義
隊列 (Queue) 是一種限定性的有序線性表,它只允許在表的一端插入元素,而在另一端刪除元素,所以隊列具有先進先出 (Fist In Fist Out,縮寫為FIFO)的特性。
- 在隊列中,允許插入的一端叫做隊尾(rear);
- 允許刪除的一端則稱為隊頭(front)。
- 隊列是一個有序列表,可以用數(shù)組或是鏈表來實現(xiàn)。
- 遵循先進先出的原則。即:先存入隊列的數(shù)據(jù),要先取出。
1.2 抽象數(shù)據(jù)類型
數(shù)據(jù)元素:可以是任意類型的數(shù)據(jù),但必須屬于同一個數(shù)據(jù)對象。
關(guān)系:隊列中數(shù)據(jù)元素之間是線性關(guān)系。
基本操作:
1.初始化操作。使用構(gòu)造方法設(shè)置一個空隊列。
2.isEmpty():判空操作。若隊列為空,則返回TRUE,否則返回FALSE。
3.isFull():判滿操作。若隊列為滿,則返回TRUE,否則返回FALSE。
4.getSize():獲取隊列元素個數(shù)。
5.add(E e):進隊操作。在隊列Q的隊尾插入e。如果隊滿,拋出異常。
6.poll():出隊操作。使隊列Q的隊頭元素出隊,并用e返回其值。如果隊空,拋出異常。
7.getHead ():取隊頭元素操作。用e取得隊頭元素的值。如果隊列為空,則返回null。
8.clear():隊列置空操作。將隊列Q置為空隊列。
9.destroy():隊列銷毀操作。釋放隊列的空間。
1.3 順序存儲
隊列的一種順序存儲稱為順序隊列。與順序棧類似,在隊列的順序存儲結(jié)構(gòu)中,用一組地址連續(xù)的存儲單元依次存放從隊頭到隊尾的元素,如一維數(shù)組Queue[maxSize]。
二、數(shù)組隊列
由于隊列中隊頭和隊尾的位置都是動態(tài)變化的,因此需要附設(shè)兩個指針 front和 rear。
- front:指示隊頭元素在數(shù)組中的位置;
- rear:指示真實隊尾元素相鄰的下一個位置。
2.1 思路分析
- 初始化隊列時,令
front = rear = 0
。 - 判斷隊空的條件:
front == rear
。 - 判斷隊滿的條件:
rear == maxSize
。 - 入隊時,若尾指針rear 小于隊列的最大下標(biāo)
maxSize
,則將數(shù)據(jù)存入rear所指的數(shù)組元素中,否則無法存入數(shù)據(jù);然后將尾指針往后移:rear + 1
。 - 出隊時,若隊列不為空,取出隊頭指針front所指的元素;然后將尾指針往后移:
front + 1
。
2.2 代碼實現(xiàn)
定義接口方法:
/** * description:自定義隊列接口 * * @author RenShiWei * Date: 2021/5/29 20:45 **/ public interface Queue<E> { /** * @return 是否隊空 */ boolean isEmpty(); /** * @return 是否隊滿 */ boolean isFull(); /** * @return 隊列的可承載元素個數(shù) */ int getCapacity(); /** * @return 隊列元素個數(shù) */ int getSize(); /** * 隊尾入隊 * * @param e 入隊元素 */ void add(E e); /** * 隊首出隊 * * @return 出隊元素 */ E poll(); /** * 獲取隊首元素 * * @return 隊首元素 */ E getHead(); }
2.3 數(shù)組隊列實現(xiàn)
/** * description:數(shù)組隊列 * * @author RenShiWei * Date: 2021/5/29 20:41 **/ public class ArrayQueue<E> implements Queue<E> { /** 表示可存儲元素的最大容量 */ private int maxSize; /** 隊列頭 */ private int front; /** 隊列尾 */ private int rear; /** 該數(shù)據(jù)用于存放數(shù)據(jù),模擬隊列 */ 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 隊列元素個數(shù) */ @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 隊列的可承載元素個數(shù) */ @Override public int getCapacity() { return data.length - 1; } /** * @return 隊列的有效容量(未使用的空間數(shù)量) */ 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):添加數(shù)據(jù)到隊列"); System.out.println("p(poll):從隊列取出數(shù)據(jù)"); System.out.println("h(getHead):查看隊列頭的數(shù)據(jù)"); System.out.println("n(isEmpty):是否隊空"); System.out.println("f(isFull):是否隊滿"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("當(dāng)前隊列:" + queue.toString() + "\t元素個數(shù):" + queue.getSize() + "\t有效容量:" + queue.getEmptyCount()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("請輸入一個整數(shù)"); 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 分析
假溢出現(xiàn)象
在非空順序隊列中,隊頭指針始終指向當(dāng)前的隊頭元素,而隊尾指針始終指向真正隊尾元素。當(dāng)rear == maxSize - 1
時,認(rèn)為隊滿。但此時不一定是真的隊滿,因為隨著部分元素的出隊,數(shù)組前面會出現(xiàn)一些空單元,如下圖所示。由于只能在隊尾入隊,使得上述空單元無法使用。把這種現(xiàn)象稱為假溢出。
問題:目前這個數(shù)組使用一次就不能用(出隊的空間),沒有達(dá)到復(fù)用的效果。可使用算法將其改造成環(huán)形隊列(取模:%)。
三、環(huán)形隊列
為了解決假溢出現(xiàn)象并使得隊列空間得到充分利用,一個較巧妙的辦法是將順序隊列的數(shù)組看成一個環(huán)狀的空間,即規(guī)定最后一個單元的后繼為第一個單元,我們形象地稱之為循環(huán)隊列。
3.1 思路分析
- 初始化隊列時,令
front = rear = 0
。front
指向隊列的第一個元素,rear
指向隊列最后一個元素的后一個位置(希望損失一個位置作為約定,用來區(qū)分隊空和隊滿)。 - 判斷隊空的條件:
front == rear
。 - 判斷隊滿的條件:
(rear + 1) % maxSize == front
。 - 隊列中的元素個數(shù):
(rear + maxSize - front) % maxSize
。 - 入隊時,將數(shù)據(jù)存入
rear
所指的數(shù)組元素中,指針變化:rear = ( rear+1) % maxSize
。 - 出隊時,將數(shù)據(jù)存入
front
所指的數(shù)組元素中,指針變化:front = ( front+1 ) % maxSize
。
下圖給出了循環(huán)隊列的幾種情況:
3.2 代碼實現(xiàn)
/** * description:循環(huán)隊列 * * @author RenShiWei * Date: 2021/5/30 16:38 **/ public class LoopQueue<E> implements Queue<E> { /** 存儲元素 數(shù)組的長度(有效長度需要-1) */ private int maxSize; /** 隊列頭 */ private int front; /** 隊列尾 */ private int rear; /** 該數(shù)據(jù)用于存放數(shù)據(jù),模擬隊列 */ private E[] data; /** * 初始化環(huán)形隊列 * * @param arrMaxSize 初始隊列容量 */ @SuppressWarnings("unchecked") public LoopQueue(int arrMaxSize) { //循環(huán)隊列需要有意識浪費一個空間 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 隊列的可承載元素個數(shù) */ @Override public int getCapacity() { return data.length - 1; } /** * @return 隊列元素個數(shù) */ @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):添加數(shù)據(jù)到隊列"); System.out.println("p(poll):從隊列取出數(shù)據(jù)"); System.out.println("h(getHead):查看隊列頭的數(shù)據(jù)"); System.out.println("n(isEmpty):是否隊空"); System.out.println("f(isFull):是否隊滿"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("當(dāng)前隊列:" + queue.toString()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("請輸入一個整數(shù)"); 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 分析
相比數(shù)組隊列來說,循環(huán)隊列解決了數(shù)組空間不能再次利用的問題。但依然存在一些問題:
- 當(dāng)隊列真的滿的時候就不能再進行入隊操作了。但是從我們常用的
ArrayList
來分析,在存儲空間允許的條件下是可以一直添加元素的。 - 當(dāng)數(shù)組元素頻繁進行入隊或者出隊操作時,可能造成空間的浪費。循環(huán)隊列其實只利用了有限的存儲空間,但是在最初實例化循環(huán)隊列的時候,如果空間聲明的很大,那么會造成一定程度上的空間浪費。
- 假設(shè),聲明一個容量為20的循環(huán)隊列,但每次入隊2個元素后,又出隊2個元素,那么實際只利用了很有限的空間,造成了空間浪費,但又不能聲明的空間太小,并不能保證未來每次只入隊或者出隊2個元素。
因此,是否可以實現(xiàn)動態(tài)的將循環(huán)隊列進行擴容或者縮容,上述兩個問題,可以利用下面的動態(tài)循環(huán)隊列來實現(xiàn)。
當(dāng)然,上述的數(shù)組隊列,也可以改造成動態(tài)的,但是出隊元素的空間依然會浪費,所以沒必要進行實現(xiàn)。
四、動態(tài)循環(huán)隊列
為了解決循環(huán)隊列,隊滿不能入隊,以及頻繁入隊出隊引起的空間浪費,而引出動態(tài)循環(huán)隊列的概念。即在隊滿時進行擴容,在隊列元素個數(shù)下降到一定情況下進行縮容。
4.1 思路分析
- 除了入隊和出隊操作,其他操作均與循環(huán)隊列相同。
- 循環(huán)隊列存儲元素的數(shù)組容量變更思路:使用擴容一倍/縮容一倍的新數(shù)組接收原來循環(huán)隊列存儲的元素。接收后,將
front
指針置為0;將rear
指針值到最后一個元素的位置(即存儲有效元素的數(shù)量)。 - 什么時候擴容:隊滿
- 什么時候縮容:隊列元素只有1/4,并且縮容后容量不為0。
- 數(shù)組容量為0時,縮容會出現(xiàn)異常
- 為什么不在隊列元素只有1/2時縮容?當(dāng)數(shù)組元素為一半的時候一次添加,一次刪除,造成的一直擴容和減小的操作。
4.2 代碼實現(xiàn)
/** * description:動態(tài)循環(huán) * * @author RenShiWei * Date: 2021/5/30 17:06 **/ public class DynamicLoopQueue<E> implements Queue<E> { /** 存儲元素 數(shù)組的長度(有效長度需要-1) */ private int maxSize; /** 隊列頭 */ private int front; /** 隊列尾 */ private int rear; /** 該數(shù)據(jù)用于存放數(shù)據(jù),模擬隊列 */ private E[] data; /** * 初始化環(huán)形隊列 * * @param arrMaxSize 初始隊列容量 */ @SuppressWarnings("unchecked") public DynamicLoopQueue(int arrMaxSize) { //循環(huán)隊列需要有意識浪費一個空間 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 隊列的可承載元素個數(shù) */ @Override public int getCapacity() { return data.length - 1; } /** * @return 隊列元素個數(shù) */ @Override public int getSize() { return (rear + maxSize - front) % maxSize; } /** * 隊尾入隊 * * @param e 入隊元素 */ @Override public void add(E e) { if (isFull()) { //隊滿不再進行報錯,而是進行動態(tài)擴容 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; //當(dāng)數(shù)組實際元素減小到空間的一半的時候,對其進行縮小 //if(size == data.length / 2) /* 解決當(dāng)一半的時候一次添加,一次刪除,造成的一直擴容和減小的操作, 增加必須要擴容,所以可以讓縮容變得更懶時在進行,即1/4時 data.length / 2 != 0防止數(shù)組大小最后變成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]; //有多個元素循環(huán)多少次 for (int i = 0; i < getSize(); i++) { //循環(huán)隊列會發(fā)生偏移,重新賦值給新數(shù)組 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):添加數(shù)據(jù)到隊列"); System.out.println("p(poll):從隊列取出數(shù)據(jù)"); System.out.println("h(getHead):查看隊列頭的數(shù)據(jù)"); System.out.println("n(isEmpty):是否隊空"); System.out.println("f(isFull):是否隊滿"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("當(dāng)前隊列:" + queue.toString()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("請輸入一個整數(shù)"); 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("程序退出"); } }
到此這篇關(guān)于Java動態(tài)循環(huán)隊列是如何實現(xiàn)的的文章就介紹到這了,更多相關(guān)Java動態(tài)循環(huán)隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot實現(xiàn)文件在線預(yù)覽功能的全過程
我們開發(fā)業(yè)務(wù)系統(tǒng)的時候,經(jīng)常有那種文檔文件在線預(yù)覽的需求,下面這篇文章主要給大家介紹了關(guān)于SpringBoot實現(xiàn)文件在線預(yù)覽功能的相關(guān)資料,需要的朋友可以參考下2021-11-11零基礎(chǔ)寫Java知乎爬蟲之獲取知乎編輯推薦內(nèi)容
上篇文章我們拿百度首頁做了個小測試,今天我們來個復(fù)雜的,直接抓取知乎編輯推薦的內(nèi)容,小伙伴們可算松了口氣,終于進入正題了,哈哈。2014-11-11使用Java模擬鼠標(biāo)和鍵盤的詳細(xì)操作步驟
這篇文章主要介紹了使用Java模擬鼠標(biāo)和鍵盤的詳細(xì)操作步驟,要運行上面提供的Java程序,您需要遵循幾個步驟來設(shè)置Java環(huán)境、編寫程序代碼,并執(zhí)行該程序,文中有相關(guān)的代碼示例,需要的朋友可以參考下2024-05-05詳解SpringBoot啟動項目后執(zhí)行方法的幾種方式
在項目開發(fā)中某些場景必須要用到啟動項目后立即執(zhí)行方式的功能,本文主要聊聊實現(xiàn)立即執(zhí)行的幾種方法,具有一定的參考價值,感興趣的可以了解一下2023-09-09