数据结构：链式队列

? ? ? ?队列是限制在两端操作进行插入操作与删除操作的线性表，允许进行插入操作的一端称为"队尾"，允许进行删除操作的一端称为“队头”。当线性表中没有元素时，称为“空队”。队列的特点是先进先出。

队列两种规定：

1、front指向队头元素的前一个位置，rear指向队尾元素所在位置；以下代码采用第一种规定。

2、front指向队头元素所在位置，rear指向队尾元素的下一个位置；? ? ? ? ? ?

?queue.h

/*===============================================
*   文件名称：queue.h
*   创 建 者：cxy     
*   创建日期：2024年01月20日
*   描    述：
================================================*/
#ifndef _QUEUE_H
#define _QUEUE_H

#include <stdio.h>
#include <stdlib.h>

typedef struct node{    //节点
    int data;
    struct node *next;
}Node,*Pnode;

//规定1
typedef struct queue{    //队列指针
    Pnode front;  //头节点指针,指向队头元素的前一个位置
    Pnode rear;   //队尾指针，指向队尾元素所在位置
}Queue,*Pqueue;

int init(Pqueue *P);
int empty(Pqueue p);
int insert_queue(Pqueue p,int data);
int delete_queue(Pqueue p,int *data);
int sum(Pqueue p);
int clear_queue(Pqueue p);

#endif

queue.c

/*===============================================
*   文件名称：queue.c
*   创 建 者：cxy     
*   创建日期：2024年01月20日
*   描    述：
================================================*/
#include "queue.h"

int init(Pqueue *P)
{
    *P = malloc(sizeof(Queue));  //队列指针
    if(NULL == *P)
    {
        perror("init err:*P");
        return -1;
    }
    (*P)->front = malloc(sizeof(Node));  //头节点
    if(NULL == (*P)->front)
    {
        perror("init err:(*P)->front");
        return -1;
    }
    (*P)->rear = (*P)->front;   //空队
    (*P)->front->next = NULL;

    return 0;
}

int empty(Pqueue p)
{
    if(NULL == p)
    {
        perror("empty err:p");
        return -1;
    }
    if(p->front->next == NULL)
        return 1;
    else 
        return 0;
}

int insert_queue(Pqueue p,int data)
{
    if(NULL == p)
    {
        perror("insert err:p");
        return -1;
    }
    Pnode new = malloc(sizeof(new));
    if(NULL == new)
    {
        perror("insert err:new");
        return -1;
    }
    new->data = data;
    new->next = NULL;   //入队：队尾
    p->rear->next = new;
    p->rear = new;      //更新队尾
   
    return 0;
}

int delete_queue(Pqueue p,int *data)
{
    if(NULL == p)
    {
        perror("delete err:p");
        return -1;
    }
    if(empty(p))
    {
        perror("delete err:empty");
        return -1;
    }

    Pnode q = p->front->next;
    *data = q->data;
    p->front->next = q->next;   //更新队头元素为q->next
    free(q);

    if(p->front->next == NULL)  //空队
        p->rear = p->front;
    
    return 0;
}

int sum(Pqueue p)
{
    if(NULL == p)
    {
        perror("sum err:p");
        return -1;
    }
    Pnode q = p->front->next;
    int sum = 1;
    while(q->next)
    {
        q = q->next;
        sum++;
    }

    return sum;
}

int clear_queue(Pqueue p)
{
    if(NULL == p)
    {
        perror("clear err:p");
        return -1;
    }
    Pnode q = NULL;
    while(p->front->next)
    {
        q = p->front->next;
        p->front->next = q->next;
        free(q);
    }

    return 0;
}

main.c

/*===============================================
*   文件名称：main.c
*   创 建 者：cxy     
*   创建日期：2024年01月20日
*   描    述：
================================================*/
#include "queue.h"

int main(int argc, char *argv[])
{ 
    Pqueue p;
    init(&p);

    int data;
    printf("----------empty,1为空----------\n");
    data = empty(p);
    printf("%d\n",data);

    printf("----------insert_queue----------\n");
    for(int i = 0;i < 5;i++)
    {
        printf("请输入入队数据:");
        scanf("%d",&data);
        insert_queue(p,data);
    }

    printf("----------empty,1为空----------\n");
    data = empty(p);
    printf("%d\n",data);
    
    printf("----------sum----------\n");
    data = sum(p);
    printf("队列中共有:%d个数据\n",data);
    
    printf("----------delete_queue----------\n");
    for(int i = 0;i < 3;i++)
    {
        printf("出队数据为:");
        delete_queue(p,&data);
        printf("%d\n",data);
    }
    printf("----------empty,1为空----------\n");
    data = empty(p);
    printf("%d\n",data);

    
    printf("----------clear_queue----------\n");
    clear_queue(p);
    printf("----------empty,1为空----------\n");
    data = empty(p);
    printf("%d\n",data);

    return 0;
} 

结果