链表实现队列

今天药忘吃喽~ 2022-05-10 08:03 206阅读 0赞

这次写的还算正规，稍微压缩了一下代码，但是不影响阅读

画个图帮助理解：

F->0->0->0<-R

第一个0不存数据

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    typedef int Elementype;//数据类型
    //节点结构
    typedef struct Node{
        Elementype Element;//数据域
        struct Node * Next;
    }NODE,*PNODE;
    
    //    定义队列结构体
    typedef struct QNode {
        PNODE Front;//队头
        PNODE Rear;//队尾
    } Queue, *PQueue;
    
    void init(PQueue queue)//初始化
    {//头尾指向同一内存空间//头结点，不存数据
        queue->Front = queue->Rear = (PNODE)malloc(sizeof(NODE));
        queue->Front->Next = NULL;//头结点指针为空
    }
    
    int isEmpty(PQueue queue)//判空·
    {
        if(queue->Front == queue->Rear)return 1;
        return 0;
    }
    
    void insert(PQueue queue,Elementype data)//入队
    {
        PNODE P = (PNODE)malloc(sizeof(NODE));//初始化
        P->Element = data;
        P->Next = NULL;
        queue->Rear->Next = P;//入队
        queue->Rear = P;
    }
    
    void delete(PQueue queue,int * val)//出队，用val返回值
    {
        if(isEmpty(queue))printf("队空");
        else
        {
            PNODE  P = queue->Front->Next;//前一元素
            *val = P->Element;//记录值
            queue->Front->Next = P->Next;//出队
            //注意一定要加上判断，手动模拟一下就明白了
            if(P==queue->Rear)queue->Rear = queue->Front;
            free(P);//注意释放
            P = NULL;
        }
    }
    
    void destroy(PQueue queue)//释放
    {
        //从头开始删
        while(queue->Front != NULL)//起临时指针作用，无需再用别的空间
        {
            queue->Rear = queue->Front->Next;
            free(queue->Front);
            queue->Front = queue->Rear;
        }
    }
    //测试
    int main(void)
    {
        int i;
        int e;
        Queue a;
        PQueue queue=&a;
        init(queue);
        for(i=0;i<10;i++)
            insert(queue,i);
        while(!isEmpty(queue))//遍历
        {
            delete(queue,&e);
            printf("%d ",e);
        }
        if(isEmpty(queue))printf("1\n");
        delete(queue,&e);
        destroy(queue);
    }