数据结构系列学习（八） - 链式队列（Chain_Queue）

目录

引言：

学习：

代码实现：

头文件（Chain_Queue.h）：

队列中的元素范型设定：

队列中的结构体设计：

所有功能函数的声明：

源文件（Chain_Queue.cpp）中的函数功能的具体实现：

初始化函数：

清空函数：

销毁函数：

打印函数：

查找函数：

入队列函数：

判空函数：

出队列函数：

获取有效长度函数：

获取队首元素函数：

测试：

测试初始化函数、打印函数：

测试入队列函数：

测试出队列函数： 

测试查找函数： 

测试获取有效元素个数函数：

测试获取队首元素函数： 

测试销毁函数： 

---

引言：

数据结构学习目录：

数据结构系列学习（一） - An Introduction to Data Structure

数据结构系列学习（二） - 顺序表（Contiguous_List）

数据结构系列学习（三） - 单链表(Linked_List)

数据结构系列学习（四） - 单向循环链表(Circular Linked List)

数据结构系列学习（五） - 双向链表（Double_Linked_List）

数据结构系列学习（六） - 顺序栈（Stack）

数据结构系列学习（七） - 链栈（Chain_Stack）

在之前的文章中，我们对链栈进行了了解和学习，并使用代码对链栈的功能函数进行了实现，并在测试中成功的执行了这些操作。这篇文章中，我们将对另外一种抽象数据类型——队列进行了解和学习，并对队列的其中一种表现形式——链式队列进行实现。

学习：

在写队列的链式存储形式之前，我们先对队列这种抽象数据类型做一个简单的了解。在严蔚敏《数据结构（C语言）》版中对队列是这样定义的：

与栈相反，队列（Queue）是一种先进先出（First in first out缩写为FIFO）的线性表，它只允许在表的一端进行插入，而在另一端进行删除元素。

这玩意儿听着比较抽象，我们举个例子来说明一下：比方说现在你们这个区域的疫情比较严重，政府组织做核酸，你这会儿去排队前面有四个人，如图：

你过去在队伍的后面排队就相当于插入元素的过程，你这时就相当于是要插入的元素，第一个人先来的所以他在前面，第二个人紧随其后，然后是第三个、第四个。然后第一个人做完了直接从前面儿走了，如图：

第一个人做完核酸之后从队伍出去之后的这个过程就相当于是出队列的过程，出去的这个第一个做完核酸的人就相当于是出队列的第一元素，然后是第二个人、第三个、第四个、你。

队列的表现形式：

通过队列的表现形式，我们可以发现如果我们需要通过链表对队列这种抽象数据类型进行实现，我们的入队列操作就相当于是单链表的尾插操作，出队列操作就相当于是单链表的头删操作。

代码实现：

头文件（Chain_Queue.h）：

链式队列中要实现的功能函数：

初始化函数（Init_Queue）；

清空函数(Clear)；

销毁函数(Destroy)；

打印函数(Show)；

查找函数(Search)；

入队列函数(Enter_Queue)；

出队列函数(Delete_Queue)；

判空函数(IsEmpty)；

获取有效长度函数(Get_Length)；

队列中的元素范型设定：

typedef int Elem_type;

队列中的结构体设计：

因为我们是以链式来对队列这种抽象数据类型进行实现的，所以我们就按链表的结构体形式来设定队列的结构体形式。

typedef struct Queue
{
    Elem_type data;
    struct Queue* next;
}Queue,*PQueue;

所有功能函数的声明：

//初始化
void Init_Queue(PQueue pqueue);
//清空
void Clear(PQueue pqueue);
//销毁
void Destroy(PQueue pqueue);
//打印
void Show(PQueue pqueue);
//查找
PQueue Search(PQueue pqueue,Elem_type val);
//入队列
bool Enter_Queue(PQueue pqueue,Elem_type val);
//判空
bool IsEmpty(PQueue pqueue);
//出队列
bool Delete_Queue(PQueue pqueue);
//获取有效长度
int Get_Length(PQueue pqueue);
//返回队首元素
Elem_type Top(PQueue pqueue);

源文件（Chain_Queue.cpp）中的函数功能的具体实现：

初始化函数：

将链式队列的头节点中的数据域浪费掉，直接将链式队列的next域赋值为空地址即可。

void Init_Queue(PQueue pqueue)
{
    assert(pqueue != nullptr);
    pqueue->next = nullptr;
}

清空函数：

清空和销毁函数类似，直接在清空函数内调用销毁函数即可。

void Clear(PQueue pqueue)
{
    Destroy(pqueue);
}

销毁函数：

当链式队列不为空时，无限调用出队列函数，直到队列为空。

void Destroy(PQueue pqueue)
{
    while(!IsEmpty(pqueue)){
        Delete_Queue(pqueue);
    }
}

打印函数：

定义结构体类型指针p指向头节点之后的第一个有效节点，定义循环，循环条件为p不为空地址，将p所指向节点的数据域中的数据打印出来即可。

//打印
void Show(PQueue pqueue)
{
    assert(pqueue != nullptr);
    PQueue p = pqueue->next;
    for(;p != nullptr;p = p->next){
        printf("%3d",p->data);
    }
}

查找函数：

函数类型为结构体指针类型，定义结构体类型指针p指向头节点之后的第一个有效节点，定义循环，循环条件为p不为空地址，如果在遍历的过程中p指向节点的数据域中的数据和我们要查找的数据是吻合的，则直接返回此节点的地址，如果没有找到，则返回空地址。

//查找
PQueue Search(PQueue pqueue,Elem_type val)
{
    assert(pqueue != nullptr);
    PQueue p = pqueue->next;
    for(;p != nullptr;p = p->next){
        if(val == p->data){
            return p;
        }
    }
    return nullptr;
}

入队列函数：

此时的入队列函数就相当于是单链表中的尾插函数，通过malloc函数在堆区申请新节点的内存，将要入队列的数赋值给新节点的数据域，定义结构体类型指针p指向队列头节点，定义循环，循环条件为p的next域不为空，循环结束后p指向的就是末尾节点，将末为节点的next域（nullptr）赋值给pnewnode的next域，再将pnewnode自身的地址，赋值给原先末尾节点的next域即可。

//入队列
bool Enter_Queue(PQueue pqueue,Elem_type val)
{
    assert(pqueue != nullptr);
    PQueue pnewnode = (PQueue)malloc(1 * sizeof(Queue));
    assert(pnewnode != nullptr);
    pnewnode->data = val;
    PQueue p = pqueue;
    for(;p->next != nullptr;p = p->next);
    pnewnode->next = p->next;
    p->next = pnewnode;
    return true;
}

判空函数：

当链式队列头节点的next域为空时，链式队列就为空。

//判空
bool IsEmpty(PQueue pqueue)
{
    assert(pqueue != nullptr);
    return pqueue->next == nullptr;
}

出队列函数：

此时的出队列函数就相当于是单链表中的头删函数，首先对链式队列进行判空操作，如果队列为空则直接返回为假，定义结构体类型指针p指向头节点之后的第一个有效节点，然后进行跨越指向操作，将p的next域中存放的地址（也就是头节点之后第二个有效节点的地址）赋值给头节点的next域即可。

//出队列
bool Delete_Queue(PQueue pqueue)
{
    assert(pqueue != nullptr);
    if(IsEmpty(pqueue)){
        return false;
    }
    PQueue p = pqueue->next;
    pqueue->next = p->next;
    return true;
}

获取有效长度函数：

定义count整形值，定义结构体类型指针p指向头节点之后的第一个有效节点，定义循环，循环条件为p不为空地址，p每遍历一个节点，count的值就加1，最后返回count的值即可。

//获取有效长度
int Get_Length(PQueue pqueue)
{
    assert(pqueue != nullptr);
    int count = 0;
    PQueue p = pqueue->next;
    for(;p != nullptr;p = p->next){
        count++;
    }
    return count;
}

获取队首元素函数：

直接返回头节点之后的第一个有效节点的数据域中存放的数据即可。

//返回队首元素
Elem_type Top(PQueue pqueue)
{
    assert(pqueue != nullptr);
    return pqueue->next->data;
}

测试：

测试初始化函数、打印函数：

#include
#include
#include
#include "Chain_Queue.h"
int main()
{
    Queue head;
    Init_Queue(&head);
    for(int i = 0;i < 10;i++){
        Enter_Queue(&head,i + 1);
    }
    printf("原始队列数据为：\n");
    Show(&head);
/*
    此处添加其他测试函数......
*/

 运行结果：

测试入队列函数：

    Enter_Queue(&head,11);
    printf("\n元素11入队列之后的数据为：\n");
    Show(&head);

运行结果：

如图，成功地将元素11添加到了队列的末尾。

测试出队列函数： 

    Delete_Queue(&head);
    printf("\n经过一次出队列操作后的数据为：\n");
    Show(&head);

运行结果：

如图，首位元素1已经出队列了。

测试查找函数： 

我们将要查找的元素设定为4:

    PQueue p = Search(&head,4);
    printf("\n要查找的元素的地址为：%p\n",p);

运行结果：

如图，成功地将队列中元素4的地址返回了出来。

我们讲要查找的元素设定为100:

    PQueue p = Search(&head,100);
    printf("\n要查找的元素的地址为：%p\n",p);

运行结果：

如图，队列中并没有元素100，程序返回了空地址。

测试获取有效元素个数函数：

    int count = Get_Length(&head);
    printf("\n此链式队列中的有效数据个数为：%d\n",count);

运行结果：

如图，获取到了经过一次出栈操作之后的元素个数为10个。

测试获取队首元素函数： 

    int top = Top(&head);
    printf("\n此时此队列的队首元素为：%d\n",top);

运行结果：

如图，获取到经过一次出栈操作之后的队首元素为2.

测试销毁函数： 

    Destroy(&head);
    printf("\n经过销毁操作之后的队列为：\n");
    Show(&head);

运行结果：

如图，成功将链式队列销毁了（没有数据） 。