链式存储队列

队列的链式存储结构，简单看来和线性表的单链表非常相似，只不过，链式存储的队列，只可以在队尾rear入队，队头front出队。

同样为了方便，在队列前添加头结点。

1、1 链式存储队列结构设计：

// 结点结构
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QListNode;
// 队列链表结构
typedef struct {
    QListNode front; // 队头
    QListNode rear;  // 队尾
}SqQueue;

1、2 初始化队列

将队列的front，rear都指向新建的头结点。

// 初始化
Status InitQueue(SqQueue *Q){    
    Q->front = Q->rear = (QListNode)malloc(sizeof(QListNode));
    if (!Q->front) {
        return ERROR;
    }
    Q->front->next = NULL;  // 头结点的指针域置空 此处Q->rear的next同样指向空
    return OK;
}

1、3 添加入队，只需要调整rear就可以，front始终指向头结点。

// 添加元素
Status EnterQueue(SqQueue *Q,QElemType e){

    if (!Q) {
        return ERROR;
    }

    QListNode temp = (QListNode)malloc(sizeof(QNode));
    if (!temp) {
        return ERROR;
    }
    temp->data = e;
    temp->next = NULL;  // 要将新结点的next指向空，以免脏数据

    Q->rear->next = temp;
    Q->rear = temp;     // 调整rear 指向最新的结点
    return OK;
}

1、4 删除出队

删除要注意两个条件：

• 删除前判断队列是否是空的
• 判断要删除的是不是最后一个元素

// 删除
Status DeleteQueue(SqQueue *Q,QElemType *e){
    if (!Q) {
        return ERROR;
    }
    if (Q->front == Q->rear) {  // 判断是否为空
        printf("队列已空\n");
        return ERROR;
    }

    QListNode temp = Q->front->next;
    *e = temp->data;
    Q->front->next = temp->next; // 要把头结点的next指向要删除结点的next

    if (Q->rear == temp) {   // 假如要删除的是最后一个，要把rear指向头结点
        Q->rear = Q->front;
    }

    free(temp);    
    return OK;
}

1、5 遍历所有元素

// 遍历
Status QueueTrave(SqQueue Q){

    QListNode temp = Q.front->next;
    while (temp) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");

    return OK;
}

1、6 队列长度

通过遍历每一个结点，计算遍历的次数，来获取队列的长度。

获取队列长度也可以在设计队列时，添加count，每次入列出列进行count加减

// 队列长度  
int QueueLength(SqQueue Q){
    if (Q.front != Q.rear) {
        QListNode temp = Q.front->next;
        int count = 0;
        while (temp) {
            count++;
            temp = temp->next;
        }
        return count;
    }
    return 0;
}

1、7 队列清空

1、 将rear重新指向头结点
2、 遍历所有的结点，free掉
3、 将front的next指向为null

// 清空
Status ClearQueue(SqQueue *Q){
    if (!Q) {
        return ERROR;
    }

    if (Q->front == Q->rear) { // 判断队列是否为空
        return ERROR;
    }
    Q->rear = Q->front;  

    QListNode temp = Q->front->next;
    while (temp) {
        QListNode p = temp->next;
        free(temp);
        temp = p;
    }

    Q->front->next = NULL;
    return OK;
}

1、8 销毁队列

// 销毁
Status DestoryQueue(SqQueue *Q){

    QListNode temp = Q->front;
    while (temp) {
        QListNode p = temp->next;
        free(temp);
        temp = p;
    }

    /*  销毁不用在意front rear ，所以也可以不用太多其它的参数，如下
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }*/

    return OK;
}

文章永久链接：https://tech.souyunku.com/31424