【脚踢数据结构】队列（顺序和链式）

news/2024/10/30 19:22:56/
  • (꒪ꇴ꒪ )，Hello我是祐言QAQ
  • 我的博客主页：C/C++语言,Linux基础,ARM开发板，软件配置等领域博主🌍
  • 快上🚘，一起学习，让我们成为一个强大的攻城狮！
  • 送给自己和读者的一句鸡汤🤔：集中起来的意志可以击穿顽石!
  • 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏


        在我们的日常生活中，队列是一个非常常见的现象。无论是在商店结账，还是在公交站等车，我们都在使用队列。在计算机科学中，队列也是一个重要的数据结构，用于处理和组织数据。在这篇文章中，我们将详细探讨队列的定义、操作、以及如何用C语言实现队列。

一、队列的定义


        队列（Queue）是一种特殊类型的线性数据结构，它遵循特定的操作规则，即遵循“先进先出”（FIFO，First-In-First-Out）原则。这意味着在队列中，首先加入的元素将会首先被移除，最后加入的元素将会最后被移除。

         当我们想存入1时，先移动front（队头）然后再写入数据1，拿数据也是一样，但务必保证先移动rear（队尾），再拿出数据，否则将会错位导致出错。

二、顺序队列

      1.  队列结构体定义


        首先需要定义一个顺序队列，我们可以使用结构体来定义一个队列，它包含一个数组（用于存储队列的数据）和三个整数（用于表示队列长度、队首和队尾的位置）。


typedef int Datatype;//队列的结构体定义
typedef struct Quene
{Datatype *q;	//用来存放队列的数据int size;		//队列的长度int front;		//队头int rear;		//队尾
}queue;

    2.  初始化队列


        接下来，我们需要初始化队列。在初始化时，我们将队首和队尾都设置为0，表示队列为空。

//初始化一个队列
queue *init_queue(int size)
{queue *que = malloc(sizeof(queue));if (que!=NULL){que->q = calloc(size, sizeof(Datatype));que->size = size;que->front = 0;que->rear = 0;}return que;
}

    3.  队空和队满


        如果我们想要实现入队和出队操作，我们需要先考虑队列可能会溢出或下溢的情况，因此我们需要判断是否队空或队满。

//队空判断
bool isempty_queue(queue *q)
{return (q->rear == q->front);
}//队满判断
bool isfull_queue(queue *q)
{return ((q->rear+1)%q->size == q->front);
}

    4.  入队和出队

//入队
bool en_queue(queue *que, Datatype data)
{if (isfull_queue(que)){return false;}//先挪rearque->rear = (que->rear+1)%(que->size);//再入数据que->q[que->rear] = data;return true;
}//出队
bool de_queue(queue *que, Datatype *data)
{if (isempty_queue(que)){return false;}//先挪frontque->front = (que->front+1)%(que->size);//再取数据*data = que->q[que->front];return true;
}


        队列是计算机科学中的一个基础概念，它在许多场景中都有应用，如操作系统的任务调度，网络的数据包处理等。理解队列的工作原理并能够实现队列，对于学习和理解计算机科学的其他概念是非常有帮助的。希望这篇文章能帮助你理解和实现队列。

        下面是一个简单的顺序队列举例，实现：输入正整数，添加员工信息，入队，用这个正整数表示员工号；输入负整数，出队（队首），显示该员工的所有信息；否则就退出。

        员工信息：工号、姓名、工资

        完整源码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define SIZE 1024
typedef struct people
{int number;		//工号char name[20];	//姓名int money;		//工资
}Datatype;//队列的结构体定义
typedef struct Quene
{Datatype *q;	//用来存放队列的数据int size;		//队列的长度int front;		//队头int rear;		//队尾
}queue;//初始化一个队列
queue *init_queue(int size)
{queue *que = malloc(sizeof(queue));if (que!=NULL){que->q = calloc(size, sizeof(Datatype));que->size = size;que->front = 0;que->rear = 0;}return que;
}//队空判断
bool isempty_queue(queue *q)
{return (q->rear == q->front);
}//队满判断
bool isfull_queue(queue *q)
{return ((q->rear+1)%q->size == q->front);
}//入队
bool en_queue(queue *que, Datatype data)
{if (isfull_queue(que)){return false;}//先挪rearque->rear = (que->rear+1)%(que->size);//再入数据que->q[que->rear] = data;return true;
}//出队
bool de_queue(queue *que, Datatype *data)
{if (isempty_queue(que)){return false;}//先挪frontque->front = (que->front+1)%(que->size);//再取数据*data = que->q[que->front];return true;
}// 添加信息
void init_info(Datatype *data,int n)
{data->number = n;printf("请输入工人信息\n");while(getchar() != '\n');printf("姓名：");scanf("%s", data->name);printf("工资：");scanf("%d", &data->money);
}int main(int argc, char const *argv[]) {queue *q = init_queue(SIZE);int n;Datatype data;while (1) {printf("请输入一个正整数或负数\n");scanf("%d", &n);if (n > 0){init_info(&data, n);en_queue(q, data);continue;}else if(n < 0){Datatype d;if (de_queue(q, &d)) {printf("工号：%d，姓名：%s，工资：%d\n", d.number, d.name, d.money);} else {printf("队列已空，无法出队。\n");}}else{return -1;}}free(q->q);free(q);return 0;
}

三、链式队列

        链式队列（Linked Queue）是一种使用链表来实现的队列数据结构。与顺序队列不同，链式队列的元素并不直接存储在数组中，而是通过链表节点来连接。

        并且 由于使用链表实现，链式队列的大小可以根据需要动态分配和释放内存，避免了固定数组大小可能带来的限制。因此就没有是否队满问题。

1.结构体定义

typedef int Datatype;typedef struct Node
{Datatype data;struct Node *next;
}node;typedef struct List_queue
{node *rear;		//队尾指针node *front;	//队头指针int size;		//链式队列的长度(实际的元素的个数)
}L_q;

2.创建新节点和判断队空

//创建新节点
node *create_node(Datatype data)
{node *new = malloc(sizeof(node));if (new != NULL){new->data = data;new->next = NULL;}return new;
}
//链式队列是否为空
bool isempty_list_queue(L_q *q)
{return (q->size == 0);
}

3.初始化队列

//初始化链式队列
L_q *init_list_queue()
{L_q *q = malloc(sizeof(L_q));if (q!=NULL){q->rear = NULL;q->front = NULL;q->size = 0;}return q;
}

3.入队

        入队操作在链表的末尾添加一个新节点，同时更新队尾指针。

//入队
bool en_list_queue(L_q *q, Datatype data)
{//先要将数据创建新节点node *new = create_node(data);if (new==NULL){return false;}//如果是第一次入队，new节点既是队尾，也是队头if (isempty_list_queue(q)){q->rear = new;q->front = new;}else    //不是第一次入队{//先将尾部节点的next指向new节点q->rear->next = new;//尾部节点要变成新节点newq->rear = new;}//队的元素个数要+1q->size++;return true;
}

4.出队

         出队操作移除链表的第一个节点，同时更新队头指针。

//出队
bool de_list_queue(L_q *q, Datatype *data)
{if (isempty_list_queue(q)){return false;}else if(q->size == 1)//只有一个数据的时候{q->rear = NULL;}//在链表不为空的情况下,先拿队头的数据*data = q->front->data;//将队头指向下一个节点q->front = q->front->next;//链式队列的元素个数-1q->size--;return true;
}

 5.遍历

//遍历
void display(L_q *q)
{if (q->front == NULL){return ;}node *p = q->front;while(p->next != NULL){printf("%d ", p->data);p = p->next;}printf("%d\n", p->data);
}

        简单示例：当我们输入正数时，入队并遍历整个队列；当我们输入负数时，出队一个元素，并再次遍历队列；输入0时退出。

int main(int argc, char const *argv[])
{L_q *q = init_list_queue();int num;Datatype data;while(1){scanf("%d", &num);if(num > 0){en_list_queue(q, num);	display(q);	}else if(num < 0){de_list_queue(q, &data);display(q);	}else{break;}}return 0;
}

四、结语

        
        队列作为一种基本的数据结构，在我们的编程生涯中扮演着重要的角色。希望这篇文章提供了一个清晰、详细的队列概述，帮助你理解队列的基本概念和操作，以及如何用C语言实现队列。

        选择顺序队列还是链式队列取决于实际应用的需求。如果你需要一个固定大小的队列，可以考虑使用顺序队列。如果你希望队列大小能够根据需要进行动态调整，那么链式队列更适合。在大多数情况下，链式队列具有更好的扩展性和灵活性。

        更多C语言、Linux系统、ARM板实战和数据结构相关文章，关注专栏：

   手撕C语言

            玩转linux

                    脚踢数据结构

                            6818（ARM）开发板实战

📢写在最后

  • 今天的分享就到这啦~
  • 觉得博主写的还不错的烦劳 一键三连喔~
  • 🎉感谢关注🎉

http://www.ppmy.cn/news/1026937.html

相关文章

JavaWeb 中对 HTTP 协议的学习

JavaWeb 中对 HTTP 协议的学习

HTTP1 Web概述1.1 Web和JavaWeb的概念1.2 JavaWeb技术栈1.2.1 B/S架构1.2.2 静态资源1.2.3 动态资源1.2.4 数据库1.2.5 HTTP协议1.2.6 Web服务器 1.3 Web核心 2 HTTP2.1 简介2.2 请求数据格式2.2.1 格式介绍2.2.2 实例演示 2.3 响应数据格式2.3.1 格式介绍2.3.2 响应状态码2.3.…
阅读更多...
QT之UDP通信

QT之UDP通信

QT之UDP通信 UDP不分客户端口服务器，只需要使用一个类QUdpSocket QT += core gui networkgreaterThan(QT_MAJOR_VERSION, 4): QT += widgetsTARGET = udp TEMPLATE = app# The following define makes your compiler emit warnings if you use # any feature of Qt …
阅读更多...
【CSS】CSS 布局——弹性盒子

【CSS】CSS 布局——弹性盒子

Flexbox 是一种强大的布局系统&#xff0c;旨在更轻松地使用 CSS 创建复杂的布局。 它特别适用于构建响应式设计和在容器内分配空间&#xff0c;即使项目的大小是未知的或动态的。Flexbox 通常用于将元素排列成一行或一列&#xff0c;并提供一组属性来控制 flex 容器内的项目行…
阅读更多...
Arduino ESP32 v2 使用记录：开发环境搭建

Arduino ESP32 v2 使用记录：开发环境搭建

文章目录 目的开发环境搭建程序下载测试使用VS Code进行开发批量烧录固件到模块中总结 目的 在之前的文章 《使用Arduino开发ESP32&#xff08;01&#xff09;&#xff1a;开发环境搭建》 中介绍了使用Arduino开发ESP32的开发环境搭建内容&#xff0c;只不过当时的 Arduino co…
阅读更多...
模板复用和文章详情页（Go搭建qiucode.cn 之七）

模板复用和文章详情页（Go搭建qiucode.cn 之七）

模板复用其实就是动态内容驱动着部分变化的区域，公共区域是整个网站页面都在共用的内容，这便是模板复用的妙处。 模板复用 作为服务端编程语言的Golang，在web模板渲染引擎上当然也不逊色于其他同类型的服务端语言，它同样也有属于自己的那一套模板渲染引擎。 更为确切的叫…
阅读更多...
在阿里云Linux服务器上部署MySQL数据库流程

在阿里云Linux服务器上部署MySQL数据库流程

阿里云百科分享在阿里云Linux服务器上部署MySQL数据库流程&#xff0c;MySQL是一个关系型数据库管理系统&#xff0c;常用于LAMP和LNMP等网站场景中。本教程介绍如何在Linux系统ECS实例上安装、配置以及远程访问MySQL数据库。 目录 背景信息 Alibaba Cloud Linux 2/3、CentO…
阅读更多...
VS+QT+Opencv使用YOLOv4对视频流进行目标检测

VS+QT+Opencv使用YOLOv4对视频流进行目标检测

对单张图像的检测&#xff0c;请参考&#xff1a;https://blog.csdn.net/qq_45445740/article/details/109659938 #include <fstream> #include <sstream> #include <iostream> #include <opencv2/dnn.hpp> #include <opencv2/imgproc.hpp> #inc…
阅读更多...
大数据课程I2——Kafka的架构

大数据课程I2——Kafka的架构

文章作者邮箱&#xff1a;yugongshiyesina.cn 地址&#xff1a;广东惠州 ▲ 本章节目的 ⚪ 掌握Kafka的架构&#xff1b; ⚪ 掌握Kafka的Topic与Partition&#xff1b; 一、Kafka核心概念及操作 1. producer生产者&#xff0c;可以是一个测试线程&#xff0c;也…
阅读更多...
最新文章

Copyright @ 2022~2023