C语言队列的链表实现

2021-01-07

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

队列的链表实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。队列指针front指向链表头部方便删除操作，队列指针rear指向链表尾部方便插入操作。

假定内存足够大，链队无队满情况。

code（整型数据的队列）

#include <stdio.h>
#include <stdlib.h>

#define ElementType int
#define ERROR -99 //ElementType的特殊值，标志错误

typedef struct Node
{
    ElementType data;
    struct Node *next;
} QNode;

typedef struct
{
    QNode *front; //指向队头节点
    QNode *rear;  //指向队尾节点
} Queue;

Queue *CreateQueue()
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    if (!q)
    {
        printf("空间不足！\n");
        return NULL;
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void AddQNode(Queue *q, ElementType item)
{
    QNode *qNode = (QNode *)malloc(sizeof(QNode));
    if (!qNode)
    {
        printf("空间不足！\n");
        return;
    }
    qNode->data = item;
    qNode->next = NULL;
    if (q->front == NULL)
    {
        q->front = qNode;
    }
    if (q->rear == NULL)
    {
        q->rear = qNode;
    }
    else
    {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}

int IsEmptyQueue(Queue *q)
{
    return (q->front == NULL);
}

ElementType DeleteQNode(Queue *q)
{
    if (IsEmptyQueue(q))
    {
        printf("空队列\n");
        return ERROR;
    }
    QNode *temp = q->front;
    ElementType item;
    if (q->front == q->rear)
    { //若队列只有一个元素
        q->front = NULL;
        q->rear = NULL;
    }
    else
    {
        q->front = q->front->next;
    }
    item = temp->data;
    free(temp);
    return item;
}

void PrintQueue(Queue *q)
{
    if (IsEmptyQueue(q))
    {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    QNode *qNode = q->front;
    while (qNode != NULL)
    {
        printf("%d ", qNode->data);
        qNode = qNode->next;
    }
    printf("\n");
}

// 销毁队列
int destroyQueue(Queue *q)
{
    while (q->front)
    {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }

    if (q->rear == q->front)
    {
        return 1;
    }

    return 0;
}

int main(int argc, const char *argv[])
{
    Queue *q = CreateQueue();

    AddQNode(q, 1);
    PrintQueue(q);

    DeleteQNode(q);
    PrintQueue(q);

    AddQNode(q, 2);
    AddQNode(q, 3);
    AddQNode(q, 4);
    PrintQueue(q);

    DeleteQNode(q);
    DeleteQNode(q);
    PrintQueue(q);

    AddQNode(q, 5);
    AddQNode(q, 6);
    PrintQueue(q);

    int whether = destroyQueue(q);
    PrintQueue(q);

    return 0;
}

code（字符串数据的队列）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STRING_LENGTH 10

typedef struct Node
{
    // 一定初始化字符数组的大小
    char data[STRING_LENGTH];
    struct Node *next;
} QNode;

typedef struct
{
    QNode *front; //指向队头节点
    QNode *rear;  //指向队尾节点
} Queue;

Queue *CreateQueue()
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    if (!q)
    {
        printf("空间不足！\n");
        return NULL;
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void AddQNode(Queue *q, char item[])
{
    QNode *qNode = (QNode *)malloc(sizeof(QNode));
    if (!qNode)
    {
        printf("空间不足！\n");
        return;
    }
    strcpy(qNode->data, item);
    qNode->next = NULL;
    if (q->front == NULL)
    {
        q->front = qNode;
    }
    if (q->rear == NULL)
    {
        q->rear = qNode;
    }
    else
    {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}

int IsEmptyQueue(Queue *q)
{
    return (q->front == NULL);
}

char* DeleteQNode(Queue *q)
{
    if (IsEmptyQueue(q))
    {
        printf("空队列\n");
        return ERROR;
    }
    QNode *temp = q->front;
    char item[STRING_LENGTH];
    if (q->front == q->rear)
    { //若队列只有一个元素
        q->front = NULL;
        q->rear = NULL;
    }
    else
    {
        q->front = q->front->next;
    }
    strcpy(item, temp->data);
    free(temp);
    return item;
}

void PrintQueue(Queue *q)
{
    if (IsEmptyQueue(q))
    {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    QNode *qNode = q->front;
    while (qNode != NULL)
    {
        printf("%s ", qNode->data);
        qNode = qNode->next;
    }
    printf("\n");
}

// 销毁队列
int destroyQueue(Queue *q)
{
    while (q->front)
    {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }

    if (q->rear == q->front)
    {
        return 1;
    }

    return 0;
}

int main(int argc, const char *argv[])
{
    Queue *q = CreateQueue();

    AddQNode(q, "Hello");
    AddQNode(q, "World!");
    PrintQueue(q);

    DeleteQNode(q);
    PrintQueue(q);

    int whether = destroyQueue(q);
    PrintQueue(q);

    return 0;
}