Java链式队列（队列的链式存储）用法详解

为了避免顺序队列在进行插入和删除操作时大量移动元素，造成效率低下，我们可以采用链式存储结构表示队列。采用链式存储结构的队列被称为链式队列或链队列。

一个链式队列通常用链表实现。同时，使用两个指针分别指向链表中存放的第一个元素的位置和最后一个元素的位置：

• 指向第一个元素的位置的指针被称为队头指针 front；
• 指向最后一个元素的指针被称为队尾指针 rear。

链式队列的表示如下图所示：


有时，为了操作方便，我们在链式队列的第一个结点之前添加一个头结点，并让队头指针指向头结点。其中，头结点的数据域可以存放队列的元素个数信息，指针域指向链式队列的第一个结点。带头结点的链式队列如下图所示。


在带头结点的链式队列中，当队列为空时，队头指针 front 和队尾指针 rear 都指向头结点，如下图所示。


在链式队列中，最基本的操作是插入和删除操作。链式队列的插入和删除操作只需要移动队头指针和队尾指针，下图表示在队列中插入元素 a 的情况：


下图表示在队列中插入元素 b、c 的情况：


下图表示元素 a 出队的情况：


链式队列的结点类型描述如下：

class QueueNode {
    char data;
    QueueNode next;
    QueueNode(char data) {
        this.data = data;
        this.next = null;
    }
}

对于带头结点的链式队列，初始时需要生成一个结点：

QueueNode QNode = new QueueNode('0');

然后令 front 和 rear 分别指向该结点，即：

• front = QNode;
• rear = QNode;

链式循环队列

链式队列也可以构成循环队列，如下图所示：


在这种链式循环队列中，可以只设置队尾指针，在这种情况下，队列 LQ 为空的判断条件为 LQ.rear.next==LQ.rear，链式循环队列为空时的情况如图 8 所示。

链式队列的实现

1) 队列的初始化

public class LinkQueue {
    QueueNode front, rear;
    // 初始化队列
    LinkQueue() {
        QueueNode QNode = new QueueNode('0');
        front = QNode;
        rear = QNode;
    }
}

2) 判断队列是否为空

public boolean QueueEmpty()
//判断链式队列是否为空，若队列为空，则返回 true，否则返回 false
{
    if (front == rear)  //若链式队列为空
        return true;    //则返回 true
    else
        return false;   //否则返回 false
}

3) 入队操作

public void EnQueue(char e)
//将元素 e 入队
{
    QueueNode pNode = new QueueNode(e);  //生成一个新结点，将元素值赋给结点的数据域
    rear.next = pNode;  //将原队列的队尾结点的指针指向新结点
    rear = pNode;  //将队尾指针指向新结点
}

4) 出队操作

public char DeQueue() throws Exception
//将链式队列中的队头元素出队，返回该元素，若队列为空，则抛出异常
{
    if (QueueEmpty())  //在出队前，判断链式队列是否为空
    {
        throw new Exception("队列为空，不能出队操作");
    }
    else
    {
        QueueNode pNode = front.next;  //使 pNode 指向队头元素
        front.next = pNode.next;  //使头结点的 next 指向 pNode 的下一个结点
        if (pNode == rear)  //若要删除的是队尾结点，则使队尾指针指向队头
            rear = front;
        return pNode.data;  //返回出队元素
    }
}

5) 取队头元素

public int getHead()
//取链式队列中的队头元素
{
    if (!QueueEmpty())  //若链式队列不为空
        return front.next.data;  //则返回队头元素
}