AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】C语言队列(详解)

2023-10-24 147
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】C语言队列(详解)

前言:

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨专栏:http://t.csdn.cn/oXkBa

⛳⛳本篇内容:c语言数据结构--C语言实现队列


一.队列概念及结构


1.1队列的概念

队列：只允许 在一端进行插入数据操作，在 另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列： 进行插入操作的一端称为队尾

出队列： 进行删除操作的一端称为队头


1.2队列的结构

c9b5f4f7a5324bb2aaa0ef47aed13a34.png


二.队列的实现


队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

image.png


2.1头文件

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


2.2链式队列的结构定义

typedef int QDataType;
typedef struct QueueNode
{ 
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.


 QueueNode结构体表示队列中的节点，每个节点包含一个数据项 data 和一个指向下一个节点的指针 next。Queue结构体表示整个队列，包含指向队列头部和尾部节点的指针 phead和ptail，以及记录队列大小的变量 size


2.3队列接口的定义

void QueueInit(Queue* pq);// 初始化队列
void QueueDestroy(Queue* pq);// 销毁队列
void QueuePush(Queue* pq, QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
int QueueSize(Queue* pq);// 获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0


2.4初始化队列

void QueueInit(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  pq->phead=NULL; //将队列的头指针置为空
  pq->ptail = NULL;//将队列的尾指针置为空
  pq->size = 0;// 将队列的头指针置为空
}


2.5判断队列是否为空

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //方法一,将队列的头指针以及尾指针置空
  //return pq->phead = NULL && pq->ptail==NULL;
  //方法二,将队列的有效元素置空
  return pq->size == 0;
}


2.6销毁队列

代码解析:

  1. assert(pq) 用于断言pq 指针不为空，确保传入的指针有效。
  2. 创建一个指针 cur，并将其初始化为队列的头指针 pq->phead。
  3. 进入循环，遍历队列中的每个节点。
  4. 在循环中，首先保存当前节点的下一个节点指针为next，以便在释放当前节点后能够访问下一个节点。
  5. 使用 free(cur) 释放当前节点的内存。
  6. 将指针 cur 移动到下一个节点，即cur = next。
  7. 循环继续，直到遍历完队列中的所有节点。
  8. 在循环结束后，将队列的头指针和尾指针 pq->phead、pq->ptail都置为空，表示队列已经为空。
  9. 将队列的大小pq->size 置为 0，表示队列中没有元素。
void QueueDestroy(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
  while (cur)
  {
    QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
    free(cur);// 释放当前节点的内存
    cur = next;// 将指针 cur 移动到下一个节点
  }
  pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  pq->size = 0;// 将队列的大小置为0
}


2.7队尾入队列

第一种情况:尾插第一个队列元素

513deb1184844536a565d7873183fab4.gif


第二种情况:已有元素前提下尾插节点

先尾插节点，后把新节点的地址给ptail(让ptail指向新节点)

d0b53e04de8f4f5db21173cd85458049.gif

void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点
  if (newnode == NULL)
  {
    perror("malloc fail\n");// 检查内存分配是否成功
    return;
  }
  newnode->data = x;// 设置新节点的数据为传入的元素值
  newnode->next = NULL;// 将新节点的指针域置空
  //一个节点
  if (pq->ptail == NULL)// 判断队列是否为空
  {
    assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
    pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
  }
    //多个节点
  else
  {
    pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
    pq->ptail = newnode;// 更新队列的尾指针为新节点
  }
  pq->size++;// 增加队列的大小计数
}

代码执行:

330d314437f74c0f9a55d2666b382db9.png


2.8队头出队列

第一种:队列只有一个元素时

b3ed2d0b0ddb49d689a60bb1161834c5.gif

第二种:队列有多个元素时

b9b117fc61204324a80dc92d9464fc08.gif

void QueuePop(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->phead);// 检查队列的头指针是否存在
  //1.一个节点
  if (pq->phead->next == NULL) // 队列只有一个节点的情况
  {
    free(pq->phead); // 释放队列头节点的内存
    pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  }
    //2.多个节点
  else
  {
    QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
    free(pq->phead);// 释放队列头节点的内存
    pq->phead = next;// 更新队列的头指针为下一个节点
  }
  pq->size--;//减少队列的大小计数
}

代码执行:

2a919d14f42f4f938c03a868f6e73e66.png


2.9获取队列头部元素

QDataType QueueFront(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->phead);// 检查队列的头指针是否存在
  return pq->phead->data;// 返回队列头节点的数据
}


代码执行:

1c6e164f6ccb4ba496c1cbbe56e88aef.png

2.10获取队列队尾元素

QDataType QueueBack(Queue* pq)
{
  assert(pq);// 检查队列是否非空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->ptail);// 检查队列的尾指针是否存在
  return pq->ptail->data;//返回队列尾节点的数据
}


代码执行:

d8a8167208034028b949060d2ae1f771.png

2.11获取队列中有效元素个数

int QueueSize(Queue* pq)
{
  assert(pq);//检查指针是否为空
  return pq->size;//返回队列的大小（元素个数）
}


代码执行:

986c973eddad45e5b9534b079279dee6.png


2.12打印队列元素

void QPrint(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  QNode* next = cur;
  while (cur != NULL)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}


代码执行:

0a75c643fbb745339c2fcd9c5c22b389.png

Test.c

#include"Queue.h"
void TestQueue1()//元素入队列
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q,1);
  QueuePush(&q,2);  
  //printf("%d ", QueueFront(&q));
  //QueuePop(&q);
  QueuePush(&q,3);
  QueuePush(&q,4);
  //printf("Size:%d\n", QueueSize(&q));
  //QPrint(&q);
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
}
void TestQueue2()//元素出队列
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  printf("%d\n", QueueFront(&q));
  QueuePop(&q);
  printf("%d\n", QueueFront(&q));
  QueuePop(&q);
  printf("%d\n", QueueFront(&q));
  QueuePop(&q);
  printf("%d\n", QueueFront(&q));
  printf("\n");
}
void TestQueue3()//获取队列头部和尾部元素,和队列元素个数
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  printf("队列头部元素:%d\n",QueueFront(&q));
  printf("队列尾部元素:%d\n", QueueBack(&q));
  printf("Size:%d\n", QueueSize(&q));
  /*while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }*/
  printf("\n");
}
void TestQueue4()//打印队列
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QPrint(&q);
  printf("\n");
}
int main()
{
  //TestQueue1();//元素入队列
  //TestQueue2();//元素出队列
  //TestQueue3();//获取队列头部和尾部元素,和队列元素个数
  TestQueue4();
}


Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{ 
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.
void QueueInit(Queue* pq);// 初始化队列
void QueueDestroy(Queue* pq);// 销毁队列
void QueuePush(Queue* pq, QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
int QueueSize(Queue* pq);// 获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0


Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  pq->phead=NULL; // 将队列的头指针置为空
  pq->ptail = NULL;// 将队列的头指针置为空
  pq->size = 0;// 将队列的头指针置为空
}
void QPrint(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  QNode* next = cur;
  while (cur != NULL)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}
void QueueDestroy(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
  while (cur)
  {
    QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
    free(cur);// 释放当前节点的内存
    cur = next;// 将指针 cur 移动到下一个节点
  }
  pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  pq->size = 0;// 将队列的大小置为0
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点
  if (newnode == NULL)
  {
    perror("malloc fail\n");// 检查内存分配是否成功
    return;
  }
  newnode->data = x;// 设置新节点的数据为传入的元素值
  newnode->next = NULL;// 将新节点的指针域置空
  //一个节点
  //多个节点
  if (pq->ptail == NULL)// 判断队列是否为空
  {
    assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
    pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
  }
  else
  {
    pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
    pq->ptail = newnode;// 更新队列的尾指针为新节点
  }
  pq->size++;// 增加队列的大小计数
}
void QueuePop(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->phead);// 检查队列的头指针是否存在
  //1.一个节点
  if (pq->phead->next == NULL) // 队列只有一个节点的情况
  {
    free(pq->phead); // 释放队列头节点的内存
    pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  }
  else
  {
    //头删
    QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
    free(pq->phead);// 释放队列头节点的内存
    pq->phead = next;// 更新队列的头指针为下一个节点
  }
  pq->size--;//减少队列的大小计数
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->phead);// 检查队列的头指针是否存在
  return pq->phead->data;// 返回队列头节点的数据
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);// 检查队列是否非空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  assert(pq->phead);// 检查队列的头指针是否存在
  return pq->ptail->data;//返回队列尾节点的数据
}
int QueueSize(Queue* pq)
{
  assert(pq);//检查指针是否为空
  return pq->size;//返回队列的大小（元素个数）
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //方法一,将队列的头指针以及尾指针置空
  //return pq->phead = NULL && pq->ptail==NULL;
  //方法二,将队列的有效元素置空
  return pq->size == 0;
}


     本篇结束，如有错误，欢迎大家指正，感谢来访！

文章标签：
C语言
关键词：
C语言数据结构
数据结构队列
C语言队列
数据结构c语言
数据结构C语言队列
Dream_Chaser～
目录
相关文章
土木林森
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
23 1
XIAZHI
|
21天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
41 4
XIAZHI
|
21天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
38 4
XIAZHI
|
21天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
35 4
XIAZHI
|
21天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
38 4
XIAZHI
|
21天前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
33 4
XIAZHI
|
21天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
32 4
龙大吉
|
13天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
32 5
土木林森
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
36 1
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
140 9