Java隊列數據結構的實現方法是什么

這篇文章主要介紹“Java隊列數據結構的實現方法是什么”，在日常操作中，相信很多人在Java隊列數據結構的實現方法是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java隊列數據結構的實現方法是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

1.隊列的基本概念

什么是隊列?

• 隊列是一種特殊的線性表

• 它只允許在表的前端（隊頭）進行刪除操作

• 在表的后端（隊尾）進行插入操作

• 隊列是一個有序表(可以用數組或鏈表實現)

• 隊列先進先出

• 隊列開辟的是一塊連續的空間

順序隊列中的溢出現象：

• 真溢出：當隊列滿時，做進棧運算產生空間溢出的現象。

• 假上溢：由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。

2.循環隊列

在實際使用隊列時，為了使隊列空間能重復使用，往往對隊列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把隊列空間想象成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。除了一些簡單應用之外，真正實用的隊列是循環隊列

3.實現思路

由于普通隊列存在溢出問題所以這里用數組來實現環形隊列

• 1、front指向隊列的首元素 初始為0

• 2、rear指向隊列尾元素的后一個位置 (空出來的一塊空間作為約定)初始為0

• 3、隊列滿的條件：(rear+1) % maxSize = front

• 4、隊列空的條件：rear = front

• 5、隊列中元素的個數：(rear+maxSize-front) % maxSize

為什么隊列滿的條件是(rear+1) % maxSize = front

(1)假設rear>front
rear-front=maxSize-1
rear+1-maxSize=front
由于當rear>front隊列滿時rear+1一定等于maxSize
(rear+1) % maxSize = rear+1-maxSize =0
(2)假設front>rear
front-rear=1
rear+1=front
由于當front>rear時rear+1一定小于maxSize
所以(rear+1) % maxSize=rear+1
(3)有上述所示可以得出隊列滿的條件是(rear+1) % maxSize = front
元素個數的計數與這相似

4.代碼實現

public class Queue {
    private int maxSzie; //隊列中能存儲的最大個數
    private int frontPoint; //頭指針指向隊頭
    private int rearPoint; //尾指針指向隊尾的后一個數據
    private int[] array; //模擬隊列的數組

    /**
     * 初始化隊列
     */
    public Queue(int max) {
        maxSzie = max;
        frontPoint = 0;
        rearPoint = 0;
        array = new int[max];
    }

    /**
     * 判斷隊列是否為空
     */
    public boolean isEmpty(){
        return frontPoint == rearPoint;
    }
    /**
     * 判斷隊列是否已滿
     */
    public boolean isFull(){
        return (rearPoint+1)%maxSzie == frontPoint;
    }
    /**
     * 向隊列中添加數據
     */
    public void add(int x){
        if (isFull()){
            System.out.println("當前隊列已滿");
            return;
        }
        //添加數據
        array[rearPoint] = x ;
        //后移尾指針
        rearPoint = (rearPoint+1) % maxSzie;
        System.out.println("添加成功");
    }
    /**
     * 取出隊列中的數據
     */
    public int remove(){
        if (isEmpty()){
            throw new RuntimeException("當前隊列為空");
        }
        //把隊頭的值賦值給臨時變量
        int x = array[frontPoint];
        //移除數據后頭指針需要向后移動 時其指向新的隊頭
        frontPoint = (frontPoint+1) % maxSzie;
        System.out.println("移除成功");
        return x;
    }
    /**
     * 獲取隊列頭數據
     */
    public int gethead(){
        if (isEmpty()){
            throw new RuntimeException("當前隊列為空");
        }
        return array[frontPoint];
    }
    /**
     * 遍歷隊列
     */
    public void show(){
        int x = 0;
       for (int i = frontPoint; i <= (rearPoint+maxSzie-frontPoint)%maxSzie; i++) {
            x++;
            System.out.println("隊列的第"+x+"個數據是"+array[i]);
        }
    }
}

public class QueueTest {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        Scanner scanner = new Scanner(System.in);
        char systemIn = ' ';
        boolean noEnd = true;
        while (noEnd){
            System.out.println("a:add(添加數據)");
            System.out.println("r:remove(刪除數據)");
            System.out.println("h:head(獲取隊頭)");
            System.out.println("s:show(遍歷隊列)");
            System.out.println("e:exit(退出程序)");
            System.out.println("請輸入字符");
            systemIn = scanner.next().charAt(0);
            switch (systemIn){
                case 'a':
                    System.out.println("請輸入入隊的數據(數字)");
                    int x = Integer.parseInt(scanner.next());
                    queue.add(x);
                    break;
                case 'r':
                    queue.remove();
                    break;
                case 'h':
                    int head = queue.gethead();
                    System.out.println("隊頭是"+head);
                    break;
                case 's':
                    queue.show();
                    break;
                case 'e':
                    noEnd = false;
                    break;
            }
        }
    }
}

5.測試

插入元素:

當添加到第五個的時候隊列已滿插入失敗:

遍歷隊列:

移除元素:

查看隊頭:

刪除一個元素后再次遍歷隊列:

到此，關于“Java隊列數據結構的實現方法是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！