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

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

2022-11-27 199
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜队列（链式）＞《数据结构(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语言队列
新晓故知
目录
相关文章
大数据文摘
|
8月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
281 1
土木林森
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
585 1
游客beejssedmb2sq
|
6月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
168 0
RossyYan
|
11月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
556 77
蓝易云
|
10月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
257 11
羑悻的小杀马特
|
10月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
187 14
RossyYan
|
11月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
461 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
羑悻的小杀马特
|
10月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
314 13
羑悻的小杀马特
|
11月前
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
179 13
RossyYan
|
11月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
249 9

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    数据结构与算法（六）：图结构
  • 4
    包含min函数的栈和两个栈实现一个队列
  • 5
    数据结构与算法——字符串
  • 6
    《大话数据结构》 查找 以及一个简单的哈希表例子
  • 7
    栈的压入、弹出序列
  • 8
    数据结构之树
  • 9
    Redis部分数据结构方法小结
  • 10
    小菜一步一步学数据结构之(一)基本概念和术语
  • 1
    c语言文件操作
    173
  • 2
    `scanf`是C语言中用于按格式读取标准输入的函数
    1038
  • 3
    基于标准C语言实现的跨平台Modbus协议库
    305
  • 4
    C语言常见概念
    312
  • 5
    C语言中的字符、字符串及内存操作函数详细讲解
    334
  • 6
    比较C++的内存分配与管理方式new/delete与C语言中的malloc/realloc/calloc/free。
    221
  • 7
    c语言的文件操作与文件缓冲区
    175
  • 8
    c语言——二叉树
    163
  • 9
    C语言分支和循环语句
    152
  • 10
    C语言与操作系统交互探秘
    277

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    安全设备篇——WAF