用数组实现环形队列的特点是高效。
- 能快速判断队列是否 满/空；
- 能快速存取数据。
因为简单高效，所以甚至在硬件中都实现了环形队列。
环形队列广泛应用于网络数据的收发，和不同应用间数据交换（内核和应用程序大量交换数据，从硬件接受大量数据）
内存上没有环形结构，因此环形队列实际上用数组的线性空间来实现。
但是当数据到了尾部如何处理呢？它将转回到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...
以及 韩顺平数据结构