Java基礎之數組模擬循環(huán)隊列

目錄

一、隊列簡(jiǎn)介

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

隊列有兩種存儲表示，順序表示和鏈式表示。順序表示可以用數組來(lái)實(shí)現。

二、數組模擬隊列

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

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

當front=0，rear=maxSize（數組的最大長(cháng)度），隊列滿(mǎn)，不能再存入數據。

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

如何解決“假溢出”的問(wèn)題呢？

答案就是循環(huán)隊列。

三、數組模擬循環(huán)隊列

將順序隊列變?yōu)橐粋€(gè)環(huán)狀空間，front、rear和隊列元素之間的關(guān)系不變，只是在循環(huán)隊列中，front、rear依次后移加1的操作可用“?！边\算來(lái)實(shí)現。

通過(guò)取模，front、rear就可以在順序表空間內以頭尾銜接的方式“循環(huán)”移動(dòng)。

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

（maxSize為數組隊列的最大長(cháng)度）

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

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

front的值同理。

寫(xiě)了這么多字，感覺(jué)還不如看代碼來(lái)得更容易理解一點(diǎn)。

四、代碼實(shí)現

數組模擬循環(huán)隊列

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) {
            //根據輸入的不同字母，進(jìn)行對應的操作
            System.out.println("a(add):添加一個(gè)數據");
            System.out.println("g(get):取出一個(gè)數據");
            System.out.println("h(head):展示頭部數據");
            System.out.println("s(show):展示所有數據");
            System.out.println("q(quit):退出程序");
            //因為判滿(mǎn)條件的緣故，隊列的最大容量實(shí)為maxSize-1
            System.out.printf("(隊列的最大容量為：%d)\n",maxSize-1);
            key = scanner.next().charAt(0);//接收一個(gè)字符
            try {
                switch (key) {
                    case 'a':
                        System.out.println("請輸入一個(gè)數：");
                        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());
            }
        }
    }
}
/**
 * 隊列的順序表示
 * 數組模擬循環(huán)隊列
 */
class CircleArrayQueue{
    private int maxSize;
    private int front;//指向頭元素所在位置
    private int rear;//指向尾元素所在位置的下一個(gè)位置
    private int arr[];//存放數據的數組

    //構造器，傳入數組最大容量值
    public CircleArrayQueue(int size){
        maxSize = size;
        front = 0;
        rear = 0;
        //雖然數組最大容量為maxSize，但實(shí)際用于存儲的只有maxSize-1
        arr = new int[maxSize];
    }
    //判空條件：front == rear
    public boolean isEmpty(){
        return front == rear;
    }
    //判滿(mǎn)條件：(rear+1)%maxSize == front
    public boolean isFull(){
        return (rear+1)%maxSize == front;
    }
    //添加數據，入隊
    public void addQueue(int n){
        //判滿(mǎn)
        checkFull();
        arr[rear] = n;
        rear = (rear+1)%maxSize;
    }
    //取出數據，出隊
    public int getQueue(){
        //判空
        checkEmpty();
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }
    //隊列中的有效值個(gè)數
    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]);
    }
    //檢測出隊列為空時(shí)，打印當前front，rear的值，拋出異常
    public void checkEmpty(){
        if (isEmpty()) {
            System.out.printf("當前front=%d,rear=%d\n",front,rear);
            throw new RuntimeException("隊列為空,不能取數據");
        }
    }
    //檢測出隊列滿(mǎn)時(shí)，打印當前front，rear的值，拋出異常
    public void checkFull(){
        if(isFull()){
            System.out.printf("當前front=%d,rear=%d\n",front,rear);
            throw new RuntimeException("隊列已滿(mǎn)，不能添加數據");
        }
    }
}

五、運行結果

到此這篇關(guān)于Java基礎之數組模擬循環(huán)隊列的文章就介紹到這了,更多相關(guān)Java數組模擬循環(huán)隊列內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！