队列的链式存储结构-链式队列

链式队列的基本操作

（1）队列初始化
（2）销毁队列
（3）判断队列是否为空
（4）获取队头元素
（5）入队
（6）出队

定义链式队列的结构

typedef struct QNode{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front;  //头指针 
    QueuePtr rear;   //尾指针 
}LinkQueue;

链式队列的初始化

/*链队的初始化*/ 
int InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front){
        printf("初始化失败\n");
        return -1;
    }
    Q.front->next = NULL;
    printf("链队初始化成功！\n"); 
    return 0;
}

销毁链式队列

/*销毁链队列*/ 
int DestoryQueue (LinkQueue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    printf("销毁队列成功！\n");
    return 0;
}

判断队列是否为空

/*判断队列是否为空*/ 
int QueueEmpty(LinkQueue Q){
    if(Q.front == Q.rear) {
        printf("队列为空！\n");
        return 0;
    }
    printf("队列不为空！\n");
    return -1;
}

获取队头元素

/*获取队头元素*/ 
int GetHead(LinkQueue Q){
    if(Q.front == Q.rear){
        printf("获取失败，队列为空\n");
        return -1;
    }
    return Q.front->next->data;
}

链式队列入队

/*链式队列入队*/
int InQueue(LinkQueue &Q,int e){
    QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode));
    if(!newNode) return -1;
    newNode->data = e;
    newNode->next = NULL;
    Q.rear->next = newNode;
    Q.rear = newNode;
    printf("元素【%d】入队成功！\n",e);
    return 0; 
}

链式队列出队

/*链式队列出队*/
int EnQueue(LinkQueue &Q,int e){
    if(Q.front==Q.rear){
        printf("队列为空，不能出队\n");
        return -1;
    }
    QueuePtr p = Q.front->next;
    e = Q.front->next->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;
    printf("元素【%d】出队成功！\n",e);
    free(p);
    return 0;
}

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct QNode{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front;  //头指针 
    QueuePtr rear;   //尾指针 
}LinkQueue;
/*链队的初始化*/ 
int InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front){
        printf("初始化失败\n");
        return -1;
    }
    Q.front->next = NULL;
    printf("链队初始化成功！\n"); 
    return 0;
} 
/*销毁链队列*/ 
int DestoryQueue (LinkQueue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    printf("销毁队列成功！\n");
    return 0;
}
/*判断队列是否为空*/ 
int QueueEmpty(LinkQueue Q){
    if(Q.front == Q.rear) {
        printf("队列为空！\n");
        return 0;
    }
    printf("队列不为空！\n");
    return -1;
} 
/*获取队头元素*/ 
int GetHead(LinkQueue Q){
    if(Q.front == Q.rear){
        printf("获取失败，队列为空\n");
        return -1;
    }
    return Q.front->next->data;
} 
/*链式队列入队*/
int InQueue(LinkQueue &Q,int e){
    QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode));
    if(!newNode) return -1;
    newNode->data = e;
    newNode->next = NULL;
    Q.rear->next = newNode;
    Q.rear = newNode; //出队元素为最后一个元
    printf("元素【%d】入队成功！\n",e);
    return 0; 
} 
/*链式队列出队*/
int EnQueue(LinkQueue &Q,int e){
    if(Q.front==Q.rear){
        printf("队列为空，不能出队\n");
        return -1;
    }
    QueuePtr p = Q.front->next;
    e = Q.front->next->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;  //出队元素为最后一个元素时将尾指针指向头指针，队列为空
    printf("元素【%d】出队成功！\n",e);
    free(p);
    return 0;
}
int main(){
    LinkQueue Q;
    int e;
    //链队初始化
    InitQueue(Q);
    //链队判空 
    QueueEmpty(Q);
    //链队入队 
    InQueue(Q,1);
    InQueue(Q,2);
    InQueue(Q,3);
    InQueue(Q,4);
    //链队判空 
    QueueEmpty(Q);
    //链队出队
    EnQueue(Q,e); 
    EnQueue(Q,e);
    //获取队头元素
    printf("队头元素为:%d\n",GetHead(Q)); 

}

运行结果