数据结构与算法——队列之链式队列

本节主要介绍下队列的链式存储方式，链式毫无疑问也是有队头front和队尾rear，队头front出队，队尾rear入队，也是先进先出的原则。
链式存储结构如下图

队列链式存储.png

1、定义
首先创建结点结构：数据域和指针域。然后是队列的结构：队头、队尾、队长（可有可无根据需求）

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

//结点结构
typedef struct SqNode{
    QElemType data;
    struct SqNode *next;
}SqNode,*node;
//队头、队尾
typedef struct{
    node front,rear;
    //队列的长度
    int length;
}SqQueue;

2、初始化
初始化队列，队头front指向队尾rear，next=NULL。

Status InitSqQueue(SqQueue *Q){
    //队头队尾指向同一个存储空间
    Q->front = Q->rear = (node)malloc(sizeof(SqNode));
    if (!Q->rear) {
        return ERROR;
    }
    Q->length = 0;
    //头结点的指针置空
    Q->front->next = NULL;
    return OK;
};

3.销毁队列
销毁链式队列，需要把之前指针指向空间给释放，不然容易造成野指针。

Status DestorySqQueue(SqQueue *Q){
    Q->length = 0;
    while (Q->front) {
        Q->rear = Q->front;
        node p = Q->front;
        Q->front = p->next;
        free(p);
    }
    return OK;
}

4.清空队列

Status ClearSqQueue(SqQueue *Q){
    node p,q;
    //记录头和尾的位置
   q =  p = Q->front;
    //1、先将队尾指向队头
    Q->rear = Q->front;
    //2、队头的指针为空
    Q->front->next = NULL;
    //3、销毁队列元素
    while (p) {
        q = p->next;
        p = q;
        free(q);
    }
    Q->length = 0;
    return OK;
}

5.对尾插入元素

Status InsertSqQueue(SqQueue *Q,int e){
//创建新的结点
    node temp = (node)malloc(sizeof(SqNode));
//结点数据域为e。
    temp->data = e;
//结点的next置为NULL
    temp->next = NULL;
//队列队尾的next=temp，
    Q->rear->next = temp;
//队尾后移
    Q->rear = temp;
//队长长队+1
    Q->length++;
    return OK;
}

6.删除队头元素,并返回删除队元素的值

Status DeleteSqQueue(SqQueue *Q,QElemType *e){
    //判断队列是否为空队列
    if (Q->rear == Q->front) {
        return ERROR;
    }
    node deleteNode;
//由于在创建的时候有一个空结点，入队的时候直接是把rear->next 为新的结点，所以获取队头获取的是front->next；
    deleteNode = Q->front->next;
    //取值
    *e = deleteNode->data;
//队头后移
    Q->front = deleteNode->next;
//释放结点
    free(deleteNode);
//长度--
    Q->length--;
    return OK;
}

7.获取队头元素

Status FrontSqQueue(SqQueue Q,QElemType *e){
    //判断队列是否为空队列
    if (Q.rear == Q.front) {
        return ERROR;
    }
    *e = Q.front->next->data;
    return OK;
}

9.获取队尾元素

Status RearSqQueue(SqQueue Q,QElemType *e){
    //判断队列是否为空队列
       if (Q.rear == Q.front) {
           return ERROR;
       }
       *e = Q.rear->data;
       return OK;
}

10.遍历队列(遍历不能改变队列哟！！！)

Status TraverseSqQueue(SqQueue Q){
    //判断队列是否为空队列
    if (Q.rear == Q.front) {
        return ERROR;
    }
    node p = Q.front->next;
    node q ;
    while (p) {
        q = p;
        printf("%d ",q->data);
        p = q->next;
    }
    printf("\n");
    return OK;
}

有什么错误的地方欢迎指出。