Java隊列數據結構的實現

1.隊列的基本概念

什麼是隊列?

  • 隊列是一種特殊的線性表
  • 它隻允許在表的前端(隊頭)進行刪除操作
  • 在表的後端(隊尾)進行插入操作
  • 隊列是一個有序表(可以用數組或鏈表實現)
  • 隊列先進先出
  • 隊列開辟的是一塊連續的空間

在這裡插入圖片描述

順序隊列中的溢出現象:

  • 真溢出:當隊列滿時,做進棧運算產生空間溢出的現象。
  • 假上溢:由於入隊和出隊操作中,頭尾指針隻增加不減小,致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於向量空間的規模時,也可能由於尾指針已超越向量空間的上界而不能做入隊操作。

在這裡插入圖片描述

2.循環隊列

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

在這裡插入圖片描述

3.實現思路

由於普通隊列存在溢出問題所以這裡用數組來實現環形隊列

  • 1、front指向隊列的首元素 初始為0
  • 2、rear指向隊列尾元素的後一個位置 (空出來的一塊空間作為約定)初始為0
  • 3、隊列滿的條件:(rear+1) % maxSize = front
  • 4、隊列空的條件:rear = front
  • 5、隊列中元素的個數:(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>rearrear+1一定小於maxSize
所以(rear+1) % maxSize=rear+1
(3)有上述所示可以得出隊列滿的條件是(rear+1) % maxSize = front
元素個數的計數與這相似

4.代碼實現

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

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

在這裡插入圖片描述

插入元素:

在這裡插入圖片描述

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

在這裡插入圖片描述

遍歷隊列:

在這裡插入圖片描述

移除元素:

在這裡插入圖片描述

查看隊頭:

在這裡插入圖片描述

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

在這裡插入圖片描述

到此這篇關於Java隊列數據結構的實現的文章就介紹到這瞭,更多相關Java隊列數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: