(20)王道数据结构-队列的链式实现

带头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front, *rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
bool DeQueue(LinkQueue &Q, int &x);
bool IsEmpty(LinkQueue Q);
int main(void) {
    LinkQueue Q;
    int x;
    InitQueue(Q);
    
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    
    
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    if (!IsEmpty(Q)) {
        printf("x=%d\n", x);
    }
    return 0;
}

//初始化队列
void InitQueue(LinkQueue &Q) {
    //初始时，队头和队尾指针指向头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

//判断队列是否为空
bool QueueEmpty(LinkQueue Q) {
    if (Q.rear == Q.front) {    //队空条件
        return true;
    } else {
        return false;
    }
}

//入队(带头结点)
void EnQueue(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;   //新节点插入到rear之后
    Q.rear = s;         //修改表尾指针
}

//队头元素出队
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == Q.rear) {    //空队
        return false;
    }
    LinkNode *p = Q.front->next;
    x = p->data;                //用变量x返回队头元素
    Q.front->next = p->next;    //修改头结点的next指针
    if (Q.rear == p) {          //此次是最后一个节点出队
        Q.rear = Q.front;       //修改rear指针
    }
    free(p);                    //释放节点空间
    return true;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

不头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front, *rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
bool DeQueue(LinkQueue &Q, int &x);
bool IsEmpty(LinkQueue Q);
int main(void) {
    LinkQueue Q;
    int x;
    InitQueue(Q);
    
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    if (!IsEmpty(Q)) {
        printf("x=%d\n", x);
    }
    return 0;
}

//初始化队列
void InitQueue(LinkQueue &Q) {
    //初始时，队头和队尾指针指向头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

//判断队列是否为空
bool QueueEmpty(LinkQueue Q) {
    if (Q.rear == Q.front) {    //队空条件
        return true;
    } else {
        return false;
    }
}

//入队(带头结点)
void EnQueue(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if (Q.front == NULL) {  //在空队列中插入第一个元素
        Q.front = s;        //修改队头队尾指针
        Q.rear = s;
    } else {
        Q.rear->next = s;   //新节点插入到rear之后
        Q.rear = s;         //修改表尾指针
    }
}

//队头元素出队
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == Q.rear) {    //空队
        return false;
    }
    LinkNode *p = Q.front;      //p指向此次出队的节点
    x = p->data;                //用变量x返回队头元素
    Q.front = p->next;          //修改front指针
    if (Q.rear == p) {          //此次是最后一个节点出队
        Q.rear = NULL;          //rear指向NULL
        Q.front = NULL;         //front指向NULL
    }
    free(p);                    //释放节点空间
    return true;
}

bool IsEmpty(LinkQueue Q) {
    if (Q.front == NULL) {
        return true;
    } else {
        return false;
    }
}