環形佇列的實作 [詳解在代碼中]

  1 package DataStructures.Queue.Array.Exerice;
  2 
  3 /**
  4  * @author Loe.
  5  * @project DataStructures&Algorithms
  6  * @date 2023/5/8
  7  * @ClassInfo 環形佇列
  8  *            主要使用取模的特性來實作環形特征
  9  */
 10 public class CirularQueue {
 11     //當前佇列大小
 12     public int maxSize;
 13     //佇列
 14     public int[] queue;
 15     //指向第一個元素
 16     public int front;
 17     //指向最后一個元素的再后一個元素
 18     public int rear;
 19 
 20     public CirularQueue(int maxSize) {
 21         this.maxSize = maxSize;
 22         //創建佇列陣列
 23         this.queue = new int[maxSize];
 24         //初始化指標
 25         this.front = 0;
 26         this.rear = 0;
 27     }
 28 
 29     public void addQueue(int data){
 30         if (this.isFull()){
 31             System.out.println("佇列已滿~");
 32 
 33         }else{
 34             //因為real指向的最后一個元素的前一個元素
 35             //所以這里可以直接使用并賦值
 36             //初始化為0可以理解為:
 37             //- 初始化時,最后一個元素的索引是 -1
 38             this.queue[this.rear] = data;
 39 
 40             //解決環形佇列問題
 41             //在以往我們需要將rear++
 42             //并且保證rear是小于maxSize即可
 43             //但環形佇列需要用一種方法來把 rear 困在 maxSize中
 44             //使其從始至終都無法超過maxSize
 45             //所以我們使用 "取模運算" 來實作
 46             this.rear = (rear + 1) % maxSize;
 47         }
 48     }
 49 
 50     /**
 51      * 取出元素方法
 52      * 在這個方法中我們需要解決 front索引指向的位置問題
 53      * 同 add 一樣,我們也需要將front困在maxSize中
 54      */
 55     public int getData(){
 56         //如果為空
 57         if (isEmpty()){
 58             System.out.println("無法取出,佇列為空~");
 59         }
 60         //由于我們需要對front進行操作
 61         //所以將front先前指向的值取出,存到一個臨時變數中
 62         int upData = https://www.cnblogs.com/loe-home/p/this.queue[this.front];
 63 
 64         //接下來對front進行操作
 65         this.front = (this.front + 1) % this.maxSize;
 66 
 67         return upData;
 68     }
 69 
 70 
 71     //展示佇列
 72     public void show(){
 73         for (int i = this.front; i < front + size(); i++) {
 74             System.out.printf("佇列元素索引[%d]=%d\n",i % this.maxSize,this.queue[i % this.maxSize]);
 75         }
 76     }
 77 
 78 
 79     //判斷是否為空
 80     public boolean isFull(){
 81         //佇列滿的條件是什么?
 82         //以往: rear == maxSize
 83         //為適配環形佇列,條件改為:
 84         //(rear + 1) % maxSize == front
 85         return (this.rear + 1) % maxSize == front;
 86     }
 87 
 88     public boolean isEmpty(){
 89         return this.rear == this.front;
 90     }
 91 
 92     //獲取當前佇列可用的元素數量
 93     public int size(){
 94         return (rear + maxSize - front) % maxSize;
 95     }
 96 
 97 
 98 
 99     public int getMaxSize() {
100         return maxSize;
101     }
102 
103     public void setMaxSize(int maxSize) {
104         this.maxSize = maxSize;
105     }
106 
107     public int[] getQueue() {
108         return queue;
109     }
110 
111     public void setQueue(int[] queue) {
112         this.queue = queue;
113     }
114 
115     public int getFront() {
116         return front;
117     }
118 
119     public void setFront(int front) {
120         this.front = front;
121     }
122 
123     public int getRear() {
124         return rear;
125     }
126 
127     public void setRear(int rear) {
128         this.rear = rear;
129     }
130 }

標籤：其他

上一篇：Codeforces Round 871 (Div. 4)

下一篇：返回列表