Java數(shù)組模擬隊列

簡介

本文主要內(nèi)容在Java代碼中用數(shù)組模擬一個隊列出來道伟，這里只簡要一提，不過多的介紹隊列基本概念

隊列是一種特殊的線性表，特點是先進先出草丧。

和棧相似，它們的操作都是受限的莹桅。

這里要說的隊列昌执，只有兩種操作，插入一個數(shù)據(jù)稱為入隊诈泼，刪除一個數(shù)據(jù)稱為出隊懂拾，并且只能從隊尾插入數(shù)據(jù)，只能在隊頭刪除數(shù)據(jù)铐达。

隊列的數(shù)組實現(xiàn)

從百度百科中可以看到對隊列的描述

簡要來說岖赋，實現(xiàn)一個隊列，本質(zhì)上需要一片連續(xù)的存儲空間瓮孙，可以是靜態(tài)分配唐断，也可以動態(tài)申請

數(shù)組呢，正好就可以貼合這個要求杭抠，靜態(tài)分配一段定長的連續(xù)內(nèi)存空間

除此之外脸甘，還需要兩個指針，一個指向隊頭偏灿，一個指向隊尾

入隊操作是在隊尾添加數(shù)據(jù)丹诀，所以要在指向隊尾的指針后一個位置添加數(shù)據(jù)，并且將指針指向新的隊尾翁垂，也就是尾指針后移

出隊操作是取出并刪除隊頭的數(shù)據(jù)铆遭，其實刪除數(shù)據(jù)的操作，就是在指向隊頭的指針處取得數(shù)據(jù)返回沿猜，然后將隊頭指針后移即可

我們發(fā)現(xiàn)枚荣，在操作數(shù)據(jù)的同時，需要伴隨著指針的移動

分析一把邢疙，如果將頭指針正好指向當(dāng)前隊頭棍弄，尾指針正好指向當(dāng)前隊尾

注意：完整實現(xiàn)一個隊列，需要有入隊疟游、出隊呼畸、初始化三個操作。但用數(shù)組實現(xiàn)隊列颁虐，因為存儲空間是靜態(tài)分配的定長空間蛮原，意味著隊列容量有最大值，所以還需要判斷隊列滿和隊列空兩種情況

1.入隊：將尾指針后移一下另绩，然后儒陨，將數(shù)據(jù)放到尾指針位置；（需要先判斷隊列是否還沒滿）

2.出隊：將頭指針位置的數(shù)據(jù)取出笋籽，然后蹦漠，后移頭指針；（需要先判斷是否有數(shù)據(jù)可以出隊）

3.判斷隊列的空滿問題：

這種方式下车海，在操作出入隊之前笛园，尾指針正好指向隊尾，頭指針正好指向隊頭

所以侍芝，尾指針數(shù)值 - 頭指針數(shù)值 +1 = 當(dāng)前隊列數(shù)據(jù)量研铆，我們判斷這個計算出的當(dāng)前隊列數(shù)據(jù)量，如果等于最大容量就說明隊列滿了州叠，如果等于0就說明隊列是空的

4.初始化隊列：

初始化隊列時棵红，首先分析初始化的隊列是空的，根據(jù)判斷隊列為空的方式咧栗，發(fā)現(xiàn)逆甜，當(dāng)隊列空時，頭指針在尾指針的后一個位置楼熄；再分析第一個入隊的數(shù)據(jù)要放在數(shù)組的第一個位置忆绰，也就是索引0的位置，而入隊時先將尾指針后移可岂，再將數(shù)據(jù)放在尾指針位置错敢，所以初始化尾指針要指向-1；而頭指針要在尾指針后一位缕粹，也就是初始化頭指針指向0稚茅。

5.改進：

這樣的方式實現(xiàn)隊列后，會發(fā)現(xiàn)指針一直在后移平斩，添加到最大容量后亚享，指針就會超出邊界，即便數(shù)據(jù)都已經(jīng)出列了绘面，也無法再入隊欺税，所以其實當(dāng)指針移動到最大容量位置時侈沪，再向后移應(yīng)該是移動到第一個，讓隊列首尾相連變成一個環(huán)狀

實現(xiàn)這個的方式是晚凿，每次在移動指針后進行一次（指針%最大容量）的取余運算

但這樣會出現(xiàn)問題亭罪，原先的計算當(dāng)前數(shù)據(jù)量公式就不再正確，還需要將（結(jié)果%最大容量）進行取余運算

也可以放任指針持續(xù)后移歼秽，在取數(shù)據(jù)和插入數(shù)據(jù)的時候?qū)χ羔樔∮嘤σ郏@樣不影響計算數(shù)據(jù)量公式

實現(xiàn)方式其實并不唯一，取決于你對頭尾指針的設(shè)定

下面的代碼演示中燥筷，設(shè)定為：頭指針指向隊列頭的前一個數(shù)據(jù)箩祥，尾指針指向隊列尾

區(qū)別就是：

1.判斷隊列容量：尾指針-頭指針正好等于隊列容量，不需要加一

2.入隊出隊操作都是先移動指針肆氓，再操作數(shù)據(jù)

眼觀千遍袍祖，不如手動一遍

讀者朋友可以看完我的實現(xiàn)代碼后，自行根據(jù)上面分析與代碼不同的思路實現(xiàn)一遍谢揪，當(dāng)做一個小練習(xí)

class ArrayQueueEntity{

    /**
     * 數(shù)組最大容量
     */
    private final int maxSize;
    /**
     * 約定指向隊列頭的前一個位置
     */
    private int front;
    /**
     * 指向隊列尾
     */
    private int rear;
    /**
     * 模擬隊列用于存放數(shù)據(jù)的數(shù)組
     */
    private final int[] arr;

    /**
     * 構(gòu)造器盲泛，創(chuàng)建隊列(初始化隊列)
     * @param arrMaxSize 隊列最大容量
     */
    public ArrayQueueEntity(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //初始化時頭指針指向第一個數(shù)據(jù)的前一個（其實表示這個位置是上一次出列的數(shù)據(jù)位置）
        front = -1;
        //初始化時尾指針需要指向當(dāng)前最后一個數(shù)據(jù)的索引，但初始化隊列為空找不到隊尾键耕，所以根據(jù)空隊列判斷尾指針-頭指針=0寺滚，設(shè)置為-1
        rear = -1;
    }

    /**
     * 判斷隊列是否是滿的
     * @return true表示隊列滿了，false表示隊列沒滿
     */
    public boolean isFull(){
        return rear - front >= maxSize;
    }

    /**
     * 判斷隊列是否為空
     * @return true表示為空屈雄，false表示不為空
     */
    public boolean isEmpty(){
        return rear - front == 0;
    }

    /**
     * 添加數(shù)據(jù)到隊列
     * @param data 要添加的數(shù)據(jù)
     */
    public void addQueue(int data){
        //判斷隊列是否已滿
        if (!isFull()){
            //隊列沒滿村视，添加數(shù)據(jù)
            //隊列尾指針后移
            rear++;
            //在尾指針處添加數(shù)據(jù)(指針位置都一直在后移，所以要對數(shù)組容量取余酒奶，模擬成環(huán)形隊列)
            arr[rear%maxSize] = data;
        }else {
            //隊列滿了輸出提示
            System.out.println("隊列滿蚁孔，不能加入數(shù)據(jù)");
        }
    }

    /**
     * 獲取隊列數(shù)據(jù)/出隊列
     * @return 出隊列的數(shù)據(jù)
     */
    public int getQueue(){
        //先判斷隊列是否為空
        if (isEmpty()){
            throw new RuntimeException("隊列為空");
        }
        //不為空，取數(shù)據(jù)
        //頭指針后移一下惋嚎，指向需要出列的數(shù)據(jù)
        front++;
        //讓指針位置數(shù)據(jù)出列即可
        return arr[front%maxSize];
    }

    /**
     * 打印當(dāng)前隊列的所有數(shù)據(jù)
     */
    public void printQueue(){
        System.out.println("正在打印當(dāng)前隊列......");
        //先判斷隊列是否為空
        if (!isEmpty()){
            //不為空就遍歷打印杠氢，從頭指針的下一個遍歷到尾指針
            for (int i = front+1; i <= rear; i++) {
                System.out.println(i+":"+arr[i%maxSize]);
            }
        }else {
            System.out.println("隊列中沒有數(shù)據(jù)");
        }
    }
}

模擬上面代碼，完成小練習(xí)后另伍，可以用下面這個主方法來測試一下隊列

    public static void main(String[] args) {
        //初始化隊列——最大容量為3
        ArrayQueueEntity queue = new ArrayQueueEntity(3);
        //接收用戶輸入
        String key;
        Scanner scanner = new Scanner(System.in);
        //讓系統(tǒng)在用戶主動退出之前一直運行鼻百，并能夠輸出一個指引菜單
        boolean loop = true;
        while (loop){
            System.out.println("s(show):顯示當(dāng)前隊列狀況");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數(shù)據(jù)到隊列");
            System.out.println("g(get):從隊列取出數(shù)據(jù)");
            key = scanner.next();
            switch (key){
                case "s":
                    queue.printQueue();
                    break;
                case "e":
                    loop=false;
                    break;
                case "a":
                    if (queue.isFull()){
                        System.out.println("隊列已滿，清先出列一些數(shù)據(jù)再試");
                        break;
                    }
                    System.out.println("請輸入要入隊的數(shù)字：");
                    int data = scanner.nextInt();
                    queue.addQueue(data);
                    break;
                case "g":
                    if (queue.isEmpty()){
                        System.out.println("隊列為空摆尝，沒有數(shù)據(jù)可以出列温艇，請先嘗試添加數(shù)據(jù)入列");
                        break;
                    }
                    System.out.println("出列成功，出列數(shù)據(jù)為："+queue.getQueue());
                    break;
                default:
                    System.out.println("請根據(jù)菜單提示輸入正確指令");
            }
        }
    }