数据结构（9）队列之链队列

古城微笑少年丶 2023-06-16 08:26 10阅读 0赞

### 数据结构（9）队列之链队列 ###

*   *   *  前言
         *  链队列的初始化
         *  源代码
         *   *  LinkQueue.h
             *  LinkQueue.c
             *  Main.c

### 前言 ###

队列同栈一样，本质都是操作受限的线性表。与栈不同的是，队列只允许在一端进行插入操作，在另一端进行删除操作，允许插入的一端称为队尾，允许删除的一端称为队头。从线性表的角度来看，也就是说队列只支持头部删除和尾部插入操作。它的特性就是先进先出，同生活中的排队现象类似。

![img\_1][img_1]

### 链队列的初始化 ###

只要认识到队列的本质是线性表，那么队列的链式存储和线性表的链式存储都是一致的，都需要考虑头结点的问题。如果设置了头结点，那么在初始化链队列时就需要生成一个头结点并为它赋初值；如果不设头结点则直接将队列赋空即可。为了方便操作，此处是设了头结点的。

![img\_2][img_2]

其他操作同单链表基本一致，就不写了

### 源代码 ###

#### LinkQueue.h ####

#ifndef LinkQueue_h
    #define LinkQueue_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    #define ElemType int
    
    typedef struct QueueNode{ 
        ElemType data;
        struct QueueNode *next;
    }QueueNode;
    
    typedef struct LinkQueue{ 
        QueueNode *fount;
        QueueNode *tail;
    }LinkQueue;
    
    //初始化
    void InitQueue(LinkQueue *Q);
    
    //入队
    void EnQueue(LinkQueue *Q,ElemType x);
    //出队
    void DeQueue(LinkQueue *Q);
    //展示
    void ShowQueue(LinkQueue *Q);
    //获取队首元素
    void GetHead(LinkQueue *Q,ElemType *x);
    //获取队列长度
    void GetLength(LinkQueue *Q);
    //清除
    void ClearQueue(LinkQueue *Q);
    //摧毁
    void DestoryQueue(LinkQueue *Q);
    #endif /* LinkQueue_h */

#### LinkQueue.c ####

#include "LinkQueue.h"
    
    //初始化
    void InitQueue(LinkQueue *Q){ 
        //申请头结点的空间
        QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
        assert(s != NULL);
        
        //初始化值
        Q->fount = Q->tail = s;
        Q->tail->next = NULL;
    }
    //入队->实际上就是尾部插入
    void EnQueue(LinkQueue *Q,ElemType x){ 
        //申请新结点的空间并赋值
        QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
        assert(s != NULL);
        s->data = x;
        s->next = NULL;
        
        //添加到队列尾部
        Q->tail->next = s;
        //重新设置队尾指针
        Q->tail = s;
    }
    
    //出队->实际上就是头部删除
    void DeQueue(LinkQueue *Q){ 
        //取出首元结点
        QueueNode *s = Q->fount->next;
        //判断是否已空
        if (s != NULL) { 
            Q->fount->next = s->next;
            free(s);
        }
        
        //判断删除的是否是最后一个结点
        if (Q->fount->next == NULL) { 
            Q->tail = Q->fount;
            Q->tail->next = NULL;
        }
    }
    
    //展示
    void ShowQueue(LinkQueue *Q){ 
        QueueNode *s = Q->fount->next;
        
        while (s != NULL) { 
            printf("%4d",s->data);
            s = s->next;
        }
        printf("\n");
    }
    
    //获取队首元素
    void GetHead(LinkQueue *Q,ElemType *x){ 
        if (Q->fount == Q->tail) { 
            //队列为空，无法获取
            printf("队列已空\n");
            return;
        }
        
        QueueNode *s = Q->fount->next;
        *x = s->data;
    }
    
    //获取队列长度
    void GetLength(LinkQueue *Q){ 
        int length = 0;
        QueueNode *s = Q->fount->next;
        while (s != NULL) { 
            length ++;
            s = s->next;
        }
        printf("长度为:%d\n",length);
    }
    
    //清除
    void ClearQueue(LinkQueue *Q){ 
        QueueNode *s = Q->fount->next;
        while (s != NULL) { 
            Q->fount->next = s->next;
            free(s);
            s = Q->fount->next;
        }
        Q->tail = Q->fount;
        Q->tail->next = NULL;
    }
    //摧毁
    void DestoryQueue(LinkQueue *Q){ 
        ClearQueue(Q);
        free(Q->fount);
        Q->fount = Q->tail = NULL;
    }

#### Main.c ####

#include "LinkQueue.h"
    
    int main(int argc, const char * argv[]) { 
        
        LinkQueue Q;
        InitQueue(&Q);
        
        //入队
        for (int i = 0; i < 5; i ++) { 
            EnQueue(&Q, i);
        }
        
        //展示
        ShowQueue(&Q);
        //出队
        DeQueue(&Q);
        ShowQueue(&Q);
        //求长度
        GetLength(&Q);
        //清除
        ClearQueue(&Q);
        GetLength(&Q);
        return 0;
    }

[img_1]: https://img-blog.csdnimg.cn/20191125192012171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_2]: https://img-blog.csdnimg.cn/20191125192028851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70