Java隊列數(shù)據(jù)結構的實現(xiàn)

更新時間：2022年01月24日 17:30:12 作者：HairLossException

這篇文章主要介紹了Java隊列數(shù)據(jù)結構的實現(xiàn),隊列是一種特殊的線性表,只允許在表的隊頭進行刪除操作，在表的后端進行插入操作，隊列是一個有序表先進先出，想了解更多相關資料的小伙伴可以參考下面文章的詳細內(nèi)容

1.隊列的基本概念

什么是隊列?

隊列是一種特殊的線性表
它只允許在表的前端（隊頭）進行刪除操作
在表的后端（隊尾）進行插入操作
隊列是一個有序表(可以用數(shù)組或鏈表實現(xiàn))
隊列先進先出
隊列開辟的是一塊連續(xù)的空間

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

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

2.循環(huán)隊列

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