共计 3402 个字符，预计需要花费 9 分钟才能阅读完成。
用数组实现环形队列的特点是高效。
- 能快速判断队列是否 满 / 空；
- 能快速存取数据。
因为简单高效，所以甚至在硬件中都实现了环形队列。
环形队列广泛应用于网络数据的收发，和不同应用间数据交换（内核和应用程序大量交换数据，从硬件接受大量数据）
内存上没有环形结构，因此环形队列实际上用数组的线性空间来实现。
但是当数据到了尾部如何处理呢？它将转回到 0 位置来处理。这个转回是通过取模操作来执行的。
因此，环形队列是逻辑上将数组元素 q[0] 和 q[maxSize – 1] 连接，形成一个存放队列的环形空间。
为了方便读写，还要用数组下标来指明队列的读写位置。head/tail. 其中 head 指向可以读的位置，tail 指向可以写的位置。
环形队列的关键是判断队列为空，还是为满。当 tail 追上 head 时，队列为满时，当 head 追上 tail 时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.
如何判断环形队列为空，为满有两种判断方法。
一. 附加一个标志位 tag
- 当 head 赶上 tail，队列空，则令 tag=0,
- 当 tail 赶上 head，队列满，则令 tag=1,
二. 限制 tail 赶上 head，即队尾结点与队首结点之间至少留有一个元素的空间。
- 队列空：head==tail
- 队列满：(tail+1)% MAXN ==head
package ds.queue;
/**
* 用数组实现环形队列
* 附加标志位法
*/
public class ArrayCircleQueue {private int[] arr;
private int maxSize;
private int rear;
private int front;
// 当 front 赶上 rear，说明队列满，令 flag=0；// 当 rear 赶上 front，说明队列空，令 flag=1
private int flag;
public ArrayCircleQueue(int size) {
maxSize = size;
arr = new int[maxSize];
front = 0;
rear = 0;
flag = 1;
}
public boolean isFull() {return front == rear && flag == 0;}
public boolean isEmpty() {return front == rear && flag == 1;}
public int peek() {if (isEmpty()) throw new RuntimeException("queue is empty!!!");
return arr[front];
}
public void offer(int v) {if (isFull()) {System.out.println("queue is full, could not add.");
return;
}
arr[rear] = v;
rear = (rear + 1) % maxSize;
if (rear == front) flag = 0;
}
public int poll() {if (isEmpty()) throw new RuntimeException("queue is empty!");
int res = arr[front];
front = (front + 1) % maxSize;
if (front == rear) flag = 1;
return res;
}
public void show() {if (isEmpty()) {System.out.println("The queue is empty!!!");
return;
}
System.out.println("front -> rear");
for (int i = front; i < front + size(); i++) {System.out.print(arr[i % maxSize] + " ");
}
System.out.println();}
public int size() {if (rear > front) return rear - front;
return rear + maxSize - front;
}
}
package ds.queue;
/**
* 数组实现环形队列
* - 预留空间法
*/
public class ArrayCircleQueue2 {
private int maxSize;
private int front; // 指向队列的第一个元素，arr[front] 就是队列的第一个元素。初始值 0
private int rear; // 指向队列的最后一个元素的后一个位置，希望空出一个空间作为约定。初始值 0
private int[] arr;
public ArrayCircleQueue2(int size) {
maxSize = size;
arr = new int[size];
}
public boolean isFull() {return (rear + 1) % maxSize == front;
}
public boolean isEmpty() {return front == rear;}
public void offer(int v) {if (isFull()) {System.out.println("queue is full!!!");
return;
}
arr[rear] = v;
rear = (rear + 1) % maxSize;
}
public int poll() {if (isEmpty()) throw new RuntimeException("queue is empty!!!");
int res = arr[front];
front = (front + 1) % maxSize;
return res;
}
public int size() {return (rear + maxSize - front) % maxSize;
}
public int peek() {if (isEmpty()) throw new RuntimeException("queue is empty");
return arr[front];
}
public void show() {if (isEmpty()) {System.out.println("queue is empty!!!");
return;
}
System.out.println("Front -> rear");
for (int i = front; i < front + size(); i++) {System.out.print(arr[i % maxSize]);
}
System.out.println();}
}
测试代码
package ds.queue;
import java.util.Scanner;
/**
*/
public class QueueDemo {public static void main(String[] args) {ArrayCircleQueue q = new ArrayCircleQueue(5);
char c;
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {System.out.println("s: 显示队列");
System.out.println("e: 退出应用");
System.out.println("a: 元素入队尾");
System.out.println("g: 从队头取出元素");
System.out.println("h: 查看队头元素");
c = scanner.next().charAt(0);
switch (c) {
case 's':
q.show();
break;
case 'a':
System.out.println("请输入一个数");
int v = scanner.nextInt();
q.offer(v);
break;
case 'g':
try {int res = q.poll();
System.out.println("取出了" + res);
} catch (Exception e) {System.out.println(e.getMessage());
}
break;
case 'h':
try {int res = q.peek();
System.out.println("队头元素" + res);
} catch (Exception e) {System.out.println(e.getMessage());
}
break;
case 'e':
loop = false;
break;
default:
break;
}
}
}
}
参考:
https://blog.csdn.net/sking00…
以及 韩顺平数据结构
正文完
