数据结构初阶详解线性表之队列

将两个指针置为空就行

2.3、入队

队列的入队一般是在队尾进行操作的，我们在编写代码的时候要留个心眼，如果当前队列一个元素都没有，那在插入的时候就是头尾指针指向同一个节点，如果队列中已经有元素了，那就只用对尾指针进行操作，最后记得将尾指针指向最新的节点下面是具体代码：

//现在是入队列
void Push_Queue(Queue* pQueue, Elemtype data) {
    assert(pQueue);
    //创建新节点
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("新节点创建失败....\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;
    if (pQueue->phead == NULL) {
        //说明是头节点
        pQueue->phead = pQueue->ptail = newNode;
    } else {
        pQueue->ptail->next = newNode;
    }
    pQueue->ptail = newNode;
}

2.4、出队

出队一般来说是对头指针进行操作的，与入队一样，我们也考虑到当队列中只有一个元素时，释放完头指针，要将头指针与尾指针同时置为 NULL，如果队列中不止一个元素，那就只用对头指针进行操作，然后将头指针指向下一个元素，下面是具体的代码：

//出队列
void Pop_Queue(Queue* pQueue) {
    assert(pQueue);
    if (pQueue->phead == NULL) {
        printf("当前队列为空，无法出队...\n");
        return;
    }
    //如果只有一个节点
    if (pQueue->phead == pQueue->ptail) {
        free(pQueue->phead);
        pQueue->phead = pQueue->ptail = NULL;
    } else {
        QueueNode* delet = pQueue->phead;
        pQueue->phead = pQueue->phead->next;
        free(delet);
        delet = NULL;
    }
}

2.5、取队头队尾数据

这个操作相对简单一点，我们只用返回队头队尾的节点元素即可，代码如下：

//取队头元素
Elemtype Get_first_elem(Queue* pQueue) {
    assert(pQueue);
    return pQueue->phead->data;
}

//取队尾元素
Elemtype Get_tail_elem(Queue* pQueue) {
    assert(pQueue);
    return pQueue->ptail->data;
}

这里要注意的是，我们在设计返回类型的时候，要将返回值设置为我们想要的类型，在这里我提前将 int 类型重命名为了 Elemtype，在代码总和那一块我会展示出来。

2.6、队列中有效的元素个数

在这个操作中，我们有两种操作方式，第一种就是传统的使用遍历的方式，将节点数一一记录下来；第二种就是在入队的时候用一个变量 size++，在出队的时候对 size--，这样就能实时更新队列中的元素个数了，第二种方式在返回个数的时候要比第一种快很多，下面是两种代码的展示:

//第一种的传统方式：//计算队列中有效的元素个数
int Size_Queue(Queue* pQueue) {
    assert(pQueue);
    int size = 0;
    QueueNode* pcur = pQueue->phead;
    while (pcur) {
        size++;
        pcur = pcur->next;
    }
    return size;
}

//第二种返回方式（需维护全局或成员变量 size）
// int Size_Queue(Queue* pQueue, int size){
//     assert(pQueue);
//     return size;
// }

2.7、队列的销毁

队列的销毁与链表的销毁相同，用遍历指针逐一将节点一一销毁，最后将头尾指针置为 NULL:

void Destory_Queue(Queue* pQueue) {
    assert(pQueue);
    QueueNode* pcur = pQueue->phead;
    while (pcur) {
        QueueNode* delet = pcur;
        pcur = pcur->next;
        free(delet);
        delet = NULL;
    }
    pQueue->phead = pQueue->ptail = NULL;
}

要提醒的是，一定要将头尾指针置为 NULL，不要这两个指针会成为野指针!!!!

三、综合代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<windows.h>

typedef int Elemtype;

//现在定义队列节点:
typedef struct QueueNode {
    Elemtype data; //数据域
    struct QueueNode* next; //指针域
}QueueNode;

//现在定义队列结构体:
typedef struct Queue {
    QueueNode* phead;
    QueueNode* ptail;
}Queue;

//现在初始化队列:
void Init_Queue(Queue* pQueue) {
    pQueue->phead = pQueue->ptail = NULL;
}

//现在是入队列
void Push_Queue(Queue* pQueue, Elemtype data) {
    assert(pQueue);
    //创建新节点
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("新节点创建失败....\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;
    if (pQueue->phead == NULL) {
        //说明是头节点
        pQueue->phead = pQueue->ptail = newNode;
    } else {
        pQueue->ptail->next = newNode;
    }
    pQueue->ptail = newNode;
}

//出队列
void Pop_Queue(Queue* pQueue) {
    assert(pQueue);
    if (pQueue->phead == NULL) {
        printf("当前队列为空，无法出队...\n");
        return;
    }
    //如果只有一个节点
    if (pQueue->phead == pQueue->ptail) {
        free(pQueue->phead);
        pQueue->phead = pQueue->ptail = NULL;
    } else {
        QueueNode* delet = pQueue->phead;
        pQueue->phead = pQueue->phead->next;
        free(delet);
        delet = NULL;
    }
}

//取队头元素
Elemtype Get_first_elem(Queue* pQueue) {
    assert(pQueue);
    return pQueue->phead->data;
}

//取队尾元素
Elemtype Get_tail_elem(Queue* pQueue) {
    assert(pQueue);
    return pQueue->ptail->data;
}

//计算队列中有效的元素个数
int Size_Queue(Queue* pQueue) {
    assert(pQueue);
    int size = 0;
    QueueNode* pcur = pQueue->phead;
    while (pcur) {
        size++;
        pcur = pcur->next;
    }
    return size;
}

void Destory_Queue(Queue* pQueue) {
    assert(pQueue);
    QueueNode* pcur = pQueue->phead;
    while (pcur) {
        QueueNode* delet = pcur;
        pcur = pcur->next;
        free(delet);
        delet = NULL;
    }
    pQueue->phead = pQueue->ptail = NULL;
}

//现在是打印队列
void my_printf(Queue* pQueue) {
    assert(pQueue);
    if (pQueue->phead == NULL) {
        printf("当前队列为空，无法打印...\n");
        return;
    } else {
        QueueNode* pcur = pQueue->phead;
        while (pcur) {
            printf("%d ", pcur->data);
            pcur = pcur->next;
        }
    }
}

//现在是打印菜单
void print_menu() {
    printf("=========================================\n");
    printf("1.入队 2.出队\n");
    printf("3.取队头元素 4.取队尾元素\n");
    printf("5.计算队列元素个数\n");
    printf("=========================================\n");
    printf("\n");
}

int main() {
    Queue L;
    Queue* pQueue = &L;
    Init_Queue(pQueue);
    int choose;
    do {
        system("cls");
        print_menu();
        printf("当前的队列为:\n");
        my_printf(pQueue);
        printf("\n");
        printf("请输入你的选择:\n");
        scanf("%d", &choose);
        switch (choose) {
        case 1: {
            printf("请输入你想输入的元素个数:\n");
            int num = 0;
            scanf("%d", &num);
            Elemtype data = 0;
            printf("请输入你想输入的元素:\n");
            for (int i = 0; i < num; i++) {
                scanf("%d", &data);
                Push_Queue(pQueue, data);
            }
            printf("正在输入...\n");
            Sleep(1000);
            printf("输入成功~\n");
            Sleep(2000);
            break;
        }
        case 2: {
            printf("正在出队...\n");
            Sleep(1000);
            Pop_Queue(pQueue);
            printf("出队成功~\n");
            Sleep(2000);
            break;
        }
        case 3: {
            Elemtype elem = Get_first_elem(pQueue);
            printf("正在取出对队头元素...\n");
            Sleep(1000);
            printf("队头元素为：%d", elem);
            Sleep(2000);
            break;
        }
        case 4: {
            Elemtype elem = Get_tail_elem(pQueue);
            printf("正在取出对队尾元素...\n");
            Sleep(1000);
            printf("队尾元素为：%d", elem);
            Sleep(2000);
            break;
        }
        case 5: {
            printf("正在计算队列大小...\n");
            int num = Size_Queue(pQueue);
            Sleep(1000);
            printf("队列的大小为：%d", num);
            Sleep(1000);
            break;
        }
        case -1: {
            printf("正在退出程序...\n");
            Sleep(1000);
            printf("退出成功~\n");
            Sleep(500);
        }
        }
    } while (choose != -1);
    Destory_Queue(pQueue);
    return 0;
}