【数据结构初阶第十节】队列(详解+附源码)

news/2025/3/15 22:13:17/

 好久不见。。。别不开心了,听听喜欢的歌吧

必须有为成功付出代价的决心,然后想办法付出这个代价。云边有个稻草人-CSDN博客

目录

一、概念和结构

二、队列的实现

Queue.h

Queue.c

 test.c

Relaxing Time!

————————————《有没有那么一首歌会让你想起我》————————————


这节课我们学习队列的概念和结构以及实现,需要提前具备前面顺序表和链表的相关知识,这样这节课就会变得非常简单!

一、概念和结构

概念: 只允许在⼀端进行插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
队列 进行 插⼊操作的⼀端称为队尾。
队列 进行 删除操作的⼀端称为队头。
队列底层结构选型 : 队列也可以数组和链表的结构实现,使⽤链表的结构实现更优⼀些,因为如果使⽤数组的结构,出队列在数组头上出数据,效率会⽐较低。
下图解释为什么用链表来实现队列

二、队列的实现

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//创建节点的结构
typedef int QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//创建队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;//队列里面有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QUDatatype x);//出队列
void QueuePop(Queue* pq);//取队头数据
QUDatatype QueueFront(Queue* pq);//取队尾数据
QUDatatype QueueBack(Queue* pq);//取队列有效元素个数
int QueueSize(Queue* pq);//销毁
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq,QUDatatype x)
{assert(pq);//申请一个新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}++pq->size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);//下面这样写也ok,return pq->phead == NULL && pq->ptail == NULL ;return pq->phead == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//若只有一个结点,防止ptail成为野指针if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除对头元素QueueNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;}--pq->size;
}//取队头数据
QUDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//取队列有效元素个数,时间复杂度为O(N),我们可以优化一下
//我们可以增加一个变量size去记录队列里面有效数据的个数然后直接返回
int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}//针对队列里面的结构进行销毁pq->phead = pq->ptail = NULL;pq->size = 0;
}

 test.c

#include"Queue.h"void test()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);/*QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);*/printf("head:%d\n", QueueFront(&pq));printf("back:%d\n", QueueBack(&pq));//两种 取队列里面有效数据的个数 方法printf("队列里面有效数据个数为:%d \n",QueueSize(&pq));printf("size:%d\n", QueueSize(&pq));printf("size:%d\n", pq.size);QueueDestroy(&pq);}int main()
{test();return 0;
}

实现队列需要注意的比较重要的点见下

  1. 队列里面有效数据的个数,如果用老方法套路实现时间复杂度为O(N),但是我们可以在队列里面重新定义一个结构,size来记录,每次入数据,出数据直接调整size即可,取有效数据个数的时候直接返回 size 就简单了很多。
  2. 队列销毁的时候,不要忘记最后把队列结构里面的phead和ptail指针置为NULL,size == 0。
  3. 我们定义了ptail指针,指向队尾,可以直接找到队尾入数据。

经过前几节顺序表,单链表,双链表,栈的学习,今天学习队列真是游刃有余呦,下一节是栈和队列算法题,期待一下啦~~

完——


Relaxing Time!

————————————《 有没有那么一首歌会让你想起我 ————————————

有没有一首歌会让你想起我_HENRY刘宪华_高音质在线试听_有没有一首歌会让你想起我歌词|歌曲下载_酷狗音乐

至此结束!

我是云边有个稻草人

期待与你的下一次相遇。。。


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

相关文章

计算机毕业设计PySpark+hive招聘推荐系统 职位用户画像推荐系统 招聘数据分析 招聘爬虫 数据仓库 Django Vue.js Hadoop

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

2025 年前端开发现状分析:卷疯了还是卷麻了?

一、前端现状&#xff1a;框架狂飙&#xff0c;开发者崩溃 如果你是个前端开发者&#xff0c;那么你大概率经历过这些场景&#xff1a; 早上打开 CSDN&#xff08;或者掘金&#xff0c;随便&#xff09;&#xff0c;发现又有新框架发布了&#xff0c;名字可能是 VueXNext.js 之…

腿足机器人之二- 运动控制概览

腿足机器人之二运动控制概览 高层运动规划MPCRL 中层逆运动学和逆动力学底层执行器控制传感器校正 上一篇博客是腿足机器人的骨架和关节的机械和电气组件&#xff0c;关节不仅需要通过机械设计实现复杂的运动能力&#xff0c;还必须通过电子组件和控制系统来精确控制这些运动。…

Docker的前世今生及安装与使用命令详解

在云原生时代&#xff0c;容器技术已经成为软件开发与部署的关键工具。其中&#xff0c;Docker 凭借其轻量、灵活和高效的特性迅速走红。本文将带你走进 Docker 的历史沿革&#xff0c;了解其从前世到今生的发展历程&#xff0c;并详细介绍如何安装 Docker 以及常用的操作命令。…

Django 创建表时 “__str__ ”方法的使用

在 Django 模型中&#xff0c;__str__ 方法是一个 Python 特殊方法&#xff08;也称为“魔术方法”&#xff09;&#xff0c;用于定义对象的字符串表示形式。它的作用是控制当对象被转换为字符串时&#xff0c;应该返回什么样的内容。 示例&#xff1a; 我在初学ModelForm时尝…

Ollama+DeepSeek+Open-WebUi

环境准备 Docker Ollama Open-WebUi Ollama 下载地址&#xff1a;Ollama docker安装ollama docker run -d \ -v /data/ollama/data:/root/.ollama \ -p 11434:11434 \ --name ollama ollama/ollama 下载模型 Ollama模型仓库 # 示例&#xff1a;安装deepseek-r1:7b doc…

SpringMVC重定向接口,参数暴露在url中解决方案!RedirectAttributes

OK&#xff0c;首先描述下业务场景&#xff0c;终端数量限制登录 1.首先访问项目login的get接口 2.输入账号密码点击登录后&#xff0c;会请求login的POST接口 3.后台对终端数量逻辑处理不允许登录跳回到登录页面 4.因代码原因需在后台进行多次重定向接口&#xff0c;最后跳…

说下JVM中一次完整的GC流程?

大家好&#xff0c;我是锋哥。今天分享关于【说下JVM中一次完整的GC流程?】面试题。希望对大家有帮助&#xff1b; 说下JVM中一次完整的GC流程? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 JVM中的一次完整的垃圾回收&#xff08;GC&#xff09;流程可以概括为…