快捷導(dǎo)航

Java隊(duì)列篇之實(shí)現(xiàn)數(shù)組模擬隊(duì)列及可復(fù)用環(huán)形隊(duì)列詳解

更新時(shí)間：2021年10月13日 10:16:04 作者：葉綠體不忘呼吸

像棧一樣，隊(duì)列（queue）也是一種線性表，它的特性是先進(jìn)先出，插入在一端，刪除在另一端。就像排隊(duì)一樣，剛來的人入隊(duì)（push）要排在隊(duì)尾(rear)，每次出隊(duì)(pop)的都是隊(duì)首(front)的人

隊(duì)列簡(jiǎn)介

隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來實(shí)現(xiàn)。

遵循先入先出的原則。即先存入隊(duì)列的數(shù)據(jù)，先取出，后存入的后取出。

示意圖：(使用數(shù)組模擬隊(duì)列示意圖)

在這里插入圖片描述

有兩個(gè)分別指向頭部和尾部的“指針”。

數(shù)組模擬隊(duì)列（無法復(fù)用）

1、實(shí)現(xiàn)思路

隊(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è)步驟：
①將尾指針往后移。
②若尾指針rear小于隊(duì)列的最大下標(biāo)maxSize-1，則將數(shù)據(jù)存入rear 所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。

rear+1當(dāng)front== rear[空]
rear==maxSize-1[隊(duì)列滿]

2、代碼實(shí)現(xiàn)

①數(shù)組實(shí)現(xiàn)隊(duì)列類

class ArrQueue {
    private int maxSize; //隊(duì)列（數(shù)組）最大容量
    private int front; //指向隊(duì)列頭部
    private int rear; //指向隊(duì)列尾部
    private int[] queue;

    //創(chuàng)造隊(duì)列的構(gòu)造器
    public ArrQueue(int maxSize){
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = -1; //其實(shí)是隊(duì)列第一個(gè)元素的前一個(gè)索引
        rear = -1; //最后一個(gè)元素的索引
    }

    //判斷是否滿
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    //判斷是否空
    public boolean isEmpty(){
        return front == rear;
    }

    //添加元素
    public void addQueue(int n){
        if (isFull()){
            System.out.println("隊(duì)列已經(jīng)滿了，無法添加！");
            return;
        }else {
            rear++;
            queue[rear] = n;
        }

    }

    //取出元素
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊(duì)列為空，無元素可??！");
        }else {
            front++;
            return queue[front];
        }
    }

    //顯示隊(duì)列
    public void showQueue(){
        if (isEmpty()){
            System.out.println("隊(duì)列為空，沒有元素可顯示！");
            return;
        }
        for (int i : queue){
            System.out.println(i);
        }
    }

    //顯示頭數(shù)據(jù)
    public void headQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊(duì)列為空，沒有頭數(shù)據(jù)！");
        }
        int i = front;
        System.out.println(queue[++i]);
    }

}

②測(cè)試類

import java.util.Scanner;

/**
 * @Author: Yeman
 * @Date: 2021-10-11-22:02
 * @Description:
 */
public class ArrayQueueTest {
    public static void main(String[] args) {
        //創(chuàng)建一個(gè)隊(duì)列
        ArrQueue arrQueue = new ArrQueue(3);
        //創(chuàng)建一個(gè)用戶輸入
        Scanner scanner = new Scanner(System.in);
        //創(chuàng)建一個(gè)功能菜單
        char key = ' ';
        boolean isShow = true;
        while (isShow){
            System.out.println("s:顯示隊(duì)列");
            System.out.println("a:添加數(shù)據(jù)");
            System.out.println("g:取出數(shù)據(jù)");
            System.out.println("h:顯示頭數(shù)據(jù)");
            System.out.println("e:退出程序");
            key = scanner.next().charAt(0);
            switch (key){
                case 's' :
                    arrQueue.showQueue();
                    break;
                case 'a' :
                    System.out.println("請(qǐng)輸入一個(gè)數(shù)：");
                    int value = scanner.nextInt();
                    arrQueue.addQueue(value);
                    break;
                case 'g' :
                    try {
                        System.out.println(arrQueue.getQueue());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h' :
                    try {
                        arrQueue.headQueue();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e' :
                    isShow = false;
                    break;
            }
        }
        System.out.println("程序退出...");
    }
}

數(shù)組模擬環(huán)形隊(duì)列（可復(fù)用）

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

分析說明:
①尾索引的下一個(gè)為頭索引時(shí)表示隊(duì)列滿，即將隊(duì)列容量空出一個(gè)作為約定。在作判斷隊(duì)列滿的時(shí)候需要注意(rear+ 1) % maxSize== front [滿]
②rear == front [空]

1、思路如下:

①front 變量的含義調(diào)整：front 指向隊(duì)列的第一個(gè)元素, 也就是說arr[front]就是隊(duì)列的第一個(gè)元素，front的初始值為0。
②rear 變量的含義調(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 + maxSize - front) % maxSize
⑥我們就可以在原來的隊(duì)列上修改得到一個(gè)環(huán)形隊(duì)列

2、代碼實(shí)現(xiàn)

①數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列類

class ArrQueue {
    private int maxSize; //隊(duì)列（數(shù)組）最大容量
    private int front; //指向隊(duì)列頭部，隊(duì)列第一個(gè)元素的索引
    private int rear; //指向隊(duì)列尾部，隊(duì)列最后一個(gè)元素的后一個(gè)索引
    private int[] queue;

    //創(chuàng)造隊(duì)列的構(gòu)造器
    public ArrQueue(int maxSize){
        this.maxSize = maxSize;
        queue = new int[maxSize];
    }

    //判斷是否滿
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    //判斷是否空
    public boolean isEmpty(){
        return front == rear;
    }

    //添加元素
    public void addQueue(int n){
        if (isFull()){
            System.out.println("隊(duì)列已經(jīng)滿了，無法添加！");
            return;
        }else {
            queue[rear] = n;
            rear = (rear + 1) % maxSize;
        }

    }

    //取出元素
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊(duì)列為空，無元素可??！");
        }else {
            int data = queue[front];
            front = (front + 1) % maxSize;
            return data;
        }
    }

    //顯示隊(duì)列
    public void showQueue(){
        if (isEmpty()){
            System.out.println("隊(duì)列為空，沒有元素可顯示！");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d] = %d\n",i % maxSize,queue[i % maxSize]);
        }

    }
    //求當(dāng)前隊(duì)列有效數(shù)據(jù)個(gè)數(shù)
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //顯示頭數(shù)據(jù)
    public void headQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊(duì)列為空，沒有頭數(shù)據(jù)！");
        }
        System.out.println(queue[front]);
    }
    
}

②測(cè)試類

import java.util.Scanner;

/**
 * @Author: Yeman
 * @Date: 2021-10-11-22:02
 * @Description:
 */
public class ArrayQueueTest {
    public static void main(String[] args) {
        //創(chuàng)建一個(gè)隊(duì)列
        ArrQueue arrQueue = new ArrQueue(3); //說明該環(huán)形隊(duì)列的最大有效數(shù)據(jù)為2
        //創(chuàng)建一個(gè)用戶輸入
        Scanner scanner = new Scanner(System.in);
        //創(chuàng)建一個(gè)功能菜單
        char key = ' ';
        boolean isShow = true;
        while (isShow){
            System.out.println("s:顯示隊(duì)列");
            System.out.println("a:添加數(shù)據(jù)");
            System.out.println("g:取出數(shù)據(jù)");
            System.out.println("h:顯示頭數(shù)據(jù)");
            System.out.println("e:退出程序");
            key = scanner.next().charAt(0);
            switch (key){
                case 's' :
                    arrQueue.showQueue();
                    break;
                case 'a' :
                    System.out.println("請(qǐng)輸入一個(gè)數(shù)：");
                    int value = scanner.nextInt();
                    arrQueue.addQueue(value);
                    break;
                case 'g' :
                    try {
                        System.out.println(arrQueue.getQueue());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h' :
                    try {
                        arrQueue.headQueue();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e' :
                    isShow = false;
                    break;
            }
        }
        System.out.println("程序退出...");
    }
}

到此這篇關(guān)于Java隊(duì)列篇之實(shí)現(xiàn)數(shù)組模擬隊(duì)列及可復(fù)用環(huán)形隊(duì)列詳解的文章就介紹到這了,更多相關(guān)Java 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: