一、概述

队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出（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]=%d\n", 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("出队: %d\n", arr[head]);head = -1;tail = -1;return true;}System.out.printf("出队: %d\n", 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]=%d\n", i % maxSize, arr[i % maxSize]);}}
}

四、Java队列用法

初始化：Queue<String> queue = new LinkedList<String>();
入队：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<String> queue = new LinkedList<String>();//添加元素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);}}
}