链式队列及其实现

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

typedef int dataType;

// 3.7 链式队列
typedef struct linkQueueNode
{
    dataType data;
    struct linkQueueNode *next;
}node,*linkQueue;

// 链式队列头指针和尾指针
typedef struct
{
    linkQueue front,rear;
}queue;

// 1.初始化链式队列
void init(queue *qu)
{
    qu->front = qu->rear =  NULL;
}

// 2.判断队列是否为空
int empty(queue qu)
{
    return !qu.front;
}

// 3.读队首元素的值
dataType read(queue qu)
{
    if(empty(qu))
    {
        printf("队列为空！\n");
        exit(1);
    }
    return qu.front->data;
}

// 4.输出队列元素的值
void display(queue qu)
{
    node *p = qu.front;
    if(!p)
    {
        printf("队列为空！\n");
        return;
    }
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 5.入队
void insert(queue *qu, dataType x)
{
    node *q;
    q = (node*) malloc(sizeof(node));
    q->data = x;
    q->next = NULL;
    if(empty(*qu)) // 队列为空时
        qu->front = q;
    else
        qu->rear->next = q;
    qu->rear = q; // 更新尾指针
}

// 6.出队
void del(queue *qu)
{
    node *p = qu->front;
    if(p == qu->rear) // 只有一个结点或队列空
    {
        if(!p)
        {
            printf("队列为空，无法出队！\n");
            return;
        }
        qu->front = qu->rear; // 更新头指针
        free(p);
        return;
    } // 队列非空时更新队头指针并释放结点空间
    qu->front = p->next;
    free(p);
}

int main()
{
    queue qu; // 定义一个指向队列的头指针和尾指针
    init(&qu); // 初始化队列
    display(qu); // 输出队列元素
    printf("入队！\n");
    for (int i = 1; i <= 5; i++)
        insert(&qu,i); // 入队
    display(qu);
    printf("队首元素为%d\n",read(qu));
    printf("出队！\n");
    del(&qu);
    display(qu);
    return 0;
}