Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/7.操作受限的线性表 -- 队列 -- 链队列.md

7.1 带头结点

#include <stdlib.h>

typedef int ElemType;
typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
} QueueNode;
typedef struct LinkQueue {
    QueueNode *front, *rear;
} LinkQueue;

/*
 创(初始化) 带头结点
 判空 linkQueue.front->next == NULL
 增
 删 如果队列在要出队时, 队列中只有一个节点, 那么出队后需要 rear=front (逻辑上恢复为空队列)
 查(改)
 */

bool InitLinkQueue(LinkQueue &linkQueue) {
    QueueNode *pNode = (QueueNode *) malloc(sizeof(QueueNode));
    if (pNode == NULL) {
        return false;
    }
    pNode->next = NULL;
    linkQueue.front = linkQueue.rear = pNode;
    return true;
}

bool IsEmpty(LinkQueue &linkQueue) {
    if (linkQueue.front == linkQueue.rear) {
        return true;
    } else {
        return false;
    }
}

bool EnLinkQueue(LinkQueue &linkQueue, ElemType e) {
    QueueNode *sNode = (QueueNode *) malloc(sizeof(QueueNode));
    if (sNode == NULL) {
        return false;
    }
    sNode->data = e;
    sNode->next = NULL;
    linkQueue.rear->next = sNode;
    linkQueue.rear = sNode;
    return true;
}

bool DeLinkQueue(LinkQueue &linkQueue, ElemType &e) {
    if (linkQueue.front == linkQueue.rear) {
        return false;
    }
    QueueNode *qNode = linkQueue.front->next;
    e = qNode->data;
    linkQueue.front->next = qNode->next;
    if (qNode == linkQueue.rear) {
        linkQueue.rear = linkQueue.front;
    }
    free(qNode);
    return true;
}

bool GetFront(LinkQueue linkQueue, ElemType &e) {
    if (linkQueue.front == linkQueue.rear) {
        return false;
    }
    e = linkQueue.front->next->data;
    return true;
}

7.2 不带头结点

#include <stdlib.h>

typedef int ElemType;
typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
} QueueNode;
typedef struct LinkQueue {
    QueueNode *front, *rear;
} LinkQueue;

/*
 创(初始化) 不带头结点
 判空 front == NULL 或 rear == NULL
 增 如果队列在要入队时, 队列为空队列, 那么入队后需要修改队头指针和队尾指针都指向第一个入队的节点
 删 如果队列在要出队时, 队列中只有一个节点, 那么出队后需要 rear=front=NULL (逻辑上恢复为空队列)
 查(改)
 */

bool InitLinkQueue(LinkQueue &linkQueue) {
    linkQueue.front = NULL;
    linkQueue.rear = NULL;
    return true;
}

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

bool EnLinkQueue(LinkQueue &linkQueue, ElemType e) {
    QueueNode *sNode = (QueueNode *) malloc(sizeof(QueueNode));
    if (sNode == NULL) {
        return false;
    }
    sNode->data = e;
    sNode->next = NULL;
    if (linkQueue.front == NULL) {
        linkQueue.front = sNode;
        linkQueue.rear = sNode;
    } else {
        linkQueue.rear->next = sNode;
        linkQueue.rear = sNode;
    }
    return true;
}

bool DeLinkQueue(LinkQueue &linkQueue, ElemType &e) {
    if (linkQueue.front == NULL) {
        return false;
    }
    QueueNode *qNode = linkQueue.front->next;
    e = qNode->data;
    linkQueue.front->next = qNode->next;
    if (qNode == linkQueue.rear) {
        linkQueue.front = NULL;
        linkQueue.rear = NULL;
    }
    free(qNode);
    return true;
}

bool GetFront(LinkQueue linkQueue, ElemType &e) {
    if (linkQueue.front == NULL) {
        return false;
    }
    e = linkQueue.front->next->data;
    return true;
}