Java隊列數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么

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

1.隊列的基本概念

什么是隊列?

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

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

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

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

• 隊列先進先出

• 隊列開辟的是一塊連續(xù)的空間

順序隊列中的溢出現(xiàn)象：

• 真溢出：當隊列滿時，做進棧運算產(chǎn)生空間溢出的現(xiàn)象。

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

2.循環(huán)隊列

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

3.實現(xiàn)思路

由于普通隊列存在溢出問題所以這里用數(shù)組來實現(xiàn)環(huán)形隊列

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

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

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

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

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

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

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

4.代碼實現(xiàn)

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

    /**
     * 初始化隊列
     */
    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;
    }
    /**
     * 向隊列中添加數(shù)據(jù)
     */
    public void add(int x){
        if (isFull()){
            System.out.println("當前隊列已滿");
            return;
        }
        //添加數(shù)據(jù)
        array[rearPoint] = x ;
        //后移尾指針
        rearPoint = (rearPoint+1) % maxSzie;
        System.out.println("添加成功");
    }
    /**
     * 取出隊列中的數(shù)據(jù)
     */
    public int remove(){
        if (isEmpty()){
            throw new RuntimeException("當前隊列為空");
        }
        //把隊頭的值賦值給臨時變量
        int x = array[frontPoint];
        //移除數(shù)據(jù)后頭指針需要向后移動 時其指向新的隊頭
        frontPoint = (frontPoint+1) % maxSzie;
        System.out.println("移除成功");
        return x;
    }
    /**
     * 獲取隊列頭數(shù)據(jù)
     */
    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+"個數(shù)據(jù)是"+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(添加數(shù)據(jù))");
            System.out.println("r:remove(刪除數(shù)據(jù))");
            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("請輸入入隊的數(shù)據(jù)(數(shù)字)");
                    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.測試

插入元素:

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

遍歷隊列:

移除元素:

查看隊頭:

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

到此，關(guān)于“Java隊列數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>