环形队列的实现 [详解在代码中]

  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 = 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 }

 

原文链接：https://www.cnblogs.com/loe-home/p/17382896.html