資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

一: 什麼是隊列?

1):隊列是一個有序清單,可以用數組或者是連結清單來實作.

2):隊列遵循先進先出的原則,即:先存入隊列的資料,要先取出,後存入隊列的資料要後取出.

如圖所示:

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

二.用數組模拟隊列的思路

1.隊列本身就是一個有序的清單如果說是使用數組的結構來存儲隊列的資料,那麼如上圖所示,其中的maxSize表示為該隊列的最大容量

2.由于用數組表示隊列,那麼隊列的輸出輸入都是從前後端來實作的,是以我們建立了兩個變量,front和rear,front表示這個模拟隊列的前後端的下标,其中front用來表示輸出資料,rear表示輸入資料,

3.當我們向隊列中添加資料時,我們需要考慮兩點:

(1).需要判斷隊列資料是否滿了,也就是尾指針rear=maxSize-1,這個時候表示資料已經滿了,

(2). 當rear=front=-1時,說明該隊列為空列,添加資料時需要将rear+1

(3).當我們擷取隊列中的資料時,我們需要考慮隊列中的資料是否為空

代碼展示:

package com.qiu.queue;

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
//測試一下
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' ';//接受使用者輸入
        Scanner scanner = new Scanner(System.in);
        boolean flag =true;
        while (flag){
            System.out.println("s(show): 顯示隊列");
            System.out.println("e(exit): 退出程式");
            System.out.println("a(add): 添加隊列資料");
            System.out.println("g(get): 從隊列中取出資料");
            System.out.println("h(head): 檢視隊列的頭資料");

            key = scanner.next().charAt(0);//接受一個字元

            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("請輸入一個數:");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try{
                        int res =arrayQueue.getQueue();
                        System.out.printf("取出的資料是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try{
                        int res =arrayQueue.headQueue();
                        System.out.printf("隊列頭的資料是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();//不退出就會被警告
                    flag=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程式退出");
    }
}
//編寫一個類,使用數組模拟隊列-編寫一個ArrayQueue類
class ArrayQueue{
    private int maxSize;//最大容量
    private int front;//隊列尾部
    private int rear;//隊列頭部
    private  int[] arr;//模拟這個隊列

    //建立一個隊列的構造器
    public ArrayQueue (int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];

        front = -1;//指向隊列頭部,也就是隊列頭的前一個位置
        rear  = -1;//指向隊列尾部,指向隊列尾部的具體的位置,直接指向隊列的尾部
    }
    //判斷隊列是否滿了
    public boolean isFull(){
        return rear == maxSize-1;
    }
    //判斷隊列是否為空
    public boolean isEmpty(){
        return rear ==front;
    }
    //添加資料到隊列
    public void addQueue(int n){
        //判斷隊列是否滿了
        if (isFull()){
            System.out.println("隊列滿了,無法新加資料");
            return;
        }
        rear++;//讓rear後移
        arr[rear] = n;
    }

    //擷取隊列資料時,也就是出隊列
    public int getQueue(){
        //判斷隊列是否為空
        if (isEmpty()){
            //通過抛出異常來處理
            throw new RuntimeException("隊列空,不能取資料");
        }
        front++;//本身就是指向前面的一個位置
        return arr[front];
    }
    //顯示隊列的所有數資料
    public void showQueue(){
        //周遊,第一步先做判斷,這個隊列是否為空
        if (isEmpty()){
            System.out.println("這個隊列裡面沒有資料喲");
            return;
        }
        for (int i = 0; i <arr.length ; i++) {
            System.out.printf("arr[%d] =%d\n",i,arr[i]);
        }
    }
    //顯示隊列的頭數劇,注意不是取出資料
    public int  headQueue(){
        //判斷
        if (isEmpty()){

            throw new RuntimeException("隊列為空,沒有資料!");
        }
        return arr[front+1];
    }

}

運作結果

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

在這裡看起來代碼沒有什麼問題,但是如果說我們在添加滿了這個隊列之後,然後取出了所有的資料,然後再去添加資料的時候,會提示隊列中的資料已經滿了

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

分析原因:我們在添加資料的時候,rear++了當rear=maxSize-1時,這個隊列的值,已經滿了,取出資料時,rear并沒有發生變化.還是rear=maxSize-1.是以導緻提醒資料滿.

問題總結:

1.目前數組使用一次之後就不能用了,未達到重複使用的效果

2.将這個資料的算法,改進成一個環形的隊列,取模的方式來完成

三:數組模拟環形隊列

在這裡我們需要對前面的數組隊列進行優化.充分利用數組,将數組看成是一個環形的{通過取模的方式來實作}

分析說明

1.尾索引的下一個為頭索引時,表示隊列為滿,即将隊列容量空出一個作為約定,這個在做判斷隊列滿的時候需要注意(rear+1)%maxSize ==front時,表示該隊列已經滿了

2.rear = =front時表示隊列為空

3.示意圖

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

代碼示範

package com.qiu.queue;

import java.util.Scanner;

public class CircleArrayQueue {
    public static void main(String[] args) {
        //測試一下
        System.out.println("測試環形數組===========");
        CirCleArray arrayQueue = new CirCleArray(4);
        char key = ' ';//接受使用者輸入
        Scanner scanner = new Scanner(System.in);
        boolean flag =true;
        while (flag){
            System.out.println("s(show): 顯示隊列");
            System.out.println("e(exit): 退出程式");
            System.out.println("a(add): 添加隊列資料");
            System.out.println("g(get): 從隊列中取出資料");
            System.out.println("h(head): 檢視隊列的頭資料");

            key = scanner.next().charAt(0);//接受一個字元

            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("請輸入一個數:");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try{
                        int res =arrayQueue.getQueue();
                        System.out.printf("取出的資料是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try{
                        int res =arrayQueue.headQueue();
                        System.out.printf("隊列頭的資料是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();//不退出就會被警告
                    flag=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程式退出");
    }
}

class CirCleArray{
    private int maxSize;//最大容量
    //front的含義做一個調整,front指向隊列中的第一個元素,也就是說arr[front]就是第一個元素
    //初始值為0
    private int front;
    //rear的含義做一個調整,rear指向隊列中的倒數第二個元素,也就是說arr[rear]就是倒數第二個元素
    //初始值為0
    private int rear;
    private  int[] arr;//模拟這個隊列

    public CirCleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    //判斷隊列是否滿了
    public boolean isFull(){
        return (rear+1) % maxSize == front;
    }
    //判斷隊列是否為空
    public boolean isEmpty(){
        return rear ==front;
    }
    //添加資料到隊列
    public void addQueue(int n){
        //判斷隊列是否滿了
        if (isFull()){
            System.out.println("隊列滿了,無法新加資料");
            return;
        }
        arr[rear] =n;//第一次添加資料的時候這個rea為0,也就是加的第一個值時arr[0]
        rear = (rear+1)%maxSize;//這裡必須使用取模運算,防止越界
    }
    //擷取隊列資料時,也就是出隊列
    public int getQueue(){
        //判斷隊列是否為空
        if (isEmpty()){
            //通過抛出異常來處理
            throw new RuntimeException("隊列空,不能取資料");
        }
        //1.這裡的front就是指向隊列的第一個元素,先把front對應的值儲存到一個臨時變量
        //2.将front後移,考慮取模
        //3.将臨時變量傳回
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }
    //顯示隊列的所有數資料
    public void showQueue(){
        //周遊,第一步先做判斷,這個隊列是否為空
        if (isEmpty()){
            System.out.println("這個隊列裡面沒有資料喲");
            return;
        }
        //從front開始周遊,周遊多少個元素
        for (int i = front; i <front+size() ; i++) {
            System.out.printf("arr[%d] =%d\n",i%maxSize,arr[i%maxSize]);
        }
    }
    //求出目前隊列的有效個數
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //顯示隊列的頭數劇,注意不是取出資料
    public int  headQueue(){
        //判斷
        if (isEmpty()){

            throw new RuntimeException("隊列為空,沒有資料!");
        }
        return arr[front];
    }

}

結果示範:

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

資料結構與算法(2):用數組模拟隊列,用算法模拟環形數組

繼續閱讀

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希