队列链式存储结构

队列的链式存储结构其实就是线性表的单链表,只不过它只能尾进头出而已,为了方便,将队列头指针指向队列的头结点,队尾指针指向终端结点

空队列时,front和rear都指向头结点,此时已经有一个结点了,所以有一点要注意的就是在出队的时候,都是讲头结点的后继结点出队,这一点刚在写的时候一直出错

链式队列数据结构:

typedef int QElemType;

typedef struct QNode {

    QElemType data;

    struct QNode *next;

}QNode;

typedef struct {

    QNode *front;

    QNode *rear;

}LinkQueue;

在入队的时候,没啥,但是出队的时候,由于初始化的时候队头和队尾指针都指向了头结点,出队的结点为头结点的后继结点,还有假如整个队列就只剩下一个头结点了,此时已经为空了,就不能再出队了,必须做个判断

#include <stdio.h>
#include <malloc.h>

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

typedef struct {
    QNode *front;
    QNode *rear;
}LinkQueue;

int PushNode(LinkQueue *q, int num){
    QNode *n;
    n = (QNode *)malloc(sizeof(QNode));
    n->next = NULL;
    n->data = num;

    q->rear->next = n;
    q->rear = n;

    return 0;
}

int InitLinkQueue(LinkQueue *q){
    QNode *n;
    n = (QNode *)malloc(sizeof(QNode));
    n->next = NULL;

    q->front = n;
    q->rear = n;
    return 0;
}

int PopNode(LinkQueue *q){
    if (q->rear == q->front)
        return 0;
    else if (q->front->next == q->rear)
        q->rear = q->front;
    QNode *n;
    n = q->front->next;
    q->front->next = q->front->next->next;
    free(n);
    return 0;
}

int main(){
    LinkQueue *q;
    q = (LinkQueue *)malloc(sizeof(LinkQueue));
    InitLinkQueue(q);

    PushNode(q, 0);
    PushNode(q, 1);
    PushNode(q, 2);
    PushNode(q, 3);
    PushNode(q, 4);
    PushNode(q, 5);

    PopNode(q);
    PopNode(q);
    PopNode(q);
    PopNode(q);

    while (q->front->next){
        printf(“%d\n”, q->front->next->data);
        q->front = q->front->next;
    }
    return 0;
}

发表评论