前言

上一章节针对于C语言栈结构做了解析，不清楚的可以回顾一下。

本章节主要针对于C语言的基础数据结构队列做以解析。

数据结构之队列

队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队友。

故队列基本操作如下：

（1）创建队列

（2）入队

（3）出队

（4）判断队列是否为NULL

（5）获取队头元素

数据结构之队列分类

根据队列实现方式与出队方式，我们可以把栈分为以下三种描述方式：

（1）原生数组队列

（2）动态申请内存的数组描述(普通队列和循环队列）

（3）链式结构描述

优先队列

原生数组描述队列

数组描述栈，只不过多了先进先出的限制而已，它是静态分配的，即使用前，它的内存就已经以数组的形式分配好了，所以在使用时，需要注意队头队尾的标记。

原生数组描述队列实现试题案例:逆序整数

动态数组描述队列

动态申请内存的数组描述不再采用上述实用性的方法了，而是通过封装相关队列函数去描述这种结构。这是写数据结构的一种大致方法。

1.结构体定义与队列的创建过程：

结构体定义:描述队列的属性：队头标记，队尾标记，队列空间

创建队列其实就是创建结构体变量

具体代码

ps:队头和队尾顶标记初始值一般都是-1 ，为了满足队列标记和数组下标一致

2.入队操作

注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的队列队尾元素，故可以使用队尾标记去计算队列中的元素个数。然后每次入队后，队尾标记往后移动。

具体实现代码：

3.出队操作和获取队头元素

注意: 出队操作应该是将队头元素删除,由于数组实现的队列无法删除，故只能把队头标记往队尾移动，简称为一种"伪删除"。

具体实现代码：

4.判断栈是否为空

用户判断栈中是否有元素，通过队尾和队头标记去做即可

具体实现代码：

动态申请内存的数组描述队列测试代码

ps:循环队列是通过区域形成的循环，这里不过多介绍，有兴趣的可以看看相关资料。

链式队列

链式队列： 链表的尾插法即可

具体实现源码线上

#include <stdio.h>#include <stdlib.h>typedef struct{  int data;  struct Node* next;}NODE,*LPNODE;LPNODE createNode(int data){  LPNODE newNode = (LPNODE)malloc(sizeof(NODE));  newNode->data = data;  newNode->next = NULL;  return newNode;}typedef struct{  int queueSize;  LPNODE frontNode;  LPNODE tailNode;}QUEUE,*LPQUEUE;LPQUEUE createQueue(){  LPQUEUE queue = (LPQUEUE)malloc(sizeof(QUEUE));  queue->queueSize = 0;  queue->frontNode = NULL;  queue->tailNode = NULL;  return queue;}void push(LPQUEUE queue, int data){  //无头表头链表的在封装法  LPNODE newNode = createNode(data);  if (queue->queueSize == 0)  {    queue->frontNode = newNode;    queue->tailNode = newNode;  }  else  {    //无表头链表的表尾插入    queue->tailNode->next = newNode;    queue->tailNode = newNode;  }  queue->queueSize++;}//FILO  +FIFOvoid pop(LPQUEUE queue){  if (queue->queueSize != 0)  {    LPNODE nextNode = queue->frontNode->next;    free(queue->frontNode);     queue->frontNode = nextNode;    queue->queueSize--;   }}int front(LPQUEUE queue){  return queue->frontNode->data;}int empty(LPQUEUE queue){  return queue->queueSize==0;}int size(LPQUEUE queue){  return queue->queueSize;}int main(){  LPQUEUE queue = createQueue();  for (int i = 1; i <= 3; i++)  {    push(queue, i);  }  while (!empty(queue))  {    printf("%d\t", front(queue));    pop(queue);  }  printf("\n");  system("pause");  return 0;}

优先队列:根据优先权去决定你出队的元素，故数据中存在优先权衡量的值，相关实现代码如下：

#include <iostream>#define MaxQueueSize 100    //队列的大小//数据类型   数据本身  优先权typedef int ElementType;  //定义数据类型地 别名 //数据 结构体typedef struct {  int priority;    //优先权---工作量  ElementType element;//队列中的元素}DataType; //队列的结构体typedef struct{  int size;  //结构体的嵌套  DataType Queue[MaxQueueSize];}PriQueue;//读取文件作业---调度读取//队列操作//初始化---初始化基本成员//size   Queuevoid InitQueue(PriQueue *Q){  Q->size = 0;}//判断队列是否为空  NULL//和它的初始化比较int QueueEmpty(PriQueue *Q){  // -> 指向运算符  C：结构体指针  C++： 类和结构体  // :: 作用域限定符  if (Q->size <= 0)    return 0;   //标志  else    return 1;  //不为空  //  return 0 函数结束}//入队 文件操作int Push(PriQueue *Q, DataType data){  //入队前判断是否满  if (Q->size >= MaxQueueSize)  {    std::cout << "杯子已满，无法再倒水" << std::endl;    return 0;  }  else  {    //Q->size=0;    Q->Queue[Q->size] = data;    //入队了队列长度就要增长    Q->size++;    return 1;  } }//出队int Pop(PriQueue *Q, DataType *A){  DataType min;    //最小的开始，排序  int minIndex = 0;  //短作业优先法  //喝水，先判断杯子有没有水  if (Q->size <= 0)  {    std::cout << "为空，无法出队" << std::endl;    return 0;  }  else  {    //假设第一个作业是最短的    min = Q->Queue[0];  //1    for (int i = 1; i < Q->size; i++)    {      //多了一个数据项  按照权值排序      //0      if (Q->Queue[i].priority < min.priority)      {        min = Q->Queue[i];        minIndex = i;    //出队依据就是最小作业序号      }    }    *A = Q->Queue[minIndex];    //难点     //删除完数组后，后面的元素往前移动    for (int i = minIndex + 1; i < Q->size; i++)    {      Q->Queue[i - 1] = Q->Queue[i];      minIndex = i;    }    Q->size--;    return 1;  }   }//获取队头元素int GetQueue(PriQueue *Q, DataType *A){  DataType min;    //最小的开始，排序  int minIndex = 0;  //短作业优先法  //喝水，先判断杯子有没有水  if (Q->size <= 0)  {    std::cout << "为空，无法出队" << std::endl;    return 0;  }  else  {    //假设第一个作业是最短的    min = Q->Queue[0];  //1    for (int i = 1; i < Q->size; i++)    {      //多了一个数据项  按照权值排序      //0      if (Q->Queue[i].priority < min.priority)      {        min = Q->Queue[i];        minIndex = i;    //出队依据就是最小作业序号      }    }    *A = Q->Queue[minIndex];    return 1;  }}

希望对大家有帮助！

另外如果你想更好的提升你的编程能力，学好C语言C++编程！弯道超车，快人一步！

编程学习软件分享：

编程学习视频分享：

分享（源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

C语言C++编程学习交流圈子，点击下方【了解更多】获取更多学习资料哦~