链队：队列的链式表示和实现
相应函数定义

InitQueue(&Q);                  构造空队列
DestroyQueue(&Q);               销毁队列
ClearQueue(&S);                 清空队列
QueueEmpty(S);                  判空.空-TRUE
QueueLength(Q);                 取队列长度
GetHead(Q, &e);                 取队头元素
EnQueue(&Q, e);                 入队列
DeQueue(&Q, &e);                出队列
QueueTraverse(Q, visit());      遍历

头文件、宏定义

#include<stdlib.h>      // 使用exit(0)时需要引用头文件
#define MAXSIZE 100
#define ElemType int
// 以下为使用Status的配套操作
#define Status int
#define OK 1
#define Error 1

定义结构体

#define ElemType int 
typedef struct QNode        // 当定义链式结构(需要定义指针时),记得需要再struct后面加类名
{
    ElemType data;
    struct QNode* next;     // 这个记得要写对,就算定义链式结构中next指针时记得加struct
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

链队初始化
step 1 ： 生成新节点作为头结点，队头和队尾指针都指向此结点。
step 2 : 头结点的指针域取为NULL

Status InitQueue(LinkQueue& Q)
{
    // 生成新节点作为头结点，对头和队尾指针指向该结点
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;   //头结点的指针与置空
    return OK;
}

判断链队是否为空

bool EmptyQueue(LinkQueue Q)
{
    return Q.front == Q.rear;
}

求链队的队头元素
记得判断队列是否非空

Status GetHeadQueue(LinkQueue Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;  // 判断队列是否非空
    e = Q.front->data;
    return OK;
}

链队入队
step 1：为入队元素分配结点空间，用指针p指向
step 2：将新结点数据域置为e，指针域置为空
step 3：将新结点插入到队尾
step 4：修改队尾指针为p

Status EnQueue(LinkQueue& Q, ElemType e)
{
    // 链队不需要判断是否队满
    QNode* p = new QNode;   // 为入队元素分配结点空间，用指针p指向
    p->data = e;            // 将新结点数据域置为e
    p->next = NULL;
    Q.rear->next = p;       // 将新结点插入到队尾
    Q.rear = p;             // 修改队尾指针
    return OK;
}

思考：链队**需要头结点**，因为当没有头结点时，我们需要判断是否为第一个结点，如果为第一个结点，那么就将`front`以及`rear`指针指向第一个结点，
链队出队
step 1：判断队列是否为空，若空着返回Error
step 2：临时保存队头元素的空间，已备释放
step 3：修改头结点的指针域，使其指向下一个结点
step 4：判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。
step 5：释放原始队头元素的空间

Status DeQueue(LinkQueue& Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;
    QNode* p = new QNode;
    p = Q.front->next;                  // p 指向首元结点
    e = Q.front->data;                  // e保存队头结点的数据域
    Q.front = Q.front->next;            // 修改头结点的指针域
    if (Q.rear == p) Q.rear = Q.front;  // 若删的是最后一个元素，则修改队尾指针指向头结点
    delete p;                           // 释放原队头元素的空间
    return OK;
}

思考：链队**需要头结点**，因为当没有头结点时，如果链队出完后为空，那么我需要将`front`和`rear`指针置空，又会多一步判断。
销毁链表
将rear指针当做第三方指针，用于记录front->next指针，然后删除前一个指针，直到front指针为空，那么就删除完了。

Status DestroyQueue(LinkQueue& Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}