环形队列的实现 [详解在代码中]
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 }
热门相关:最强狂兵 战神 最强装逼打脸系统 夫人你马甲又掉了 法医娇宠,扑倒傲娇王爷