一次性數組模拟隊列

隊列先進先出，隊列的輸出、輸入分别從前端、後端處理，需要2個變量front及rear分别記錄隊列前後端的下标，front随着輸出改變，rear随着輸入改變
添加隊列元素步驟：

尾指針後移且小于最大下标

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //測試隊列
        ArrayQueue queue = new ArrayQueue(3);
        boolean loop=true;
        while (loop){
            System.out.println("添加元素請按a ：");
            System.out.println("取出元素請按g ：");
            System.out.println("顯示第一個元素請按h ：");
            System.out.println("顯示元素請按s ：");
            Scanner scanner = new Scanner(System.in);
            String key = scanner.next();
            switch (key){
                case "a":
                    System.out.println("請輸入一個數字：");
                    int n = scanner.nextInt();
                    queue.addQueue(n);
                    break;
                case "g":
                    try {
                        int i = queue.getQueue();
                        System.out.println("去除的數字是："+i);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "h":
                    try {
                        System.out.println("隊列的頭部是： "+queue.headQueue());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "s":
                    queue.showQueue();
                    break;
                case "e":
                    scanner.close();
                    loop=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程式退出.");

    }
}

class ArrayQueue{
    private int MaxSize;
    private int front;
    private int rear;
    private int[] arr;

    //初始化隊列構造函數
    public ArrayQueue(int maxSize) {
        MaxSize = maxSize;
       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 element){
        if (isfull()){
            System.out.println("隊列已滿不可添加");
            return;
        }
        rear++;
        arr[rear]=element;
    }

    //擷取隊列元素
    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];
    }

}

此代碼的弊端：

取出資料後再次展示元素還在，隻是索引front的指向發生變化
當添加元素已滿時，再全部取出，此時再添加，會顯示隊列已滿，rear=front=maxSize-1

解決方式：将數組使用算法，改為環形隊列。取模

數組模拟環形隊列

取模的了解：為了将一次性隊列改為循環隊列，引入取模的方法，%maxSize，當小于maxSize時，沒有影響；一旦等于maxSize，就會又從0開始，形成了循環。

取餘的作用就是相等時将結果置為0。

資料結構02-----------數組模拟環形隊列一次性數組模拟隊列數組模拟環形隊列隊列
無論出隊入隊，目前面元素取出rear在最後一個位置時取模才能讓繼續從0開始添加；否則會造成指針溢出。
隊列滿的了解：空時rear=front，那麼滿時可以保留一個元素空間，也就是數組中還有一個空閑單元。就表示隊列已滿。是以a4就表示數組的最後一個元素，而rear指向最後一個元素的下一個位置。

下圖是滿的兩種情況：

資料結構02-----------數組模拟環形隊列一次性數組模拟隊列數組模拟環形隊列隊列
隊列滿的條件是： （rear+1）%MaxSize==front 針對于第一種情況如果條件為 rear+1==front 的話就不滿足，需要通過取模将rear+1的值循環起來，一旦rear+1=maxSize就将rear+1至為0與front比較，此時的條件依然滿足第二種rear<front的情況，因為rear+1<maxSize,取模依舊為本值，不影響。
循環隊列有效長度的了解：如上左圖，當rear>front，隊列元素個數為rear-front；當rear<front時，如上右圖，計算元素個數分為兩段：第一段為rear-0；第二段為 maxSize-front ，相加為 rear-front+maxSize ；如果rear=0，front=0時，隊列為空，此時有效長度為0，是以需要将結果置為0，取模，是以最終公式為 （rear-front+maxSize）%maxSize 。

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //測試隊列
        CircleArrayQueue queue = new CircleArrayQueue(4);//設定是4，有效資料為3，因為有預留白間
        boolean loop=true;
        while (loop){
            System.out.println("添加元素請按a ：");
            System.out.println("取出元素請按g ：");
            System.out.println("顯示第一個元素請按h ：");
            System.out.println("顯示元素請按s ：");
            Scanner scanner = new Scanner(System.in);
            String key = scanner.next();
            switch (key){
                case "a":
                    System.out.println("請輸入一個數字：");
                    int n = scanner.nextInt();
                    queue.addQueue(n);
                    break;
                case "g":
                    try {
                        int i = queue.getQueue();
                        System.out.println("取出的數字是："+i);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "h":
                    try {
                        System.out.println("隊列的頭部是： "+queue.headQueue());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "s":
                    queue.showQueue();
                    break;
                case "e":
                    scanner.close();
                    loop=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程式退出.");

    }
}

class CircleArrayQueue{
    private int MaxSize;
    private int front;
    private int rear;
    private int[] arr;

    //初始化隊列構造函數
    public CircleArrayQueue(int maxSize) {
        MaxSize = maxSize;
       arr=new int[maxSize];
       front=0;//輸出上移 指向初始位置
       rear=0;//輸入上移  指向尾部最後一個位置的下一個位置
    }
    //判斷隊列是否滿
    public  boolean isfull(){
        return (rear+1)%MaxSize==front ;
    }

    //判斷隊列是否為空
    public boolean isempty(){
        //隊列空表示頭部索引與尾部索引重合 例如初始化的時候
        return rear==front;
    }

    //添加資料到隊列
    public  void addQueue(int element){
        if (isfull()){
            System.out.println("隊列已滿不可添加");
            return;
        }
//因為rear指向最後一個元素的後一個位置，rear索引處元素為空，直接在此處添加元素，再後移rear到下一個空位置
        arr[rear]=element;
        //rear如果在最後一個位置，要将元素添加最後一個位置後，移動到0位置時需要取模；其餘情況直接後移
        rear=(rear+1)%MaxSize;
    }

    //擷取隊列元素
    public  int getQueue(){
        if (isempty()){
          throw  new RuntimeException("隊列為空，沒有資料可取");
        }
        //front是指向隊列的第一個元素，首先先儲存front的值，然後後移front，最後傳回先儲存的值
        int value=front;
        front=(front+1)%MaxSize;
        return arr[value];

    }

    //顯示隊列的所有元素
    public void showQueue(){
        if (isempty()){
            System.out.println("隊列為空，沒有資料可取");
            return;
        }
        //如果隊列前面為空，後面一部分有元素，就沒有必要展示
        //思路：從front開始周遊有效元素個數個元素
        int length=(rear-front+MaxSize)%MaxSize;
        for (int i = front; i < front+length; i++) {
            System.out.printf("arr[%d]==%d\n",i%MaxSize,arr[i%MaxSize]);//i有可能越界是以要取模
        }
    }

    //顯示隊列頭元素
    public int headQueue(){
        if (isempty()){
            throw  new RuntimeException("隊列為空，沒有資料可取");
        }
        return arr[front];//front就是指頭元素，不需要+1
    }

}

隊列

先進先出、隊列是順序的

通路O(n)、搜尋O(N)、

插入O(1) linklist來表示、

删除O(1)， linklist來表示，删除每次隻能删除先進來的數

隊列的操作：

建立隊列、

擷取即将出隊的元素

、删除即将出隊的元素、

判斷隊列是否為空、O(1)

隊列長度、O(1)

周遊隊列(邊删除邊周遊隊列)O(N)

Leetcode933

将每次ping的請求時間節點存入隊列中，判斷目前請求時間與隊列第一個元素請求時間隻差是否小于3000，如果小于就計算隊列的長度；如果大于就删除隊列第一個元素再次計算目前元素與隊列第一個元素時間差
構造函數初始化隊列， ping方法在隊列中添加時間節點，并通過while循環來判斷目前時間節點與隊列第一個元素時間節點之差是否大于3000，大于就删除第一個元素，小于就傳回隊列長度

class RecentCounter{
    Queue<Integer> queue;
    public   RecentCounter() {
        queue= new LinkedList<>();
      }
      
      public int ping(int t){
          queue.add(t);
          while(!queue.isEmpty()&& (t-queue.peek()>3000)){
              queue.poll();
          }
          return queue.size();//傳回一個隊列長度為需求結果，是以while循環條件要反着寫

      }
}

資料結構02-----------數組模拟環形隊列一次性數組模拟隊列數組模拟環形隊列隊列

文章目錄

一次性數組模拟隊列

數組模拟環形隊列

隊列

Leetcode933

繼續閱讀

Java Map和Set

Java 優先級隊列（堆）

資料結構--時間複雜度的算法

字元串的模式比對（BF算法，KMP算法）

JAVA資料結構 - 單向環形連結清單與約瑟夫問題

java 集合 Collection（List、Set）集合

java輸入一個連結清單，按連結清單值從尾到頭的順序傳回一個ArrayList

Java資料結構 List Map Set Collection Collections集合Collection接口集set清單List映射表MapCollections類用于同步集合，還能改變集合隻讀方式的類Collection與Collectiions的差別

java實作帶頭結點的單連結清單（增删改查）

4、逆波蘭表達式求值——棧（java資料結構）

Java實作循環連結清單，實作連結清單的基本操作

單連結清單的基本操作-Java實作

二叉樹的鍊式存儲結構（線索二叉樹）

Java—排序1.插入排序2.希爾排序3.選擇排序4.堆排序5.快速排序6.冒泡排序7.歸并排序8.總結

java資料結構資料結構

TreeMap使用案例-多個映射（簡單版）