要点
那么,循环队列为什么用空一个元素的位置呢???
这个是根据需要来用的
循环队列中,由于入队时尾指du针向前追赶头指针;zhi出队时头指针向前追赶尾指针,造成dao队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种:
①另设一布尔变量以区别队列的空和满;
②少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
③使用一个计数器记录队列中元素的总数(即队列长度)
因为采取了第二种方法,所以要始终大1。
使用【头尾指向一个位置】的条件来判断空。使用【尾指针在头指针前一个】的条件判断满
尾指针始终指向的是一个空位置,即下一个要填入的位置
头指针在队列为空时为第一个元素的位置,队列不为空时为第一个元素的位置。实际上除了判断满和判断空的方法外,对头元素和头指针的操作都经过了空判断过滤。所以允许空和非空时含义不一致。
代码
public class CircularQueue {
public static void main(String[] args) {
Queue queue = new Queue(3);
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("p: pop");
key = scanner.next().charAt(0);
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'p':
queue.popQueue();
break;
case 'e':
scanner.close();
loop = false;
break;
}
}
}
}
class Queue {
int maxSize;
int front = 0;
int rear = 0;
int[] arr;
public Queue(int maxSize) {
this.maxSize = maxSize + 1;
arr = new int[this.maxSize];
}
public boolean isFull() {
if ((rear +1)%maxSize == front) {
System.out.println("已满");
return true;
}
return false;
}
public boolean isEmpty() {
if(front == rear){
System.out.println("为空");
return true;
}
return false;
}
public void addQueue(int data) {
if (this.isFull()) {
return;
}
System.out.println("输入");
this.arr[rear%maxSize] = data;
rear++;
}
public void popQueue() {
if (!isEmpty()) {
int value = this.arr[front % maxSize];
front++;
System.out.println(value);
}
}
public void showQueue() {
if (!isEmpty()) {
for (int i = front % maxSize; i < (rear-front)%maxSize + front % maxSize; i++) {
System.out.printf("a[%d]=%d\n", i%maxSize, arr[i%maxSize]);
}
}
}
}