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

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

2022-11-27 80
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜队列（链式）＞《数据结构(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语言数据结构
队列数据结构
新晓故知
目录
相关文章
ephemerals__
|
5天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
64 9
aliyun3611036241
|
20天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
aliyun3611036241
54 4
ephemerals__
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
43 16
ephemerals__
|
4天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
32 8
ephemerals__
|
7天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
32 4
ephemerals__
|
8天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
32 3
aliyun1622584902-46568
|
9天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
aliyun1622584902-46568
24 2
肾透侧视攻城狮
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
13 1
ephemerals__
|
7天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
24 0
程序员大阳
|
C语言
C语言队列实现
一，简介 开发环境是VC6.0，实现了一个基于C语言的队列。 主要功能，入队、出队、显示当前队列元素。
程序员大阳
126 0