循环队列是 队列的一种特殊形式。首先介绍队列,然后引申出循环队列。
队列又称为“先进先出”FIFO线性表
限定插入操作只能在队尾进行,而删除操作只能在队首进行
队列也可以采用顺序存储结构或链表结构来实现,分别称为顺序队列和链队列
队列的顺序表示—顺序队列
用一组连续的存储单元依次存放从队首到队尾的元素,附设两个指针 head 和 tail 分别指向队首元素和队尾元素的位置,
(有的地方用 front 和 rear 表示)
![img](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
当 head = tail = 0 时表示空队列
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
当插入新元素到队尾时,tail 加 1
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
当删除队首元素时,head 加 1,上图如果把 C 也删掉,那么就 head = tail 了
tail 始终指向队列元素的下一个位置
对应的操作:
队空:head=tail
求队长:tail - head
入队:新元素按 tail 指示位置加入,再将队尾指针加 1 ,即 tail = tail + 1
出队:将 head 指示的元素取出,再将队头指针加 1,即 head = head + 1
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
下面引入循环队列
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
入队,tail 指针变化: >tail = (tail + 1)%maxsize
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
出队,head 指针变化: >head =( head + 1)%maxsize
删除数据 C,队列为空
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
依次插入数据 D,E,F,G,H,I,J,K
队列满:head = tail
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
队满和队空时,均有 head=tail
因此,只凭 head=tail 还无法区分是满还是空。
如何判定队列满还是空?
方法 1:
用一个计数变量来记载队列中的元素个数
初始化队列时 c=0;
当入队时,计数变量+ 1( c=c+1 )
当出队时,计数变量-1 (c=c-1)
当计数变量= maxsize 时,队满
当计数变量= 0 时,队空
方法 2:
牺牲一个元素空间,来区别队空或队满。
入队前,先判 Q.rear+1 是否等于 Q.front,
若是则为队满。
而当 Q.front=Q.rear 时,为队空。
上图中:当数据 J 入队后,就认为队已满,
而当数据 K 再要入队时,就拒绝入队。
当队列已经满了,如果允许覆盖之前的数据:
![这里写图片描述](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
队列已经满了之后,
继续插入数据 L,M,N,
之前的数据 D,E,F 被覆盖
此时,队列已经满了,
最新的数据是:G,H,I,J,K,L,M,N
在程序中,取队列的数据的时候,如果检测到 队列满了,
此时,需要一次性取出队列中的数据,一次性取出数据的时候,不用管 head 指针,直接按照 tail 指针指向的位置开始取数据,直到循环取到 tail-1 位置停止。最终取出的数据的个数是 队列的长度 maxsize
取出之后,可以对队列指针 head 和 tail 初始化为 0,需要将队列满整个标志设置为 False.
当应该用场景如下的时候:
- 数据是一条一条的进入队列的
- 队列中的数据是一次性读取的
一次性读取出队列中的所有数据的方式:
因为允许覆盖,有两种情况:
当队列满了之后,
需要根据 tail,从 tail 所在位置的数据,绕一圈到 tail-1 位置所在的数据,都按照顺序取出来,这些数据是按照顺序,最新的数据。
当队列没有满的时候,
队列中所有的数据是 Head 到 tail 之间的所有数据。
这里采用方式 2 来进行代码演示
参考代码:
分析:
- 当队列满时,条件是(rear + 1) % maxSize = front
- 队列为空的条件: rear == front
- 队列有效数据个数:(rear + maxSize - front) % maxSize
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
| import java.util.Scanner;
public class CircleArrayQueueDemo { public static void main(String[] args) { System.out.println("测试数组模拟环形队列的案例~~~~~"); CircleArray circleArray = new CircleArray(4); char key = ' '; Scanner scanner = new Scanner(System.in); boolean loop = true; while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 推出队列"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0); switch (key) { case 's': try { circleArray.showQueue(); break; } catch (Exception e) { System.out.println(e.getMessage()); break; } case 'a': System.out.println("请输入一个数"); int value = scanner.nextInt(); circleArray.addQueue(value); break; case 'g': try { int res = circleArray.getQueue(); System.out.printf("取出的数据是: %d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int res = circleArray.headQueue(); System.out.printf("队列头数据是:%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("退出队列~~~"); } }
class CircleArray { private int maxSize; private int front; private int rear; private int[] arr;
public CircleArray(int arrMaxSize) { this.maxSize = arrMaxSize; this.arr = new int[this.maxSize]; }
public boolean isFull() { return (rear + 1) % maxSize == front; }
public boolean isEmpty() { return rear == front; }
public void addQueue(int n) { if (isFull()) { System.out.println("队列满,不能加入数据~~~"); } arr[rear] = n; rear = (rear + 1) % maxSize; }
public int getQueue() { if (isEmpty()) { throw new RuntimeException("队列为空,不能获取数据"); } int value = arr[front]; front = (front + 1) % maxSize; return value; }
public void showQueue() { if (isEmpty()) { throw new RuntimeException("队列为空,不能获取数据"); } 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; }
public int headQueue() { if (isEmpty()) { throw new RuntimeException("队列为空,没有数据~~~~"); } return arr[front]; } }
|