- 一、概述
- 二、数组模拟队列
- 三、数组模拟环形队列
- 四、Java队列用法
队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出（FIFO）的原则。即：先存入队列的数据，要先取出。后存入的要后取出
二、数组模拟队列队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。
数组模拟队列代码（Java）：
class ArrayQueue {
private int maxSize; // 数组最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 用于存放数据，模拟队列
// 队列构造器
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
// 判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int n) {
if (isFull()) {
return;
}
arr[++rear] = n;
}
// 获取队列数据，出队
public int getQueue() {
if (isEmpty()) {
// 抛出异常
throw new RuntimeException("队列空，不能取数据");
}
return arr[++front];
}
// 显示队列所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%dn", i, arr[i]);
}
}
// 显示队列头部（不是取出数据）
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，没有数据");
}
return arr[front+1];
}
}
但是存在一个问题：数据加满后，即使取出全部的数据也不能再添加新的数据了。因为rear和front的值均已达到MaxSize-1，后面将用数组模拟环形队列解决该问题。
三、数组模拟环形队列 思路
1 head为队列将要取出元素的索引，head初始值为-1，当入队第一个元素后head设置为0。在出队时，要先取出元素，再head++。
2 tail为队列刚刚插入元素的索引，tail初始值为-1，在 入队时，先tail++，再存入元素。
3 队列已满：(tail + 1) % maxSize = head
4 队列为空：head=-1，当队列最后一个元素取出后就令head=-1，tail=-1。
5 队列中有效数据个数：在不为空或满的情况下为 (tail + maxSize - head + 1) % maxSize
当head=1，tail=0时，队列已满，此时tail+ 1 = 1等于head；
当head=0，tail=maxSize-1时，队列已满，此时rear + 1 = maxSize并不等于head，而(tail+ 1) % maxSize = head
假设maxSize=5
当head=1，tail=3时，队列有效元素为tail- head+ 1 = 3，也可以(tail+ maxSize - head + 1) % maxSize = 3
当head=3，tail=1时，队列有效元素不为tail- head+ 1= -1，应为(tail+ maxSize - head + 1 ) % maxSize = 4
代码
// 使用数组模拟队列，编写一个ArrayQueue类
class CircleArrayQueue {
private int[] arr; // 用于存放数据，模拟队列
private int head; // 队列头索引
private int tail; // 队列尾索引
private int maxSize; // 数组大小
// 队列构造器
public CircleArrayQueue(int k) {
arr = new int[k];
head = -1;
tail = -1;
maxSize = k;
}
// 判断队列是否满
public boolean isFull() {
return (tail + 1) % maxSize == head;
}
// 判断队列是否为空
public boolean isEmpty() {
return head == -1;
}
// 添加数据到队列
public boolean enQueue(int value) {
if (isFull()) {
System.out.println("队列已满，不能添加数据");
return false;
}
if (isEmpty()) {
head = 0;
}
tail = (tail + 1) % maxSize;
arr[tail] = value;
return true;
}
// 获取队列数据，出队
public boolean deQueue() {
if (isEmpty()) {
System.out.println("队列为空，不能取数据");
return false;
}
if (head == tail) {
System.out.printf("出队: %dn", arr[head]);
head = -1;
tail = -1;
return true;
}
System.out.printf("出队: %dn", arr[head]);
head = (head + 1) % maxSize;
return true;
}
// 显示队列头部（不是取出数据）
public int getFront() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据");
}
return arr[head];
}
public int getRear() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据");
}
return arr[tail];
}
// 获取队列数据个数
public int size() {
if (isEmpty()) {
return 0;
} else if (isFull()) {
return maxSize;
}
return (tail - head + maxSize + 1) % maxSize;
}
// 显示队列所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空");
}
// 从front开始遍历，遍历多少个元素
for (int i = head; i < head + size(); i++) {
System.out.printf("arr[%d]=%dn", i % maxSize, arr[i % maxSize]);
}
}
}
四、Java队列用法
初始化：Queue
入队：queue.offer("a");
出队：queue.poll()
返回第一个元素：queue.peek()
import java.util.linkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
//add()和remove()方法在失败的时候会抛出异常(不推荐)
Queue queue = new linkedList();
//添加元素
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("element="+queue.element()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("peek="+queue.peek()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
}
}
