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语言 队列的资料请关注编程宝库其它相关文章！

怎么在C++项目中遍历二叉树：本文主要介绍"如何在C++项目中遍历二叉树"，希望能够解决您遇到有关问题，下面我们一起来看这篇 "如何在C++项目中遍历二叉树" 文章。在讲遍历之前，我们要先创建一个树：#include <iostrea ...