数据结构——队列的链式实现（C语言）-蒲公英云

数据结构——队列的链式实现（C语言）

队列是一种先进先出的线性表，但队列顺序存储的时候，操作不方便，为了操作简单，队列采用链式存储结构。队列入队时只能在队尾操作，出队时在队首操作，头结点的指针域有头指针(front)和尾指针(rear)，头结点只存放指针域，不存放数据项，但头指针和尾指针指向头指针时，队列为空。

以下是C语言源程序：

函数声明：

#ifndef Queue_H
#define Queue_H
typedef int Item;
typedef struct node *PNode;
typedef struct node
{
    Item data;
    PNode next;
}Node;
typedef struct queue *PQueue;
typedef struct queue
{
    PNode front;
    PNode rear;
    Item size;
}Queue;
/***创建空队列***/
PQueue Creat_Queue();
/***判断队列是否为空***/
int Is_Empty(PQueue);
PQueue CreateQueue(PQueue); //创建队列  
/***数据项入队，在队尾入队***/
PQueue Add_Queue(PQueue,Item);
/***计算队列大小***/
int Size_Queue(PQueue);
/***数据项出队，在队首出队***/
Item Delete_Queue(PQueue);
/***清空队列***/
void Clear_Queue(PQueue);
/***遍历队列***/
void Traverse_Queue(PQueue);
#endif

函数定义：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include"Queue.h"
/***创建空队列***/
PQueue Creat_Queue()
{
    PQueue P=(PQueue)malloc(sizeof(Queue));
    P->rear=P->front=(PNode)malloc(sizeof(Node));
    if(NULL==P || NULL==P->front)
    {
        printf("The queue is failed.\n");
        exit(1);
    }
    //P->front=P->rear;
    P->front->next=NULL;
    P->size=0;
    return P;
}
/***判断队列是否为空***/
int Is_Empty(PQueue P)
{
    if(P->front==P->rear)
        return 1;
    else
        return 0;
}
PQueue CreateQueue(PQueue P) //创建队列  
{  
    P=Creat_Queue();  
    printf("Enter the data:");  
    int k;  
    while((scanf("%d",&k)) == 1)  
    {
        Add_Queue(P,k);
        printf("Enter the next data:");  
    }
    return P;
}
/***数据项入队,在队尾入队***/
PQueue Add_Queue(PQueue P,Item data)
{
    PNode temp=(PNode)malloc(sizeof(Node));
    if(NULL==temp)
    {
        printf("The temp is failed.\n");
        exit(1);
    }
    temp->data=data;
    temp->next=NULL;
    if(Is_Empty(P))
        P->front->next=temp;
    else
        P->rear->next=temp;
    P->rear=temp;
    P->size++;
    printf("Add the data of %d to queue is success: %d\n ",data,data);
    return P;
}
/***计算队列大小***/
int Size_Queue(PQueue P)
{
    return P->size;
}
/***数据项出队，在队首出队***/
Item Delete_Queue(PQueue P)
{
    Item data;
    if(Is_Empty(P))
        return NULL;
    PNode temp=P->front->next;
    data=temp->data;
    P->front->next=temp->next;
    if(0==P->size)
        P->rear=P->front;
    P->size--;
    free(temp);
    return data;
}
/***清空队列***/
void Clear_Queue(PQueue P)
{  
    PNode temp = P->front->next;  
    while(temp)  
    {  
        PNode tp = temp;  
        temp = temp->next;  
        free(tp);  
    }  
    temp = P->front;  
    P->front = P->rear = NULL;  
    free(temp);  
}  
/***遍历队列***/
void Traverse_Queue(PQueue P)
{  
    if(Is_Empty(P))  
        printf("there is no data in the queue!\n");  
    else  
    {     
        PNode pCurrent = P->front->next;   
        printf("Now datas int the queue are:\n");  
        while(pCurrent)  
        {  
            printf("%d ",pCurrent->data);  
            pCurrent = pCurrent->next;  
        }  
        printf("\n");  
    }  
    return;  
}

测试程序：

#include<stdio.h>
#include<stdlib.h>
#include "Queue.h"
#define num 5
int main()
{
    /***创建空队列***/
    PQueue PQ;
    int size=0;
    int data;
    PQ=Creat_Queue();
    printf("The queue is created.\n");
    /***判断队列是否为空***/
    if(Is_Empty(PQ))
        printf("The queue is empty.\n");
    PQ=CreateQueue(PQ); //创建队列
    /***遍历队列***/
    Traverse_Queue(PQ);
    /***数据项入队，在队尾入队***/
    PQ=Add_Queue(PQ,num);
    /***遍历队列***/
    Traverse_Queue(PQ);
    /***计算队列大小***/
    size=Size_Queue(PQ);
    printf("The size of queue are: %d\n",size);
    /***数据项出队，在队首出队***/
    data=Delete_Queue(PQ);
    printf("The deleted data is: %d\n",data);
    /***遍历队列***/
    Traverse_Queue(PQ);
    /***清空队列***/
    Clear_Queue(PQ);
    if(Is_Empty(PQ))
        printf("The queue is empty.\n");
    /***遍历队列***/
    Traverse_Queue(PQ);
    return 0;
}