佇列的模擬及環形佇列思路

定義

• 佇列是一個有序串列，可以用陣列或是鏈表來實作，
• 遵循先入先出的原則，即：先存入佇列的資料，要先取出，后存入的要后取出

模擬思路

• 佇列本身是有序串列，若使用陣列的結構來存盤佇列的資料，則佇列陣列的宣告如下圖, 其中 maxSize 是該佇列的最大容量

• 因為佇列的輸出、輸入是分別從前后端來處理，因此需要兩個變數 front及 rear分別記錄佇列前后端的下標，front 會隨著資料輸出而改變，而 rear則是隨著資料輸入而改變，如圖所示

入隊出隊操作模擬

當我們將資料存入佇列時稱為”addQueue”，addQueue 的處理需要有兩個步驟：

• 將尾指標往后移：rear+1 , 當 front == rear 時，佇列為空

• 若尾指標 rear 小于佇列的最大下標 maxSize-1，則將資料存入 rear所指的陣列元素中，否則無法存入資料，rear == maxSize - 1時，佇列滿

注意：front指向的是佇列首元素的前一個位置

實作代碼

import java.util.Scanner;
 
public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag){
            System.out.println("輸入a(add)添加資料");
            System.out.println("輸入g(get)取出資料");
            System.out.println("輸入s(show)顯示所有資料");
            System.out.println("輸入h(head)顯示頭部資料");
            System.out.println("輸入e(exit)退出程式");
            char c = scanner.next().charAt(0);
            switch (c){
                case 'a':
                    System.out.println("請輸入資料");
                    int num = scanner.nextInt();
                    queue.addNum(num);
                    break;
                case 'g':
                    try {
                        queue.getQueue();
                        System.out.println("取出成功");
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    queue.showQueue();
                    break;
                case 'h':
                    try {
                        queue.headQueue();
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    flag = false;
                    System.out.println("程式已退出");
                    break;
                default:
                    break;
            }
        }
        scanner.close();
    }
}
 
class ArrayQueue{
    private int maxSize;//佇列的大小
    private int front;//指向佇列首元素的前一個位置
    private int rear;//指向佇列的尾元素
    private int[] arr;//用陣列來實作佇列
 
    //構造方法初始化
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        front = -1;//指向的是佇列第一個元素的前一個位置
        rear = -1;
        arr = new int[maxSize];
    }
 
    /**
     * 判斷佇列是否裝滿
     * @return
     */
    public boolean isFull(){
        return rear == maxSize-1;
    }
 
    /**
     * 判斷佇列是否為空
     * @return
     */
    public boolean isEmpty(){
        return front == rear;
    }
 
    /**
     * 為佇列添加資料
     * @param num
     */
    public void addNum(int num){
        if (isFull()){
            System.out.println("佇列已經滿了,無法再加入資料");
            return;
        }
        rear++;
        arr[rear] = num;
    }
 
    /**
     * 取出佇列中的資料
     * @return
     */
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("佇列為空,不能取出資料");
        }
        front++;
        return arr[front]=0;
    }
 
    /**
     * 顯示佇列的所有資料
     */
    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]);
        }
    }
 
    /**
     * 顯示佇列的頭資料,注意不是取出資料
     * @return
     */
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("佇列為空,沒有資料");
        }
        return arr[front+1];
    }
}

　　運行結果

 注意：因先入先出的原則，front和rear最終都會在佇列頂部，所以上述佇列只能一次性使用，沒有達到復用的效果，因此我們要用到環形佇列

環形佇列

思路：

• front變數含義調整：front變數指向隊首元素，初值為0
• rear變數含義調整：rear變數指向隊尾元素的下一個元素，初值為0，規定空出一個位置
• 佇列為空的判定條件：front == rear
• 佇列為滿的判定條件：(rear + 1) % maxSize == front
• 佇列中有效元素的個數：(rear - front + maxSize) % maxSize
• 入隊和出隊時，都需要讓標記對maxSize取模

• import java.util.Scanner;
   
  public class CyclicArrayQueueDemo {
      public static void main(String[] args) {
          CyclicArrayQueue queue = new CyclicArrayQueue(3);
          Scanner scanner = new Scanner(System.in);
          boolean flag = true;
          while (flag){
              System.out.println("輸入a(add)添加資料");
              System.out.println("輸入g(get)取出資料");
              System.out.println("輸入s(show)顯示所有資料");
              System.out.println("輸入h(head)顯示頭部資料");
              System.out.println("輸入e(exit)退出程式");
              char c = scanner.next().charAt(0);
              switch (c){
                  case 'a':
                      System.out.println("請輸入資料");
                      int num = scanner.nextInt();
                      queue.addNum(num);
                      break;
                  case 'g':
                      try {
                          int n = queue.getQueue();
                          System.out.println("取出的數是:"+n);
                      }catch (Exception e){
                          System.out.println(e.getMessage());
                      }
                      break;
                  case 's':
                      queue.showQueue();
                      break;
                  case 'h':
                      try {
                          queue.headQueue();
                      }catch (Exception e){
                          System.out.println(e.getMessage());
                      }
                      break;
                  case 'e':
                      flag = false;
                      System.out.println("程式已退出");
                      break;
                  default:
                      break;
              }
          }
          scanner.close();
      }
  }
   
  class CyclicArrayQueue {
      private int maxSize;//佇列的大小
      private int front;//front變數指向隊首元素，初值為0
      private int rear;//rear變數指向隊尾元素的下一個元素，初值為0，規定空出一個位置
      private int[] arr;//用陣列來實作佇列
   
      public CyclicArrayQueue(int maxSize) {
          this.maxSize = maxSize;
          arr = new int[maxSize];
      }
   
      /**
       * 判斷佇列是否裝滿
       *
       * @return
       */
      public boolean isFull() {
          return (rear + 1) % maxSize == front;
      }
   
      /**
       * 判斷佇列是否為空
       *
       * @return
       */
      public boolean isEmpty() {
          return front == rear;
      }
   
      /**
       * 為佇列添加資料
       *
       * @param num
       */
      public void addNum(int num) {
          if (isFull()) {
              System.out.println("佇列已經滿了,無法再加入資料");
              return;
          }
          arr[rear] = num;
          rear = (rear + 1) % maxSize;
      }
   
      /**
       * 取出佇列中的資料
       *
       * @return
       */
      public int getQueue() {
          if (isEmpty()) {
              throw new RuntimeException("佇列為空,不能取出資料");
          }
          int value = https://www.cnblogs.com/wyh518/p/arr[front];
          front = (front + 1) % maxSize;
          return value;
      }
   
      /**
       * 顯示佇列的所有資料
       */
      public void showQueue() {
          if (isEmpty()) {
              System.out.println("佇列為空,沒有資料");
              return;
          }
          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;
      }
   
      /**
       * 顯示佇列的頭資料,注意不是取出資料
       * @return
       */
      public int headQueue(){
          if (isEmpty()){
              throw new RuntimeException("佇列為空,沒有資料");
          }
          return arr[front];
      }
  }
  

  　　

標籤：Java

上一篇：Java基礎（識別符號，資料型別，資料轉換，變數）

下一篇：Spring（八）：Bean的作用域