日撸Java三百行（day17：链队列）

目录

一、队列基础知识

1.队列的概念

2.队列的实现

二、代码实现

1.链队列创建

2.链队列遍历

3.入队

4.出队

5.数据测试

6.完整的程序代码

总结

---

一、队列基础知识

1.队列的概念

今天我们继续学习另一个常见的数据结构——队列。和栈一样，队列也是一种操作受限制的线性表，其限定在表的前端进行删除操作，在表的后端进行插入操作，删除这一端叫做队头，插入这一端叫做队尾。由于队列属于线性表的范畴，所以队列当然拥有线性表存储数据的特性，其中队列存储的数据元素称为队列元素。注意，当队列中没有数据元素时，为空队列。

在之前，我们说过栈是一种先进后出（后进先出）的线性表，而队列却完全不一样。因为队列只能在队头删除，在队尾插入，所以最先进入的元素会最早到达队头然后被删除，因此队列是一种先进先出（后进后出）的线性表。这其实有点像我们平时在电影院排队买票，第一个排队的人就最先到达队头买票，最后一个排队的人只能最晚到达队头买票。

和顺序表、链表、栈这些线性表一样，队列也有一些基本操作实现，这里我们主要介绍的是入队和出队。

• 入队：在队列中插入一个队列元素就叫做入队
• 出队：在队列中删除一个队列元素就叫做出队

2.队列的实现

在java中，队列的实现可以通过以下两种方式完成。

• 顺序队列：以数组为底层，通过顺序存储结构实现队列。分配一段连续的存储空间，用两个整型下标front和rear分别代表队头和队尾。

• 链队列：以链表为底层，通过链表存储结构来实现队列。链队列类似于一个单链表，用头指针header和尾指针tail分别指向队头和队尾。

二、代码实现

这里我们采用链队列进行模拟。

1.链队列创建

由于链队列基于链表结构，所以它的创建大体上和链表差不多，结合之前学过的链表知识可以很容易得到如下代码：

第一步，我们同样创建一个内部类Node作为结点类，并在其中定义成员变量data域和next域，以及一个基本成员方法。

public class LinkedQueue {/*** An inner class.*/class Node {/*** The data.*/int data;/*** The reference to the next node.*/Node next;/********************* * The constructor.* * @param paraValue The data.******************* */public Node(int paraValue) {data = paraValue;next = null;}// Of the constructor}// Of class Node

第二步，为了方便后续进行出队入队操作，我们提前准备一个头指针header和一个尾指针tail，并通过new关键字为其分配内存空间。

   /*** The header of the queue.*/Node header;/*** The tail of the queue.*/Node tail;/************************ Construct an empty sequential list.**********************/public LinkedQueue() {header = new Node(-1);// header.next = null;tail = header;}// Of the first constructor

2.链队列遍历

链队列的遍历我们同样通过重写toString()方法来完成，如下：

    /************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";if (header.next == null) {return "empty";} // Of ifNode tempNode = header.next;while (tempNode != null) {resultString += tempNode.data + ", ";tempNode = tempNode.next;} // Of whilereturn resultString;}// Of toString

这段代码在day13链表中有详细的分析，这里就不再重复赘述了。 

3.入队

我们知道链表在插入时，一共需要三步，分别是：第一步创建新的结点，第二步找到指定插入位置的前一个结点，第三步修改该指定插入位置前后的指针指向。但是，链队列不一样，因为队列只能在队尾插入，所以我们只需要在原尾指针之后增加一个新的结点即可，具体模拟如下：

    /************************ Enqueue.* * @param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {Node tempNode = new Node(paraValue);tail.next = tempNode;tail = tempNode;}// Of enqueue

首先，定义一个新的结点tempNode；然后通过语句tail.next = tempNode;将原尾指针与新结点链接起来（相当于在原尾指针后面插入新结点）；最后不要忘了更新尾指针，将新结点令为新的尾指针（因为尾指针始终指向队尾）。

4.出队

由于链表的存储方式是在物理空间中直接、任意创建一个新的结点，所以它并没有明确的上限，所以在上面链队列入队时，我们并没有考虑队列是否已满的问题。但是，在出队时就需要考虑队列是否为空。

在前面，我们已经定义了头指针和尾指针，当队列为空时，显然头指针等于尾指针，所以我们就把header == tail作为判断队列是否为空的条件，并且规定队列为空时返回 -1。

    /************************ Dequeue.* * @return The value at the header.**********************/public int dequeue() {if (header == tail) {System.out.println("No element in the queue");return -1;} // Of ifint resultValue = header.next.data;header.next = header.next.next;// The queue becomes empty.if (header.next == null) {tail = header;} // Of ifreturn resultValue;}// Of dequeue

确定该队列不空后，就可以进行出队操作了。早在day13链表中，我们就已经知道头结点header的data域是无效的，没办法执行删除操作，同理这里的头指针header也是如此，所以出队时我们需要跳过头指针，从头指针后面第一个结点开始。显然，header.next就是指的头指针后面第一个结点，而header.next.data就是指头指针后面第一个结点的data域，也就是第一个有效数据（即需要删除的第一个数据），所以我们将其赋给resultValue；然后再通过header.next = header.next.next;实现删除操作。

这里有一个地方需要特别注意，当队列中只有一个有效结点时，头指针header和尾指针tail的指向如图所示：

这个时候再执行header.next = header.next.next;毫无疑问就会将该有效结点和尾指针一同删掉，所以我们需要重新定义尾指针。具体方法就是，当header.next = null即队列为空时，重新定义尾指针tail = header，最后不要忘记返回所删掉的数据。

5.数据测试

接下来进行数据测试：

• 创建LinkedQueue类的一个对象tempQueue，并调用toString()方法进行遍历（此时肯定为空）
• 进行入队操作，利用for循环向空队列中插入5个队列元素，并输出
• 出队一次，并输出
• 再循环执行出队操作5次，并输出
• 最后再循环入队3次，输出

    /************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {LinkedQueue tempQueue = new LinkedQueue();System.out.println("Initialized, the list is: " + tempQueue.toString());for (int i = 0; i < 5; i++) {tempQueue.enqueue(i + 1);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());tempQueue.dequeue();System.out.println("Dequeue, the queue is: " + tempQueue.toString());int tempValue;for (int i = 0; i < 5; i++) {tempValue = tempQueue.dequeue();System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 3; i++) {tempQueue.enqueue(i + 10);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());}// Of main

6.完整的程序代码

package datastructure;/*** Linked queue.* * @author Xin Lin [e-mail].*/
public class LinkedQueue {/*** An inner class.*/class Node {/*** The data.*/int data;/*** The reference to the next node.*/Node next;/********************* * The constructor.* * @param paraValue The data.******************* */public Node(int paraValue) {data = paraValue;next = null;}// Of the constructor}// Of class Node/*** The header of the queue.*/Node header;/*** The tail of the queue.*/Node tail;/************************ Construct an empty sequential list.**********************/public LinkedQueue() {header = new Node(-1);// header.next = null;tail = header;}// Of the first constructor/************************ Enqueue.* * @param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {Node tempNode = new Node(paraValue);tail.next = tempNode;tail = tempNode;}// Of enqueue/************************ Dequeue.* * @return The value at the header.**********************/public int dequeue() {if (header == tail) {System.out.println("No element in the queue");return -1;} // Of ifint resultValue = header.next.data;header.next = header.next.next;// The queue becomes empty.if (header.next == null) {tail = header;} // Of ifreturn resultValue;}// Of dequeue/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";if (header.next == null) {return "empty";} // Of ifNode tempNode = header.next;while (tempNode != null) {resultString += tempNode.data + ", ";tempNode = tempNode.next;} // Of whilereturn resultString;}// Of toString/************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {LinkedQueue tempQueue = new LinkedQueue();System.out.println("Initialized, the list is: " + tempQueue.toString());for (int i = 0; i < 5; i++) {tempQueue.enqueue(i + 1);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());tempQueue.dequeue();System.out.println("Dequeue, the queue is: " + tempQueue.toString());int tempValue;for (int i = 0; i < 5; i++) {tempValue = tempQueue.dequeue();System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 3; i++) {tempQueue.enqueue(i + 10);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());}// Of main
}// Of class LinkedQueue

运行结果

总结

队列是一个非常基本非常重要的数据结构，因其先进先出的特性，使得它在管理和调度顺序性任务时非常有效，在很多实际问题中，合理利用队列可以提升效率、保证数据处理的顺序性和稳定性；同时，队列还可以用来实现很多算法，比如广度优先搜索算法、消息传递等等。

队列和我们之前学过的栈都是常用的两种数据结构，也均为受限线性表，只不过前者为先进先出，适用于按顺序处理的场景，后者为先进后出，适合需要逆序处理的场景。