链式队列的基本操作C语言详解-蒲公英云

链式队列的基本操作C语言详解

链式队列有带头结点，和不带头结点的，我这里是带头结点的。
逻辑结构如图

编译环境vc6.0,代码如下：

/* 首元结点是指链表中存储线性表中第一个数据元素的结点。 初始化：队头指针和队尾指针都指向头结点（不是首元结点） 队满状态：只要还有内存，理论上不会满 进队操作：插入到链尾，尾指针指向新的尾结点 出头操作：删除首元结点（不是头结点），头指针指向新首元结点 */
#include <stdio.h>
#include <stdlib.h>
//结点结构
typedef struct QNode
{ 
    int data;
    struct QNode* next;
}QNode,*Queueptr;
//链表结构
typedef struct
{ 
    Queueptr front, rear;    //对头，队尾指针
}LinkQueue;
//************************初始化**************************
int InitLinkQueue(LinkQueue* Q)
{ 
    Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));             //建立头结点
    if (!Q->rear || !Q->front)
    { 
        return 0;
        printf("动态分配内存失败\n");
    }
    Q->front->next = NULL;                                        //初始化为空
    return 1;
}
//************************判断是否非空**************************
int IsEmpty(LinkQueue Q)
{ 
    if (Q.front == Q.rear)                                    //头尾指针同时指向头结点为空
        return 1;
    else return 0;
}
//************************入队**************************
int EnQueue(LinkQueue* Q, int e)
{ 
    Queueptr s = (Queueptr)malloc(sizeof(QNode));         //动态申请内存
    if (s == NULL)
        return 0;
    s->data = e;
    s->next = NULL;                                    //s插入到链尾巴，所有next指针指向空
    Q->rear->next = s;                                    //插入
    Q->rear = s;                                        //尾指针指向新的尾结点
    return 1;
}
//************************出队**************************
int DeQueue(LinkQueue* Q, int* e)
{ 
    Queueptr p;
    if (Q->front == Q->rear)                        //队空
        return 0;
    p = Q->front->next;                           //将欲删除的结点暂存给p
    *e = p->data;                                        //获取元素值
    Q->front->next = p->next;                        //删除Q->front->next, Q->front时头结点，Q->front->next 时首元结点
    if (Q->rear == p)                              //若删除后只剩下头结点，将尾指针指向头结点
        Q->rear = Q->front;
    free(p);
    return 1;
}
//************************遍历输出**************************
int LinkQueueTraverse(LinkQueue Q)
{ 
    Queueptr p;                   //结点指针
    if (IsEmpty(Q))
    { 
        printf("链表为空\n");
        return 0;
    }
    p = Q.front->next;              //p指向首元结点
    while (p)
    { 
        printf("%-5d", p->data);
        p = p->next;
    }
    return 1;
}
int main()
{ 
    int i, e, n;                        //e入队元素，n入队元素个数
    LinkQueue Q;
    InitLinkQueue(&Q);                            //初始化
    printf("初始化成功\n");
    printf("请输入,入队元素个数\n");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    { 
        printf("请输入第%d个元素值", i + 1);
        scanf("%d", &e);
        if (EnQueue(&Q, e))
            printf("入队成功\n");
        else printf("入队失败\n");
    }
    if (DeQueue(&Q, &e))
        printf("\n元素%d出队\n", e);
    else printf("出队失败\n");
    printf("遍历输出\n");
    LinkQueueTraverse(Q);
    return 0;
}