【C语言数据结构】队列-链式存储(链队列)

川长思鸟来 2024-02-27 06:20 9阅读 0赞

--------------------

#### 队列-链式存储 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //定义元素数据类型
    #define ElemType int
    
    //定义链队列的数据结构体
    typedef struct LinkNode {
        
        //保存数据元素
        ElemType data;
    
        //指向下一个结点(这个要在front和rear的基础上来用)
        struct LinkNode *next;
    } LinkNode;
    
    //定义队首队尾指针结构体(这个才是用于进行各种操作的结构体)
    typedef struct {
        
        //定义队首队尾指针(这下真的是指针了)
        LinkNode *front, *rear;
    } *LinkQueue;
    
    //初始化队列
    void InitQueue(LinkQueue *queue) {
        
        //为整个队列指针先分配一个内存空间
        (*queue) = (LinkQueue)malloc(sizeof(LinkNode));
        
        //将队首队尾指针都置空，表明现在整个链队列还为空，没有数据
        (*queue)->front = NULL;
        (*queue)->rear = NULL;
    }
    
    //判断队列是否为空
    bool QueueEmpty(LinkQueue queue) {
        
        //这里只需要看front指针是否为空就行了，为什么呢？
        //因为如果添加了一个元素，那么front和rear都需要指向那个元素。如果再加一个元素，那么front指针不动，rear指针指向下一个结构体
        //如果要删除一个元素，那么front指针指向下一个结构体，释放上一个结构体的内存空间。
        //因此可以知道，如果队列为空，那么front指针一定为空
        return queue->front == NULL;
    }
    
    //入队操作
    bool EnQueue(LinkQueue *queue, ElemType e) {
        
        //先建立一个新的结构体结点
        LinkNode *newNode = (LinkNode *) malloc(sizeof(LinkNode));
    
        if (newNode == NULL) {
        
            // 内存分配失败，返回错误
            return false;
        }
    
        //将元素值赋给newNode里
        newNode->data = e;
        //不要忘了把新节点的next置空，否则会出现野指针
        newNode->next = NULL;
    
        //如果队列现在没有元素，那么front和rear都指向这个结构体
        if (QueueEmpty(*queue)) {
        
            (*queue)->front = newNode;
            (*queue)->rear = newNode;
        }
            //否则当前rear的下一个结点就是这个新结点，并将rear移动到新节点上
        else {
        
            (*queue)->rear->next = newNode;
            (*queue)->rear = newNode;
        }
    }
    
    //出队操作
    bool DeQueue(LinkQueue *queue, ElemType *e) {
        
        //如果队列为空，就不用出队了
        if (QueueEmpty(*queue))
            return false;
    
        //先把当前front的元素赋值给e，然后将front后移
        *e = (*queue)->front->data;
        (*queue)->front = (*queue)->front->next;
    
        return true;
    }
    
    //读取队头元素
    bool GetHead(LinkQueue queue, ElemType *e) {
        
        //如果队列为空,读取失败
        if (QueueEmpty(queue))
            return false;
    
        //把当前front的元素赋值给e
        *e = (*queue).front->data;
    
        return true;
    }
    
    int main(){
        
        //定义队列
        LinkQueue queue;
        ElemType Elem;
    
        //初始化队列
        InitQueue(&queue);
    
        //入队元素
        EnQueue(&queue,1);
        EnQueue(&queue,2);
        EnQueue(&queue,3);
        EnQueue(&queue,4);
    
        //读取当前队头元素
        GetHead(queue,&Elem);
        printf("当前队头元素为:%d\n",Elem);
    
        //依次出队元素，并打印出队的元素
        DeQueue(&queue,&Elem);
        printf("出队的元素为:%d\n",Elem);
        DeQueue(&queue,&Elem);
        printf("出队的元素为:%d\n",Elem);
        DeQueue(&queue,&Elem);
        printf("出队的元素为:%d\n",Elem);
        DeQueue(&queue,&Elem);
        printf("出队的元素为:%d\n",Elem);
    
        return 0;
    }