链表队列的结构

上一节我们介绍了队列的顺序存储结构，也就是通过数组实现队列。这一节我们介绍队列的链式存储，也就是通过单链表来实现的队列，说的简单一点，链式存储的队列就是受限制的单链表。我们限定只能在单链表的头部删除，尾部增加，这样的单链表就是一个队列。

链队列的定义

我们在程序中声明一个LinkedQueue类表示链队列，队列里面维护了链表头front和链表尾rear。

internal class LinkedQueue
{
    Node front;//队头
    Node rear;//队尾
}

算法1：入队

入队相当于在尾部插入一个新的节点，需要执行两步操作：last.Next=newNode;last=newNode；

public void EnQueue(int data)
{
    Node newNode = new Node(data);
    if (front == null)
    {
        front = newNode;
        rear = newNode;
    }
    else
    {
        rear.Next = newNode;
        rear = newNode;
    }
}

算法2：出队

出队相当于删除链表的第一个节点，执行一步操作:front=front.Next；

public Node Dequeue()
{
    if (IsEmpty())
    {
        throw new Exception("队列为空！");
    }
    Node res = front;
    front = front.Next;
    return res;
}

算法3：查看队头元素

直接返回头节点front即可。

public Node Peek()
{
    return front;
}

算法4：队列是否为空

注意这里不能使用front==rear判断队列为空，因为当队列中只有一个节点的时候front和rear指向同一个节点。
public bool IsEmpty() { return front == null; }

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/08LinkedQueue.cs