App下載

詳細(xì)代碼解析如何使用Java的數(shù)組來模擬環(huán)形隊(duì)列的實(shí)現(xiàn)

孫尚香 2021-08-09 14:02:08 瀏覽數(shù) (2073)
反饋

學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的小伙伴們,想來對最常用的數(shù)據(jù)結(jié)構(gòu)之一的隊(duì)列是不陌生的吧。沒學(xué)過的也不用緊張,下文將簡單為大家介紹關(guān)于數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的一些簡單的概念以及具體的實(shí)現(xiàn)思路。并通過Java數(shù)組的形式來模擬數(shù)據(jù)結(jié)構(gòu)中環(huán)形隊(duì)列的實(shí)現(xiàn)。

一、隊(duì)列是什么

我們先來看下百科的解釋:
隊(duì)列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作,而在表的后端(rear)進(jìn)行插入操作,隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾,進(jìn)行刪除操作的端稱為隊(duì)頭。
總結(jié)起來兩點(diǎn):
1.一種線性表
2.添加操作只能在表尾,刪除操作在表頭(先進(jìn)先出)

二、實(shí)現(xiàn)隊(duì)列的思路

 1.初始化一個(gè)空隊(duì)列

初始化一個(gè)大小固定的數(shù)組,并將頭指針,尾指針都指向下表為0的位置,但其實(shí)這種初始化頭指針指向的是隊(duì)首,尾指針指向的是隊(duì)尾的后一個(gè)元素。

初始化一個(gè)隊(duì)列

2.往隊(duì)列里添加元素

往隊(duì)列里添加元素,尾指針后移一位。

添加元素到隊(duì)列

一直添加直到隊(duì)列滿

一直添加直到隊(duì)列滿

這個(gè)時(shí)候尾指針已經(jīng)出現(xiàn)在數(shù)組下標(biāo)外了

3.消費(fèi)隊(duì)列元素

每消費(fèi)一個(gè)隊(duì)列元素,頭指針指向的元素出隊(duì),并且后移一位

202104180958019

再消費(fèi)兩個(gè)

2021041809580110

這個(gè)時(shí)候我們想往隊(duì)列里繼續(xù)添加元素,尾指針后移,然后發(fā)現(xiàn)出現(xiàn)了假溢出的情況,因?yàn)槲仓羔槦o法再向后移動(dòng),而隊(duì)列實(shí)際上并沒有滿,我們又無法繼續(xù)往隊(duì)列里添加數(shù)據(jù)。這個(gè)時(shí)候其實(shí)有兩種解決方案。
方案一:我們每消費(fèi)一個(gè)元素,其后面的元素都整體往前移動(dòng)一位,就像我們生活中排隊(duì)打飯一樣,后面的人都往前挪一挪。但這種方案帶來的后果是,帶來的時(shí)間開銷太大,因?yàn)榛旧弦僮魉械脑兀赃@種方案不可行。
方案二:尾指針在指向下表為最后一個(gè)元素時(shí),再添加元素,如果還有空位,就將尾指針重新指向0,頭指針在取到下表數(shù)組末尾時(shí),如果前面還有元素,頭指針也指向0,這就是我們說的環(huán)形隊(duì)列。

三、實(shí)現(xiàn)環(huán)形隊(duì)列

1.環(huán)形隊(duì)列示例圖

尾指針重新指向零

2021041809580111

再添加一個(gè)元素

2021041809580112

連續(xù)消費(fèi)三個(gè)元素,如果前面還有元素,頭指針也指向0

在這里插入圖片描述

這個(gè)時(shí)候我們發(fā)現(xiàn)那個(gè)原來熟悉的隊(duì)列又回來了。

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

/**
 * description:數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列
 * author: xiaowang
 * */
public class MyQueue<E> {
    // 隊(duì)列最大個(gè)數(shù)
    private int size;
    // 元素真實(shí)個(gè)數(shù)
    private int number;
    // 頭指針,指向隊(duì)列的第一個(gè)元素即隊(duì)頭
    private int front;
    // 尾指針,指向隊(duì)尾的后一個(gè)元素(非隊(duì)尾)
    private int rear;
    // 隊(duì)列具體值
    private Object[] values;
    // 隊(duì)列滿標(biāo)記,當(dāng)隊(duì)列是滿的時(shí)候?yàn)閠rue
    private boolean isFullFlag;

    /**構(gòu)造器*/
    public MyQueue(int size){
        if (size<0){
            throw new RuntimeException("初始化隊(duì)列時(shí),隊(duì)列最大元素個(gè)數(shù)不能為負(fù)");
        }
        this.front  = 0;
        this.rear = 0;
        this.number = 0;
        this.isFullFlag = false;
        this.size = size;
        this.values = new Object[size];

    }

    /**往隊(duì)列里添加元素 添加成功返回true 失敗返回false*/
    public boolean addToQueue(E e){
        // 判斷隊(duì)列是否已經(jīng)滿了
        if (isFullFlag){
            System.out.println("隊(duì)列已滿,無法繼續(xù)添加元素");
            return false;
        }
        // 添加元素
        values[rear] = e;
        // 元素個(gè)數(shù)加一
        number++;
        // 尾指針后移一位,若已經(jīng)指向數(shù)組最后的下表,則重新指向0
        if (rear == size-1){
            rear = 0;
        }else{
            rear++;
        }
        // 添加完這個(gè)元素,判斷隊(duì)列是否已經(jīng)滿了,若滿則標(biāo)記為true
        if (rear==front){
            isFullFlag = true;
        }
        return true;
    }
    /**從隊(duì)列里取出數(shù)據(jù),隊(duì)頭數(shù)據(jù)*/
    public E getFromQueue(){
        // 判斷隊(duì)列是否為空
        if (number==0||size==0){
            System.out.println("隊(duì)列為空,無法從隊(duì)列中獲取數(shù)據(jù)");
            return null;
        }
        // 臨時(shí)變量
        E e = (E) values[front];
        // 隊(duì)頭置空
        values[front] = null;
        // 個(gè)數(shù)減一
        number--;
        // 頭指針后移,若已經(jīng)指向數(shù)組最后的下表,則重新指向0
        if (front==size-1){
            front = 0;
        }else {
            front++;
        }
        // 取隊(duì)列之前若是滿的狀態(tài),則更新狀態(tài)
        if (isFullFlag){
            isFullFlag = false;
        }
        return e;
    }
    /**獲取目前有幾個(gè)元素正在進(jìn)行排隊(duì)*/
    public int getNumber(){
        return number;
    }
    /**獲取隊(duì)列的最大個(gè)數(shù)*/
    public int getSize(){
        return size;
    }
    /**查看隊(duì)列在數(shù)組里保存的詳細(xì)情況*/
    public String toString(){
        StringBuffer valueStr = new StringBuffer();
        valueStr.append("[");
        for (int i = 0; i < size; i++) {
            if (i!=size-1){
                valueStr.append(values[i]+",");
            }else{
                valueStr.append(values[i]+"]");
            }
        }
        return valueStr.toString();
    }
}

測試代碼

public class TestQueue {

    public static void main(String[] args) {
        MyQueue<String> queue = new MyQueue<String>(5);
        Scanner scanner = new Scanner(System.in);
        Scanner scanner2 = new Scanner(System.in);
        boolean isCan = true;
        while (isCan){
            System.out.println("歡迎來到小王排隊(duì)系統(tǒng),您可以使用以下功能。
添加:1;取出:2;展示:3;獲取排隊(duì)個(gè)數(shù):4;退出:0。");
            int flag = scanner.nextInt();
            switch (flag){
                case 1 :
                    System.out.println("請輸入一個(gè)數(shù)據(jù):");
                    String data = scanner2.nextLine();
                    boolean isSuccess = queue.addToQueue(data);
                    if (isSuccess){
                        System.out.println("添加成功~~~");
                    }
                    break;
                case 2 :
                    String dataFromQueue = queue.getFromQueue();
                    if (dataFromQueue!=null){
                        System.out.println("本次取出的數(shù)據(jù)為:"+dataFromQueue);
                    }
                    break;
                case 3 :
                    System.out.println("隊(duì)列詳情為:
"+queue.toString());
                    break;
                case 4 :
                    System.out.println("目前有"+queue.getNumber()+"個(gè)元素正在進(jìn)行排隊(duì)");
                    break;
                default:
                    isCan = false;
                    System.out.println("已退出...");
                    break;
            }
        }

    }
}

總結(jié)

以上就是關(guān)于如何使用Java的數(shù)組來模擬數(shù)據(jù)結(jié)構(gòu)中的環(huán)形隊(duì)列實(shí)現(xiàn)的全部內(nèi)容,想要了解更多相關(guān)java 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容,請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望本篇文章能夠?qū)Υ蠹业膶W(xué)習(xí)或者工作能夠有所幫助!

0 人點(diǎn)贊