怎么在Java中利用數組模擬循環隊列

怎么在Java中利用數組模擬循環隊列？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

Java有哪些集合類

Java中的集合主要分為四類：1、List列表：有序的，可重復的；2、Queue隊列：有序，可重復的；3、Set集合：不可重復；4、Map映射：無序，鍵唯一，值不唯一。

一、隊列簡介

隊列是一個有序列表，遵循“先入先出”的原則，即先存入隊列的數據要先取出，后存入的數據后取出。

隊列有兩種存儲表示，順序表示和鏈式表示。順序表示可以用數組來實現。

二、數組模擬隊列

用數組模擬隊列時，設兩個值front=0，rear=0。front表示隊列首部第一個數據所在位置，rear表示尾部最后一個數據的下一個位置。

將數據插入數組隊列時（入隊），從尾部進行插入,即array[rear] = value,同時rear后移，rear++。取出數據時（出隊），從頭部取出數據,value = array[front]，同時front后移front++。

當front=0，rear=maxSize（數組的最大長度），隊列滿，不能再存入數據。

這時如果執行出隊操作，又有空間可以存儲，但繼續插入數據，會出現溢出現象，即因數組越界而導致程序非法操作錯誤。而實際上空間并未占滿，所以稱這種現象為“假溢出”。這是由“隊尾入隊，隊頭出隊”的限制操作所造成的。

如何解決“假溢出”的問題呢？

答案就是循環隊列。

三、數組模擬循環隊列

將順序隊列變為一個環狀空間，front、rear和隊列元素之間的關系不變，只是在循環隊列中，front、rear依次后移加1的操作可用“模”運算來實現。

通過取模，front、rear就可以在順序表空間內以頭尾銜接的方式“循環”移動。

元素出隊后，front = （front+1）%maxSize ；
元素入隊后，rear = （rear+1）%maxSize 。

（maxSize為數組隊列的最大長度）

例如，隊列最大長度為4，當rear=3時，存入數據，array[3]=value,rear后移一位，如果沒有取模運算，則rear=4，這時繼續插入數據，array[4]越界。

如果進行取模運算，rear = （rear+1）%maxSize ，這時rear=0，rear又重新回到了0的位置。這樣的運算，使得rear的值在0、1、2、3之間循環。

front的值同理。

寫了這么多字，感覺還不如看代碼來得更容易理解一點。

四、代碼實現

數組模擬循環隊列

package com.ArrayQueue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String args[]){
        int maxSize = 4;
        CircleArrayQueue queue = new CircleArrayQueue(maxSize);
        Scanner scanner = new Scanner(System.in);
        char key;
        boolean loop = true;
        while (loop) {
            //根據輸入的不同字母，進行對應的操作
            System.out.println("a(add):添加一個數據");
            System.out.println("g(get):取出一個數據");
            System.out.println("h(head):展示頭部數據");
            System.out.println("s(show):展示所有數據");
            System.out.println("q(quit):退出程序");
            //因為判滿條件的緣故，隊列的最大容量實為maxSize-1
            System.out.printf("(隊列的最大容量為：%d)\n",maxSize-1);
            key = scanner.next().charAt(0);//接收一個字符
            try {
                switch (key) {
                    case 'a':
                        System.out.println("請輸入一個數：");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                        System.out.println("數據添加成功。");
                        break;
                    case 'g':
                        System.out.printf("取出的數據為：%d\n", queue.getQueue());
                        break;
                    case 'h':
                        queue.headQueue();
                        break;
                    case 's':
                        queue.showQueue();
                        break;
                    case 'q':
                        scanner.close();
                        loop = false;
                        System.out.println("程序已退出。");
                        break;
                    default:
                        break;
                }
            } catch (RuntimeException e) {
                System.out.println(e.getMessage());
            }
        }
    }
}
/**
 * 隊列的順序表示
 * 數組模擬循環隊列
 */
class CircleArrayQueue{
    private int maxSize;
    private int front;//指向頭元素所在位置
    private int rear;//指向尾元素所在位置的下一個位置
    private int arr[];//存放數據的數組

    //構造器，傳入數組最大容量值
    public CircleArrayQueue(int size){
        maxSize = size;
        front = 0;
        rear = 0;
        //雖然數組最大容量為maxSize，但實際用于存儲的只有maxSize-1
        arr = new int[maxSize];
    }
    //判空條件：front == rear
    public boolean isEmpty(){
        return front == rear;
    }
    //判滿條件：(rear+1)%maxSize == front
    public boolean isFull(){
        return (rear+1)%maxSize == front;
    }
    //添加數據，入隊
    public void addQueue(int n){
        //判滿
        checkFull();
        arr[rear] = n;
        rear = (rear+1)%maxSize;
    }
    //取出數據，出隊
    public int getQueue(){
        //判空
        checkEmpty();
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }
    //隊列中的有效值個數
    public int size(){
        return (rear-front+maxSize)%maxSize;
    }
    //展示隊列的所有數據
    public void showQueue(){
        //判空
        checkEmpty();
        for(int i=front;i<front+size();i++){
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
        System.out.printf("當前front=%d,rear=%d\n",front,rear);
    }
    //展示位于隊列頭部的元素值，不改變front的指向
    public void headQueue(){
        //判空
        checkEmpty();
        System.out.printf("頭部數據是：%d\n",arr[front]);
    }
    //檢測出隊列為空時，打印當前front，rear的值，拋出異常
    public void checkEmpty(){
        if (isEmpty()) {
            System.out.printf("當前front=%d,rear=%d\n",front,rear);
            throw new RuntimeException("隊列為空,不能取數據");
        }
    }
    //檢測出隊列滿時，打印當前front，rear的值，拋出異常
    public void checkFull(){
        if(isFull()){
            System.out.printf("當前front=%d,rear=%d\n",front,rear);
            throw new RuntimeException("隊列已滿，不能添加數據");
        }
    }
}

五、運行結果

關于怎么在Java中利用數組模擬循環隊列問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。