如何使用数组和链表来实现“队列”
与栈一样，队列（Queue）也是一种数据结构，它包含一系列元素。但是，队列访问元素的顺序不是后进先出（LIFO)，而是先进先出（FIFO）。
实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
数组实现分析下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一个位置。
入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear++，出队列的时候只需要执行front++即可。
代码实现代码语言：javascript复制/** * 数组实现队列 * * @author tian * @date 2023/4/26 */public class MyArrayQueueDemo { public static void main(String[] args) { MyQueueDemo myQueueDemo = new MyQueueDemo(); myQueueDemo.enQueue(1); System.out.println("-----向队列中添加元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.enQueue(2); System.out.println("-----向队列中添加元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.enQueue(3); System.out.println("-----向队列中添加元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.enQueue(4); System.out.println("-----向队列中添加元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); System.out.println("---------------------------"); myQueueDemo.deQueue(); System.out.println("-----从队列中取出元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.deQueue(); System.out.println("-----从队列中取出元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.deQueue(); System.out.println("-----从队列中取出元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); myQueueDemo.deQueue(); System.out.println("-----从队列中取出元素-----"); System.out.println("队列头元素 = " + myQueueDemo.getFront()); System.out.println("队列尾元素 = " + myQueueDemo.getBack()); System.out.println("队列大小 = " + myQueueDemo.size()); }}class MyQueueDemo { private List arrayList = new ArrayList(); private int front; private int rear; public MyQueueDemo() { this.front = 0; this.rear = 0; } public boolean isEmpty() { return front == rear; } public int size() { return rear - front; } //获取对手元素 public T getFront() { if (isEmpty()) { return null; } return arrayList.get(front); } //获取队列尾部元素 public T getBack() { if (isEmpty()) { return null; } return arrayList.get(rear - 1); } //删除队列中头部元素 public void deQueue() { if (rear > front) { front++; } else { System.out.println("队列已经不存在元素了"); } } //把新元素添加到队列中（队列尾部） public void enQueue(T item) { arrayList.add(item); rear++; }}运行结果
OK，自此，使用数组实现队列已经搞定。
问题出队列后数组前半部分的空间不能够充分地利用，解决这个问题的方法为把数组看成一个环状的空间（循环队列）。当数组最后一个位置被占用后，可以从数组首位置开始循环利用。
链表实现分析采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。
在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中（1）和（2）两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要（3）这一步，改变pHead指针使其指向pHead→next，此外也需要考虑结点所占空间释放的问题。
代码实现代码语言：javascript复制/** * @author tian * @date 2023/4/26 */class QueueNode { T data; QueueNode next;}class MyNodeQueue { private QueueNode head; private QueueNode end; //初始化队列 public MyNodeQueue() { end = head = null; } boolean isEmpty() { return head == null; } int size() { int size = 0; QueueNode temp = head; while (temp != null) { temp = temp.next; size++; } return size; } //入队 void enQueue(T t) { QueueNode temp = new QueueNode(); temp.data = t; temp.next = null; if (head == null) { head = end = temp; } else { end.next = temp; end = temp; } } //出队 void deQueue() { if (head == null) { System.out.println("不存在元素，出队失败"); return; } head = head.next; if (head == null) { end = null; } } //获取队首元素 T getFront() { if (head == null) { System.out.println("队列中不存在元素，获取为空"); return null; } return head.data; } //获取队尾元素 T getBack() { if (end == null) { System.out.println("队列中不存在元素，获取失败"); return null; } return end.data; }}public class MyNodeQueueDemo { public static void main(String[] args) { MyNodeQueue queue = new MyNodeQueue(); queue.enQueue(1); System.out.println("向队列中添加元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.enQueue(2); System.out.println("向队列中添加元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.enQueue(3); System.out.println("向队列中添加元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.enQueue(4); System.out.println("向队列中添加元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); System.out.println("------------------"); queue.deQueue(); System.out.println("从队列中取出元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.deQueue(); System.out.println("从队列中取出元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.deQueue(); System.out.println("从队列中取出元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); queue.deQueue(); System.out.println("从队列中取出元素"); System.out.println("头 元素=" + queue.getFront()); System.out.println("尾 元素=" + queue.getBack()); System.out.println("大小=" + queue.size()); }}运行结果
OK，使用链表实现队列到此就搞定。
总结显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链表尾元素可以非常容易地找到链表的首结点。