队列—链式结构

拼搏现实的明天。 2024-04-17 17:59 65阅读 0赞

1、定义

队列的链式存储结构，实质就是线性表的单链表，只是限定尾部进头部出的规则。

2、结构

如图所示  
1）队列非空时，将头指针（front）指向头结点，尾指针指（rear）向队列的最后一个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]  
2）队列为空时，头指针（front）和尾指针指（rear）都指向头结点。  
![在这里插入图片描述][20190829163940251.png]  
3、代码

queue.h

#ifndef Queue_H
    #define Queue_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    typedef int DataType;
    
    //节点的结构体定义
    typedef struct Node{ 
        DataType data;
        struct node *next;
    }Node;
    
    //头指针、尾指针的结构体定义
    typedef struct { 
        Node *front;
        Node *rear;
    }LinkQueue;
    
    int GetQueueLength(LinkQueue *Lqueue);                    //获取链队的长度
    Status DestroyQueue(LinkQueue *Lqueue);                   //销毁链队
    Status IfQueueIsEmpty(LinkQueue *Lqueue);                 //判断链队是否为空
    Status InitiateQueue(LinkQueue *Lqueue);                  //初始化链队
    Status EnterQueueData(LinkQueue *Lqueue, DataType elem);  //入队
    Status OutQueueData(LinkQueue *Lqueue, DataType *elem);   //出队
    Status GetQueueElement(LinkQueue *Lqueue, DataType *elem);//取队头元素
    
    #endif // MAINWINDOW_H

queue.c

#include "queue.h"
    
    //初始化链队
    Status InitiateQueue(LinkQueue *Lqueue)
    { 
        Node *head = (Node *)malloc(sizeof(Node));
        head->next = NULL;
    
        Lqueue->front = head;
        Lqueue->rear = head;
    
        return TRUE;
    }
    
    //判断链队是否为空
    Status IfQueueIsEmpty(LinkQueue *Lqueue)
    { 
        if (Lqueue->front == Lqueue->rear)
        { 
            printf("链队为空！\n");
            return FALSE;
        }
        else
            return TRUE;
    }
    
    //获取链队的长度
    int GetQueueLength(LinkQueue *Lqueue)
    { 
        int length = 0;
    
        Node *p = Lqueue->front;
        while (p->next != NULL)
        { 
            ++length;
            p = p->next;
        }
        return length;
    }
    
    //入队
    Status EnterQueueData(LinkQueue *Lqueue, DataType elem)
    { 
        Node *p = (Node *)malloc(sizeof(Node));
        p->data = elem;
        p->next = NULL;
    
        Lqueue->rear->next = p;
        Lqueue->rear = p;
        return TRUE;
    }
    
    //出队
    Status OutQueueData(LinkQueue *Lqueue, DataType *elem)
    { 
        if (Lqueue->front == Lqueue->rear) //链队为空的判断
        { 
            printf("链队已空！\n");
            return FALSE;
        }
    
        Node *p = NULL;
        p = Lqueue->front->next;
        *elem = p->data;
        Lqueue->front->next = p->next;
    
        if (Lqueue->rear == p)
            Lqueue->rear = Lqueue->front;
    
        free(p);
        return TRUE;
    }
    
    //取队头元素
    Status GetQueueElement(LinkQueue *Lqueue, DataType *elem)
    { 
        if (Lqueue->front == NULL)
        { 
            printf("链队已空无数据元素可取! \n");
            return FALSE;
        }
        else
        { 
            *elem = Lqueue->front->next->data;
            return TRUE;
        }
    }
    
    //销毁链队
    Status DestroyQueue(LinkQueue *Lqueue)
    { 
        Node *p = NULL;
    
        while (Lqueue->front != Lqueue->rear)
        { 
            p = Lqueue->front;
            Lqueue->front = p->next;
            free(p);
        }
    
        return TRUE;
    }

main.c

#include "queue.h"
    
    int main()
    { 
        LinkQueue Lqueue;
        int x = 0;
    
        InitiateQueue(&Lqueue);
    
        for(int i = 0; i < 10; i++)
        { 
            EnterQueueData(&Lqueue, i+1);
        }
    
        GetQueueElement(&Lqueue, &x);
        printf("当前队头元素为：%d\n", x);
    
        printf("依次出队列的元素序列如下：\n");
        while(IfQueueIsEmpty(&Lqueue))
        { 
            OutQueueData(&Lqueue, &x);
            printf("%d ", x);
        }
    
        DestroyQueue(&Lqueue);
        IfQueueIsEmpty(&Lqueue);
    
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b6f48e6cade3485faff4d444cac93626.png
[20190829163940251.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/987eb4b5732944b0ba5f426f574a9651.png