AI 助理
备案控制台
开发者社区 云计算 文章 正文

＜队列（链式）＞《数据结构(C语言版)》

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

目录

《数据结构(C语言版)》实战项目之队列（链式）的功能实现

                                                                            ——By 作者：新晓·故知

一、完整源码：

               完整源码如下，欢迎复制测试指正！

               队列（链式）的功能实现测试示例：  

      完整源码：

       二、队列（链式）的功能实现分析：

1.队列的概念及结构

2.队列的实现功能函数：

（1）初始化队列

（2）销毁队列

（3）插入（进队）

（4）删除（出队）

（5）判断队列是否为空

（6）判断队列大小

（7）队头

（8）队尾

扩展了解：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                          ——By 作者：新晓·故知

 

《数据结构(C语言版)》实战项目之队列（链式）的功能实现

                                                                            ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

队列（链式）的功能实现测试示例：  image.gif编辑

完整源码：

Test.c:

#include "Queue.h"
//队列（链式）的功能实现
//初始化队列测试
void TestQueue1()
{
  Queue q;
  QueueInit(&q);
  ////1.一个一个创建数据
  //QueuePush(&q, 1);
  //QueuePush(&q, 2);
  //QueuePush(&q, 3);
  //QueuePush(&q, 4);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
  }
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
}
//判断队列大小测试
void TestQueue2()
{
  Queue q;
  QueueInit(&q);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    /*printf("%d ", QueueFront(&q));
    QueuePop(&q);*/
  }
  printf("\n");
  //判断队列大小
  size_t size=QueueSize(&q);
  printf("队列的大小为：%u", size);
}
//队头查找打印测试
void TestQueue3()
{
  Queue q;
  QueueInit(&q);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    /*printf("%d ", QueueFront(&q));
    QueuePop(&q);*/
  }
  printf("%d ", QueueFront(&q));
}
//队尾查找打印测试
void TestQueue4()
{
  Queue q;
  QueueInit(&q);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    /*printf("%d ", QueueFront(&q));
    QueuePop(&q);*/
  }
  printf("%d ", QueueBack(&q));
}
//入队+出队测试
void TestQueue5()
{
  Queue q;
  QueueInit(&q);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    //入队
    QueuePush(&q, i);
    printf("%d ", QueueFront(&q));
    //出队
    QueuePop(&q);
  }
  printf("\n");
}
//销毁队列测试
void TestQueue6()
{
  Queue q;
  QueueInit(&q);
  //2.使用循环创建数据
  for (int i = 1; i < 6; ++i)
  {
    QueuePush(&q, i);
    printf("%d ", QueueFront(&q));
    //删除队头
    QueuePop(&q);
  }
  printf("\n");
  QueueEmpty(&q);
  QueueDestroy(&q);
  printf("%d ", QueueFront(&q));
}
int main()
{
  TestQueue1();
  TestQueue2();
  TestQueue3();
  TestQueue4();
  TestQueue5();
  //TestQueue6();
  return 0;
}
image.gif

Queue.c:

#include "Queue.h"
//队列（链式）的功能实现
//队列的功能函数
//初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//插入（进队）
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //开辟新结点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
    assert(pq->head == NULL);
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//删除（出队）
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head && pq->tail);
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //return pq->head == NULL && pq->tail == NULL;
  return pq->head == NULL;
}
//队列大小
//size_t即unsigned int，包含在头文件
size_t QueueSize(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  size_t size = 0;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
  //如果经常使用size，可以在结构体中定义size，
  //然后初始化为0，就不用在使用while计算
  //这样就不用遍历，降低时间复杂度
}
//队头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
//队尾
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->tail);
  return pq->tail->data;
}
image.gif

Queue.h:

#pragma once
//队列（链式）的功能实现
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QNode;
//定义第二个结构体的原因是因为要方便队尾的插入，删除的管理
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  //size_t size;  //若经常使用，可在此增加一个计数
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//插入（进队）
void QueuePush(Queue* pq, QDataType x);
//删除（出队）
void QueuePop(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列大小
size_t QueueSize(Queue* pq);   //size_t即unsigned int，包含在头文件
//队头
QDataType QueueFront(Queue* pq);
//队尾
QDataType QueueBack(Queue* pq);
image.gif

二、队列（链式）的功能实现分析：

1.队列的概念及结构

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

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

image.gif编辑

2.队列的实现功能函数：

链式结构：表示队列

（1）初始化队列

//初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
image.gif

（2）销毁队列

//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
image.gif

（3）插入（进队）

//插入（进队）
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //开辟新结点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
    assert(pq->head == NULL);
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
image.gif

（4）删除（出队）

//删除（出队）
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head && pq->tail);
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
image.gif

（5）判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //return pq->head == NULL && pq->tail == NULL;
  return pq->head == NULL;
}
image.gif

（6）判断队列大小

//队列大小
//size_t即unsigned int，包含在头文件
size_t QueueSize(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  size_t size = 0;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
  //如果经常使用size，可以在结构体中定义size，
  //然后初始化为0，就不用在使用while计算
  //这样就不用遍历，降低时间复杂度
}
image.gif

（7）队头

//队头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
image.gif

（8）队尾

//队尾
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->tail);
  return pq->tail->data;
}
image.gif

销毁队列测试：

image.gif编辑

扩展了解：

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

image.gif编辑

image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                          ——By 作者：新晓·故知


关键词：
数据结构c语言
C语言数据结构
数据结构队列
C语言队列
队列数据结构
新晓故知
目录
相关文章
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
22 6
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
21 6
小徐在进步
|
2天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
16 5
小徐在进步
|
2天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
10 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
14 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
12 2
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
10 1
2的n次方_
|
4天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
10 0
【数据结构】栈和队列的深度探索，从实现到应用详解
cz游客
|
19天前
|
机器学习/深度学习 消息中间件 缓存
栈与队列的实现
栈与队列的实现
cz游客
35 0
這～悸ベ雨落憂殇
|
11月前
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
39 0

热门文章

最新文章

  • 1
    数据结构实践——队列数组
  • 2
    seastar的用户态协议栈
  • 3
    数据结构与算法(三) 线性表之双向链表
  • 4
    数据结构(二)_栈
  • 5
    动态规划-jobdu-1547：出入栈
  • 6
    数据结构之链表
  • 7
    你知道我想要的不只是算法与数据结构，还有Android高级架构学习开发指南
  • 8
    OpenJudge计算概论-排队游戏【这个用到了栈的思想】
  • 9
    单链表_JAVA描述《数据结构与算法分析》
  • 10
    图解Java数据结构之队列
  • 1
    【C 言专栏】C 语言与数据库的连接与操作
    169
  • 2
    【C 言专栏】优化 C 语言程序性能的策略
    142
  • 3
    【C 言专栏】C 语言中的位运算技巧
    128
  • 4
    【C 言专栏】C 语言与操作系统的交互
    68
  • 5
    【C 言专栏】基于 C 语言的嵌入式系统开发
    107
  • 6
    【C 言专栏】C 语言函数的高效编程技巧
    48
  • 7
    【C 言专栏】C 语言中的数据类型详解
    91
  • 8
    【C言专栏】C 语言实现动态内存分配
    74
  • 9
    【C 言专栏】C 语言文件操作的技巧与方法
    42
  • 10
    【C言专栏】递归算法在 C 语言中的应用
    52

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    对象存储 OSS 如何创建 bucket|学习笔记