怎么在java中利用數組實現一個環形隊列

本篇文章為大家展示了怎么在java中利用數組實現一個環形隊列，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

Java是什么

Java是一門面向對象編程語言，可以編寫桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序。

及具體代碼

一、隊列是什么

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
總結起來兩點：
1.一種線性表
2.添加操作只能在表尾，刪除操作在表頭（先進先出）

二、實現隊列的思路

 1.初始化一個空隊列

初始化一個大小固定的數組，并將頭指針，尾指針都指向下表為0的位置，但其實這種初始化頭指針指向的是隊首，尾指針指向的是隊尾的后一個元素。

2.往隊列里添加元素

往隊列里添加元素，尾指針后移一位。

一直添加直到隊列滿

這個時候尾指針已經出現在數組下標外了

3.消費隊列元素

每消費一個隊列元素，頭指針指向的元素出隊，并且后移一位

再消費兩個

這個時候我們想往隊列里繼續添加元素，尾指針后移，然后發現出現了假溢出的情況，因為尾指針無法再向后移動，而隊列實際上并沒有滿，我們又無法繼續往隊列里添加數據。這個時候其實有兩種解決方案。
方案一：我們每消費一個元素，其后面的元素都整體往前移動一位，就像我們生活中排隊打飯一樣，后面的人都往前挪一挪。但這種方案帶來的后果是，帶來的時間開銷太大，因為基本上要操作所有的元素，所以這種方案不可行。
方案二：尾指針在指向下表為最后一個元素時，再添加元素，如果還有空位，就將尾指針重新指向0，頭指針在取到下表數組末尾時，如果前面還有元素，頭指針也指向0，這就是我們說的環形隊列。

三、實現環形隊列

1.環形隊列示例圖

尾指針重新指向零

再添加一個元素

連續消費三個元素，如果前面還有元素，頭指針也指向0

這個時候我們發現那個原來熟悉的隊列又回來了。

2.代碼實現

/**
 * description:數組實現環形隊列
 * author: xiaowang
 * */
public class MyQueue<E> {
    // 隊列最大個數
    private int size;
    // 元素真實個數
    private int number;
    // 頭指針，指向隊列的第一個元素即隊頭
    private int front;
    // 尾指針，指向隊尾的后一個元素(非隊尾)
    private int rear;
    // 隊列具體值
    private Object[] values;
    // 隊列滿標記，當隊列是滿的時候為true
    private boolean isFullFlag;

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

    }

    /**往隊列里添加元素 添加成功返回true 失敗返回false*/
    public boolean addToQueue(E e){
        // 判斷隊列是否已經滿了
        if (isFullFlag){
            System.out.println("隊列已滿,無法繼續添加元素");
            return false;
        }
        // 添加元素
        values[rear] = e;
        // 元素個數加一
        number++;
        // 尾指針后移一位，若已經指向數組最后的下表，則重新指向0
        if (rear == size-1){
            rear = 0;
        }else{
            rear++;
        }
        // 添加完這個元素，判斷隊列是否已經滿了，若滿則標記為true
        if (rear==front){
            isFullFlag = true;
        }
        return true;
    }
    /**從隊列里取出數據，隊頭數據*/
    public E getFromQueue(){
        // 判斷隊列是否為空
        if (number==0||size==0){
            System.out.println("隊列為空，無法從隊列中獲取數據");
            return null;
        }
        // 臨時變量
        E e = (E) values[front];
        // 隊頭置空
        values[front] = null;
        // 個數減一
        number--;
        // 頭指針后移，若已經指向數組最后的下表，則重新指向0
        if (front==size-1){
            front = 0;
        }else {
            front++;
        }
        // 取隊列之前若是滿的狀態，則更新狀態
        if (isFullFlag){
            isFullFlag = false;
        }
        return e;
    }
    /**獲取目前有幾個元素正在進行排隊*/
    public int getNumber(){
        return number;
    }
    /**獲取隊列的最大個數*/
    public int getSize(){
        return size;
    }
    /**查看隊列在數組里保存的詳細情況*/
    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("歡迎來到小王排隊系統，您可以使用以下功能。\n添加：1；取出：2；展示：3；獲取排隊個數：4；退出：0。");
            int flag = scanner.nextInt();
            switch (flag){
                case 1 :
                    System.out.println("請輸入一個數據：");
                    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("本次取出的數據為："+dataFromQueue);
                    }
                    break;
                case 3 :
                    System.out.println("隊列詳情為：\n"+queue.toString());
                    break;
                case 4 :
                    System.out.println("目前有"+queue.getNumber()+"個元素正在進行排隊");
                    break;
                default:
                    isCan = false;
                    System.out.println("已退出...");
                    break;
            }
        }

    }
}

上述內容就是怎么在java中利用數組實現一個環形隊列，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。