C语言数据结构之队列的定义与实现

目录
  • 一、队列的性质
  • 二、队列的结构
  • 三、代码实现
    • 头文件
    • 功能函数

一、队列的性质

上次我们学习栈，了解到栈储存释放数据的方式是：先进后出

而队列与其相反，队列是：先进先出，后进后出。

二、队列的结构

多个链表节点 + 头尾指针   （链表式队列）

链表节点负责存储数据；头节点 负责定位先进的起始数据，方便先出；

尾节点负责记录尾部数据，方便确定队列当前状态。

三、代码实现

头文件

这里方便统一调用，将头尾指针定义成一个结构体 。

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

typedef int Quetype;          //定义队列的数据类型

typedef struct QueNode        //定义数据节点
{
    struct QueNode* Next;
    Quetype data;
}QueNode;

typedef struct Quetail
{
    struct QueNode* head;     //定义头尾指针
    struct QueNode* tail;
}Quetail;

void Que_Init(Quetail* pq);                //队列的初始化
void Que_Destory(Quetail* pq);             //队列的销毁
void Que_push(Quetail* pq ,Quetype data);  //插入数据
void Que_pop(Quetail* pq);                 //删除数据
bool Que_Empty(Quetail* pq);               //判断队列是否为空
int Que_size(Quetail* pq);                 //统计队列长度
int Que_front(Quetail* pq);                //查找队列的头部数据

功能函数

1.队列的初始化：

将头尾指针置为NULL 方便后续使用。

void Que_Init(Quetail* pq)           //队列的初始化
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

2.插入数据：

创建链表节点 >> 导入数据 >> 头部指针指向头节点 >> 尾部指针指向尾节点

//插入数据
void Que_push(Quetail* pq,Quetype data)
{
    assert(pq);
    QueNode* NewNode = (QueNode*)malloc(sizeof(QueNode));//创建节点
    if (NewNode == NULL)
    {
        printf("Que_push->malloc");
        exit(-1);
    }
    NewNode->Next = NULL;
    NewNode->data = data;
    if (pq->head == NULL)         //判断是否创建为头节点
    {
        pq->head = NewNode;       //更新头指针
    }
    else
    {
        pq->tail->Next = NewNode; //不为头节点，就正常链接在尾节点后
    }
    pq->tail = NewNode;           //更新尾指针
}

3.删除数据：

记录头节点的下一个位置 >> 判断是否为最后的数据 >> 更新头指针

细节点：如果队列中还剩多个节点时，删除头节点后，尾指针始终指向尾节点，不需要改动；

但是如果只剩一个数据节点的话，删除后需要将尾指针置空。

//删除数据
void Que_pop(Quetail* pq)
{
    assert(pq);
    assert(!Que_Empty(pq));         //判断队列是否为空
    QueNode* Next = pq->head->Next; //记录删除数据的

    if (pq->head == pq->tail)       //判断是否是最后的数据
    {
        free(pq->head);
        pq->tail = NULL;            //更新尾指针
    }
    else
    {
        free(pq->head);
    }
    pq->head = Next;                //更新头指针
}

4.判断列表是否为空：

用bool 作为返回类型

//判断队列是否为空
bool Que_Empty(Quetail* pq)
{
    assert(pq);
    return pq->head == NULL;
}

5.查找队列的头部数据：

判断队列是否为空 >> 返回头部数据

//查找队列的头部数据
Quetype Que_front(Quetail* pq)
{
    assert(pq);
    assert(!Que_Empty(pq));    //判断队列是否为空
    return pq->head->data;     //返回头部数据
}

6. 统计队列的长度：

就是统计有多少个链表节点

int Que_size(Quetail* pq)
{
    assert(pq);
    int size;
    QueNode* pphead = pq->head;
    for (size = 0; pphead; pphead = pphead->Next, size++);
    return size;
}

7.队列的销毁：

依次删除数据 >> 将申请空间释放

细节点：这里可以进行复用：判断队列是否为空 、 删除数据

void Que_Destory(Quetail* pq)
{
    for (; !Que_Empty(pq); )  //判断队列是否为空
    {
        Que_pop(pq);          //删除数据
    }
}

以上就是C语言数据结构之队列的定义与实现的详细内容，更多关于C语言 队列的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言数据结构之队列算法详解

    C语言数据结构之队列算法详解

    目录 一.前言 二.基本概念 三.顺序队列 四.链队列 五.循环队列 六.总结与提高 一.前言 队列在程序设计中经常出现,如:操作系统中的排队问题. 这篇文章主要介绍了队列的基本概念.性质,顺序.链.循环三种不同的方法实现队列,顺序和循环队列在算法中比较常用 二.基本概念    定义:队列是允许在一端插入,另一端删除的线性表 队头(front):允许删除的一端 队尾(rear):允许插入的一端 特点:先进先出 三.顺序队列 动态图: 算法讲解:  图解:入队,rear++,出队,front++

  • C语言数据结构进阶之栈和队列的实现

    C语言数据结构进阶之栈和队列的实现

    目录 栈的实现: 一.栈的概念和性质 二.栈的实现思路 三.栈的相关变量内存布局图 四.栈的初始化和销毁 五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空 队列的实现: 一.队列的概念和性质 二.队列的实现思路 三.队列相关变量的内存布局图 四.队列的初始化和销毁 五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空 总结 栈的实现: 一.栈的概念和性质 栈(stack)又名

  • 详解数据结构C语言实现之循环队列

    详解数据结构C语言实现之循环队列

    本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize

  • C语言编程数据结构栈与队列的全面讲解示例教程

    C语言编程数据结构栈与队列的全面讲解示例教程

    目录 一.栈的表示和实现 1栈的概念和结构 2栈的初始化 3压栈(栈顶插入一个数据) 4出栈(栈顶删除一个数据) 5取栈顶元素 6取栈顶元素 7判断栈是否为空 二.队列的表示和实现 1队列的概念及结构 2队列的实现 3队列初始化 4入队(队尾插入一个数据) 5出队(队头删除一个数据) 6取队头数据 7取队尾数据 8计算队列中数据个数 9判断队列是否为空 10销毁队列 总结 一.栈的表示和实现 1栈的概念和结构 栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作.

  • C语言编程数据结构的栈和队列

    C语言编程数据结构的栈和队列

    目录 栈 数组实现 标题全部代码 Stack_array.c Stack_array.h 初始化数组栈 满栈后扩容 是否为空栈 压栈和退栈 链表实现 stack_chain.h stack_chain.c 整个压栈流程 整个弹栈流程 出栈情况 队列 队列的实现 queue_chain.h queue_chain.c 一个结构体类型用于维护这个队列 概念流程图 入队列的实现 出队列的实现 是否空队 栈 栈是一种以后进先出为顺序对对象进行添加或删除的数据结构 对栈进行形象记忆就像是桌子上的一堆书或一

  • C语言数据结构系列队列篇

    C语言数据结构系列队列篇

    目录 一.队列(Queue) 0x00队列的概念 0x01队列的结构 二.队列的定义 0x00链式队列 0x02 接口函数 三.队列的实现 0x00队列初始化(QueueInit) 0x01销毁队列(QueueDestroy) 0x02判断队列是否为空(HeapIsEmpty) 0x03入队(QueuePush) 0x04出队(QueuePop) 0x05 返回队头数据(QueueFront) 0x06 返回队尾数据(QueueBack) 0x07 求队列大小(QueueSize) 0x08完整

  • C语言数据结构链表队列的实现

    C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的,遵循先进先出原则的线性表. 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码. 分解代码没有包含在内的代码如下: #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status; 2.代码分解 2.1对队列和节点的结构定义 typedef struct

  • C语言数据结构之队列的定义与实现

    C语言数据结构之队列的定义与实现

    目录 一.队列的性质 二.队列的结构 三.代码实现 头文件 功能函数 一.队列的性质 上次我们学习栈,了解到栈储存释放数据的方式是:先进后出 而队列与其相反,队列是:先进先出,后进后出. 二.队列的结构 多个链表节点 + 头尾指针   (链表式队列) 链表节点负责存储数据:头节点 负责定位先进的起始数据,方便先出: 尾节点负责记录尾部数据,方便确定队列当前状态. 三.代码实现 头文件 这里方便统一调用,将头尾指针定义成一个结构体 . #include<stdio.h> #include<

  • C语言数据结构之链队列的基本操作

    C语言数据结构之链队列的基本操作

    目录 1.队列的定义 2.队列的表示和实现 (1) 初始化操作 (2)销毁队列 (3) 入队操作 (4) 出队操作 附录完整代码: 总结 1.队列的定义 队列 (Queue)是另一种限定性的线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出(Fist In Fist Out,缩写为FIFO)的特性.在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front). 假设队列为q=(a1,a2,-,an),那么a1就是队头元素,an则是队尾元素.队列中

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C利用语言实现数据结构之队列

    C利用语言实现数据结构之队列

    目录 一.链队列 二.链队的表示 三.链队的基本操作 1. 链队的初始化 2. 链队的销毁 3. 入队 4. 出队 四.顺序队列 五.循环队列 1. 初始化 2. 求队列长度 3. 入队 4. 出队 前言: 队列在生活中也比较常见,例如购物排队--新来的成员总是加入队尾,每次离开的成员总是队列头上的. 队列按存储方式可以分为两种:顺序队列和链队列. 一.链队列 链式队列中每个元素定义成一个结点,含数据域与指针域(指向下一结点),并设头尾指针.用图表示就是. 二.链队的表示 前面的链式结构,总是使

  • C语言数据结构算法基础之循环队列示例

    C语言数据结构算法基础之循环队列示例

    目录 说明 示例代码 1. 首先定义结构体: 2. 定义各种算法: 3. 测试: 4. 最后的结果: 说明 循环队列是一种先进先出的,首尾相连的队列. 大致的结构如下图: 用数组来抽象的表示一下的话,如下图: 循环队列有两个指针指向数据,上图中的start和end就是那两个指针,它们指向相同的位置,表示的是空,即队列是空的. 随着数据的放入,队列一般有下面的两种形式: 需要注意第二种形式,从图上看end在start的前面了,但是因为循环关系,前后并不重要. 另外需要考虑的是队列满的情况: 但这种

  • C语言数据结构之栈和队列的实现及应用

    C语言数据结构之栈和队列的实现及应用

    目录 一.栈的概念 二.Stack.h 三.Stack.c 1.栈的初始化和销毁 2.栈的进栈.出栈 3.栈的判空.访问栈顶元素.栈内元素个数 四.队列的概念 五.Queue.h 六.Queue.c 1.队列的初始化和销毁 2.队列的入队.出队 3.队列的判空 4.访问队头.队尾数据.统计队列长度 七.力扣中栈和队列OJ题 1.有效的括号 2.用队列实现栈 3.用栈实现队列 4.设计循环队列 栈和队列是一种数据结构,只规定了性质,并没有规定实现方式. 本文以顺序结构实现栈,链表方式实现队列. 一

随机推荐