快捷導(dǎo)航

Java實(shí)現(xiàn)隊(duì)列的N種方法

更新時(shí)間：2023年10月03日 09:46:00 作者：java廠長

在Java中,我們可以使用不同的方式來實(shí)現(xiàn)隊(duì)列,本文主要介紹了Java實(shí)現(xiàn)隊(duì)列的N種方法,具有一定的參考價(jià)值,感興趣的可以了解一下

隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來實(shí)現(xiàn)。
遵循先入先出的原則。即：先存入隊(duì)列的數(shù)據(jù)，要先取出。后存入的要后取出。
就相當(dāng)于我們?nèi)粘Ｉ钪械呐抨?duì)，先來先服務(wù)，后來的只能在后面進(jìn)行排隊(duì)等待。

圖解

數(shù)組模擬隊(duì)列

通過對(duì)定義的了解，發(fā)現(xiàn)隊(duì)列很像我們的數(shù)組，那我們是不是可以通過數(shù)組來模擬隊(duì)列，下面我們來實(shí)踐一下。

首先先分析一下：

隊(duì)列本身是有序列表，若使用數(shù)組的結(jié)構(gòu)來存儲(chǔ)隊(duì)列的數(shù)據(jù)，則隊(duì)列數(shù)組的聲明如下圖, 其中 maxSize 是該隊(duì) 列的最大容量。
因?yàn)殛?duì)列的輸出、輸入是分別從前后端來處理，所以我們需要兩個(gè)變量 front 及 rear 分別記錄隊(duì)列前后端的下標(biāo)， front 會(huì)隨著數(shù)據(jù)輸出而改變，而 rear 則是隨著數(shù)據(jù)輸入而改變。
當(dāng)我們將數(shù)據(jù)存入隊(duì)列時(shí)稱為addQueue，addQueue 的處理需要有兩個(gè)步驟：思路分析
- 當(dāng) front == rear 【隊(duì)列空無數(shù)據(jù)】，將尾指針往后移：rear + 1
- 若尾指針 rear 小于隊(duì)列的最大下標(biāo) maxSize-1，則將數(shù)據(jù)存入 rear 所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。 rear == maxSize - 1【表示隊(duì)列滿】無法存入數(shù)據(jù)。

代碼

package com.cz.Queuearray;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.BlockingQueue;
/**
?* @ProjectName: Data_structure
?* @Package: com.cz.Queuearray
?* @ClassName: QueueArray
?* @Author: 張晟睿
?* @Date: 2022/2/21 18:42
?* @Version: 1.0
?*/
public class QueueArray {
? ? public static void main(String[] args) {
? ? ? ? // TODO Auto-generated method stub
? ? ? ? QueueArray1 ?qArray1 = new QueueArray1(3);
? ? ? ? Scanner scanner = new Scanner(System.in);
? ? ? ? char key = ' ';
? ? ? ? boolean f = true;
? ? ? ? while(f){
? ? ? ? ? ? System.out.println("s(show):顯示隊(duì)列");
? ? ? ? ? ? System.out.println("e(exit):退出程序");
? ? ? ? ? ? System.out.println("a(add):添加數(shù)據(jù)到隊(duì)列");
? ? ? ? ? ? System.out.println("g(get):從隊(duì)列里面取出數(shù)據(jù)");
? ? ? ? ? ? System.out.println("h(head):查看隊(duì)列頭部的數(shù)據(jù)");
? ? ? ? ? ? key = scanner.next().charAt(0);
? ? ? ? ? ? switch (key) {
? ? ? ? ? ? ? ? case 's':
? ? ? ? ? ? ? ? ? ? qArray1.getQueue();
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'a':
? ? ? ? ? ? ? ? ? ? System.out.println("請(qǐng)輸出一個(gè)數(shù)字：");
? ? ? ? ? ? ? ? ? ? int value = scanner.nextInt();
? ? ? ? ? ? ? ? ? ? qArray1.addQueue(value);
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'g':
? ? ? ? ? ? ? ? ? ? try {
? ? ? ? ? ? ? ? ? ? ? ? int res = qArray1.exitQueue();
? ? ? ? ? ? ? ? ? ? ? ? System.out.printf("輸出的數(shù)據(jù)是%d\n",res);
? ? ? ? ? ? ? ? ? ? } catch (Exception e) {
? ? ? ? ? ? ? ? ? ? ? ? System.out.println(e.getMessage());
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'h':
? ? ? ? ? ? ? ? ? ? try {
? ? ? ? ? ? ? ? ? ? ? ? int res = qArray1.headQueue();
? ? ? ? ? ? ? ? ? ? ? ? System.out.printf("對(duì)頭的數(shù)據(jù)是%d\n",res);
? ? ? ? ? ? ? ? ? ? } catch (Exception e) {
? ? ? ? ? ? ? ? ? ? ? ? System.out.println(e.getMessage());
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'e':
? ? ? ? ? ? ? ? ? ? scanner.close();
? ? ? ? ? ? ? ? ? ? f=false;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? default:
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println("退出程序！?。。。。?！");
? ? }
}
//數(shù)組模擬隊(duì)列
class QueueArray1{
? ? private int maxSize;//最大容量、
? ? private int arr[]; //聲明數(shù)組
? ? private int front;//隊(duì)頭元素
? ? private int rear;//隊(duì)尾
? ? //構(gòu)造器
? ? public QueueArray1(int arrMaxSize) {
? ? ? ? maxSize = arrMaxSize;
? ? ? ? arr = new int [maxSize];
? ? ? ? front = -1;//指向隊(duì)列頭部，分析出front是指向隊(duì)列頭的前一 個(gè)位置。
? ? ? ? rear = -1;//指向隊(duì)列尾，指向隊(duì)列尾的數(shù)據(jù)(即就是隊(duì)列最后一個(gè)數(shù)據(jù))
? ? }
? ? //判斷隊(duì)空
? ? public boolean isEmety(){
? ? ? ? return rear==front;
? ? }
? ? //判斷隊(duì)滿
? ? public boolean isFull(){
? ? ? ? return rear == maxSize - 1;
? ? }
? ? //入隊(duì)
? ? public void addQueue(int n){
? ? ? ? if (isFull()) {
? ? ? ? ? ? System.out.println("隊(duì)列已滿，無法插入");
? ? ? ? ? ? return;//不加return
? ? ? ? ? ? //Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
? ? ? ? ? ? //at day1.QueueArray1.insert(QueueArray.java:89)
? ? ? ? ? ? //at day1.QueueArray.main(QueueArray.java:32)
? ? ? ? }
? ? ? ? arr[++rear] = n;
? ? }
? ? //出隊(duì)
? ? public int exitQueue(){
? ? ? ? if (isEmety()) {
? ? ? ? ? ? throw new RuntimeException("隊(duì)列為空，無元素");
? ? ? ? }
? ? ? ? return arr[++front];
? ? }
? ? //輸出全部元素
? ? public void getQueue(){
? ? ? ? if (isEmety()) {
? ? ? ? ? ? System.out.println("隊(duì)列為空，無法輸出數(shù)據(jù)~~~~~~~~~~");
? ? ? ? }
? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? System.out.printf("arr[%d]=%d\n",i,arr[i]);
? ? ? ? }
? ? }
? ? //顯示隊(duì)列的頭數(shù)據(jù)，不是取數(shù)據(jù)
? ? public int headQueue(){
? ? ? ? if (isEmety()) {
? ? ? ? ? ? throw new RuntimeException("數(shù)據(jù)為空，無法取出頭元素~~~~~~~~~~");
? ? ? ? }
? ? ? ? return arr[front+1];
? ? }
}

隊(duì)列優(yōu)化—循環(huán)隊(duì)列

在上述的使用中，發(fā)現(xiàn)數(shù)組使用一次之后就無法使用，沒有達(dá)到復(fù)用的效果，那究竟能不能實(shí)現(xiàn)復(fù)用呢？當(dāng)然可以的。

我們將這個(gè)數(shù)組使用算法，改進(jìn)成一個(gè) 環(huán)形的隊(duì)列取模：%

對(duì)前面的數(shù)組模擬隊(duì)列的優(yōu)化，充分利用數(shù)組. 因此將數(shù)組看做是一個(gè)環(huán)形的。(通過取模的方式來實(shí)現(xiàn)即可)

簡單分析一下：

尾索引的下一個(gè)為頭索引時(shí)表示隊(duì)列滿，即將隊(duì)列容量空出一個(gè)作為約定,這個(gè)在做判斷隊(duì)列滿的時(shí)候需要注意 (rear + 1) % maxSize == front 【隊(duì)列滿】
rear == front 【隊(duì)列為空】

思路如下：

front 變量的含義做一個(gè)調(diào)整： front 就指向隊(duì)列的第一個(gè)元素, 也就是說 arr[front] 就是隊(duì)列的第一個(gè)元素，front 的初始值 = 0
rear 變量的含義做一個(gè)調(diào)整：rear 指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置. 因?yàn)橄Ｍ粘鲆粋€(gè)空間做為約定，rear 的初始值 = 0
當(dāng)隊(duì)列滿時(shí)，條件是 (rear + 1) % maxSize == front 【滿】
對(duì)隊(duì)列為空的條件， rear == front 空
當(dāng)我們這樣分析，隊(duì)列中有效的數(shù)據(jù)的個(gè)數(shù) (rear - front + maxSize) % maxSize
我們就可以在原來的隊(duì)列上修改得到，一個(gè)環(huán)形隊(duì)列

代碼

package com.cz.Queuearray;
import java.util.Scanner;
/**
?* @ProjectName: Data_structure
?* @Package: com.cz.Queuearray
?* @ClassName: CircleQueueArray
?* @Author: 張晟睿
?* @Date: 2022/2/22 14:58
?* @Version: 1.0
?*/
public class CircleQueueArray {
? ? public static void main(String[] args) {
? ? ? ? CircleQueueArray1 ?circlequeue = new CircleQueueArray1(3);
? ? ? ? Scanner scanner = new Scanner(System.in);
? ? ? ? char key = ' ';
? ? ? ? boolean f = true;
? ? ? ? while(f){
? ? ? ? ? ? System.out.println("s(show):顯示隊(duì)列");
? ? ? ? ? ? System.out.println("e(exit):退出程序");
? ? ? ? ? ? System.out.println("a(add):添加數(shù)據(jù)到隊(duì)列");
? ? ? ? ? ? System.out.println("g(get):從隊(duì)列里面取出數(shù)據(jù)");
? ? ? ? ? ? System.out.println("h(head):查看隊(duì)列頭部的數(shù)據(jù)");
? ? ? ? ? ? key = scanner.next().charAt(0);
? ? ? ? ? ? switch (key) {
? ? ? ? ? ? ? ? case 's':
? ? ? ? ? ? ? ? ? ? circlequeue.showQueue();
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'a':
? ? ? ? ? ? ? ? ? ? System.out.println("請(qǐng)輸出一個(gè)數(shù)字：");
? ? ? ? ? ? ? ? ? ? int value = scanner.nextInt();
? ? ? ? ? ? ? ? ? ? circlequeue.addQueue(value);
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'g':
? ? ? ? ? ? ? ? ? ? try {
? ? ? ? ? ? ? ? ? ? ? ? int res = circlequeue.getQueue();
? ? ? ? ? ? ? ? ? ? ? ? System.out.printf("輸出的數(shù)據(jù)是%d\n",res);
? ? ? ? ? ? ? ? ? ? } catch (Exception e) {
? ? ? ? ? ? ? ? ? ? ? ? System.out.println(e.getMessage());
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'h':
? ? ? ? ? ? ? ? ? ? try {
? ? ? ? ? ? ? ? ? ? ? ? int res = circlequeue.headQueue();
? ? ? ? ? ? ? ? ? ? ? ? System.out.printf("對(duì)頭的數(shù)據(jù)是%d\n",res);
? ? ? ? ? ? ? ? ? ? } catch (Exception e) {
? ? ? ? ? ? ? ? ? ? ? ? System.out.println(e.getMessage());
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case 'e':
? ? ? ? ? ? ? ? ? ? scanner.close();
? ? ? ? ? ? ? ? ? ? f=false;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? default:
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println("退出程序?。。。。。?！");
? ? }
}
class CircleQueueArray1{
? ? private int maxSize; // 表示數(shù)組的最大容量
? ? //front 變量的含義做一個(gè)調(diào)整： front 就指向隊(duì)列的第一個(gè)元素, 也就是說 arr[front] 就是隊(duì)列的第一個(gè)元素
? ? //front 的初始值 = 0
? ? private int front;
? ? //rear 變量的含義做一個(gè)調(diào)整：rear 指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置. 因?yàn)橄Ｍ粘鲆粋€(gè)空間做為約定. //rear 的初始值 = 0
? ? private int rear; // 隊(duì)列尾
? ? private int[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊(duì)列
? ? public CircleQueueArray1(int MaxSize){
? ? ? ? maxSize = MaxSize;
? ? ? ? arr = new int [maxSize];
? ? }
? ? //判斷隊(duì)滿
? ? public boolean isFull(){
? ? ? ? return (rear + 1) % maxSize == front;
? ? }
? ? //判斷隊(duì)列空
? ? public boolean isEmpty(){
? ? ? ? return rear == front;
? ? }
? ? // 添加數(shù)據(jù)到隊(duì)列
? ? public void addQueue(int n) {
? ? ? ? if (isFull()){
? ? ? ? ? ? System.out.println("隊(duì)列滿，不能加入數(shù)據(jù)~");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? //將數(shù)據(jù)直接插入到數(shù)組，用隊(duì)尾rear來進(jìn)行位置的確定
? ? ? ? arr[rear] = n;
? ? ? ? //將 rear 后移, 這里必須考慮取
? ? ? ? rear = (rear + 1) % maxSize;
? ? }
? ? //獲取隊(duì)列的數(shù)據(jù), 出隊(duì)列
? ? public int getQueue() {
? ? ? ? if (isEmpty()) throw new RuntimeException("隊(duì)列空，不能取數(shù)據(jù)");
? ? ? ? // 這里需要分析出 front 是指向隊(duì)列的第一個(gè)元素,因?yàn)檫@里是循環(huán)的，所以我們考慮用一個(gè)臨時(shí)變量來獲取當(dāng)前的隊(duì)頭
? ? ? ? // 1. 先把 front 對(duì)應(yīng)的值保留到一個(gè)臨時(shí)變量
? ? ? ? // 2. 將 front 后移, 考慮取模
? ? ? ? // 3. 將臨時(shí)保存的變量返回
? ? ? ? int value = front;
? ? ? ? front = (front + 1) % maxSize;
? ? ? ? return arr[value];
? ? }
? ? // 求出當(dāng)前隊(duì)列有效數(shù)據(jù)的個(gè)數(shù)
? ? public int size() {
? ? ? ? return (rear - front + maxSize) % maxSize;
? ? }
? ? // 顯示隊(duì)列的所有數(shù)據(jù)
? ? public void showQueue() {
? ? ? ? if (isEmpty()) throw new RuntimeException("隊(duì)列空，不能取數(shù)據(jù)");
? ? ? ? for (int i = front; i < front + size(); i++) {
? ? ? ? ? ? System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
? ? ? ? }
? ? }
? ? // 顯示隊(duì)列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
? ? public int headQueue() {
? ? ? ? // 判斷隊(duì)列是空
? ? ? ? if (isEmpty()) {
? ? ? ? ? ? throw new RuntimeException("隊(duì)列空的，沒有數(shù)據(jù)~~");
? ? ? ? }
? ? ? ? return arr[front];
? ? }
}

使用java內(nèi)部隊(duì)列

LinkedList 類實(shí)現(xiàn)了 Queue 接口，因此我們可以把 LinkedList 當(dāng)成 Queue 來用。

代碼

package com.cz.Queuearray;
import java.util.LinkedList;
import java.util.Queue;
/**
?* @ProjectName: Data_structure
?* @Package: com.cz.Queuearray
?* @ClassName: LinkedListDemo
?* @Author: 張晟睿
?* @Date: 2022/2/22 15:43
?* @Version: 1.0
?*/
public class LinkedListDemo {
? ? public static void main(String[] args) {
? ? ? ? //add()和remove()方法在失敗的時(shí)候會(huì)拋出異常(不推薦)
? ? ? ? Queue<Integer> queue = new LinkedList<>();
? ? ? ? //offer() 將指定的元素添加為此列表的尾部（最后一個(gè)元素）。
? ? ? ? queue.offer(1);
? ? ? ? queue.offer(2);
? ? ? ? queue.offer(3);
? ? ? ? queue.offer(4);
? ? ? ? queue.offer(5);
? ? ? ? for (Integer nums:queue) {
? ? ? ? ? ? System.out.println(nums);
? ? ? ? }
? ? ? ? //poll() 檢索并刪除此列表的頭（第一個(gè)元素）。
? ? ? ? //當(dāng)集合為空時(shí)，返回 null
? ? ? ? queue.poll();
? ? ? ? queue.poll();
? ? ? ? queue.poll();
? ? ? ? queue.poll();
? ? ? ? //queue.poll();
? ? ? ? //remove() 檢索并刪除此列表的頭（第一個(gè)元素）。
? ? ? ? //當(dāng)集合為空時(shí)，出現(xiàn)異常 java.util.NoSuchElementException;
? ? ? ? queue.remove();
? ? ? ? //element() 檢索但不刪除此列表的頭（第一個(gè)元素）。
? ? ? ? //當(dāng)隊(duì)列為空時(shí)，java.util.NoSuchElementException
? ? ? ? //System.out.println("隊(duì)列的頭部：" + queue.element());
? ? ? ? //peek() 檢索但不刪除此列表的頭（第一個(gè)元素）。
? ? ? ? //當(dāng)隊(duì)列為空時(shí)，返回null
? ? ? ? System.out.println("隊(duì)列的頭部：" + queue.peek());
? ? }
}

poll，remove 區(qū)別：

remove() 和 poll() 方法都是從隊(duì)列中刪除第一個(gè)元素。remove() 的行為與 Collection 接口的版本相似，但是新的 poll() 方法在用空集合調(diào)用時(shí)不是拋出異常，只是返回 null。因此新的方法更適合容易出現(xiàn)異常條件的情況。