数据结构之队列详解（包含例题）

一、队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

二、模拟实现顺序队列

我们可以用单链表模拟实现顺序队列。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部（对应单链表的尾插），而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素（对应单链表的头删）。

对应的接口

注意又提供一种避免使用二级指针的方法，创建一个结构体变量，里面存储结点，当我们想要改变结构体里面的值，我们就用一级指针即可。

typedef int QDataType;
typedef struct QueueNode
{
	//用单链表模拟实现队列
	struct QueueNode* next;
	QDataType data;
}QNode;

//新的避免二级指针的结构体
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int sz;
}Que;

void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueeuPop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

队列的初始化：

void QueueInit(Que* pq)
{
	assert(pq);
	pq->sz = 0;
	pq->head = pq->tail = NULL;
}

队列的销毁

注意free过后，也要指向空

void QueueDestroy(Que* pq)
{
	assert(pq);
	while (pq->sz > 0)
	{
		QNode* cur = pq->head->next;
		free(pq->head);
		pq->head = cur;
		pq->sz--;
	}
	pq->tail = pq->head = NULL;
}

队列的插入数据

也就是单链表的尾插，同时也要注意当队列为空时的特殊情况。

void QueuePush(Que* pq,QDataType x)
{
	//类似于尾插
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
		pq->sz++;
	}
	else
	{
		pq->sz++;
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

队列的删除数据

也就是单链表的头删，同时也要注意只剩下一个结点删除后，尾结点指向空的情况


void QueeuPop(Que* pq)
{
	assert(pq);
	assert(pq->sz > 0);
	//头删
	//单独判断只剩下一个结点，头删后tail是野指针的情况
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
		pq->sz--;
	}
	else
	{
		QNode* cur = pq->head;
		pq->head = pq->head->next;
		free(cur);
		pq->sz--;
	}
	
}

返回队列头数据

QDataType QueueFront(Que* pq)
{
	assert(pq);
	//assert(pq->head);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

返回队列尾数据

QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

判断队列是否为空

bool QueueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}

返回队列的数据个数

int QueueSize(Que* pq)
{
	assert(pq);
	//assert(pq->head);
	return pq->sz;
}

三、模拟实现循环队列

622. 设计循环队列 - 力扣（LeetCode）

这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

注意本题结构较为复杂，必须要画图进行解决，这样就容易考虑到特殊情况，不容易出错。

本题用数组实现较为简单，如果用单链表实现，那么rear尾结点的前一个不好寻找。

那数组如何实现循环呢？

数组实现循环并不像单链表那样有一个next指针指向头结点，如果已经走向尾部，可以直接让头部的值等于尾部想要的值。

//如何用数组实现循环？
typedef struct {
    int* a;
    int front;
    int rear;
    int num;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //用k+1个数组空间，便于判断空和满的情况。
    cur->a = (int*)malloc(sizeof(int)*(k+1));
    cur->front = 0;
    cur->rear = 0;
    cur->num = k;
    return cur;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front == obj->rear)
        return true;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //两种情况都要考虑到！
    if(obj->front-obj->rear == 1 || obj->rear-obj->front == obj->num)
        return true;
    else
        return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判断是否已经满
    if(myCircularQueueIsFull(obj) == true)
        return false;
    //假设rear在队列的尾部
    if(obj->rear == obj->num)
    {
        obj->a[obj->rear] = value;
        obj->rear = 0;
    }
    else
    {
        obj->a[obj->rear] = value;
        obj->rear++;
    }
    //obj->a[obj->rear] = value;
    //obj->rear++;
    //obj->rear %= (obj->num+1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判断是否已经空了
    if(myCircularQueueIsEmpty(obj) == true)
    {
        return false;
    }
    //假设front在队列的尾部
    if(obj->front == obj->num)
        obj->front = 0;
    else
        obj->front++;
    //++obj->front;
    //obj->front %= (obj->num+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj) == true)
        return -1;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    //注意队尾的rear比数据提前一位数，所以是rear-1
    //但要考虑rear-1的情况
    if(myCircularQueueIsEmpty(obj) == true)
        return -1;
    if(obj->rear == 0)
    {
        //需要再创建一个临时变量，不能改变rear的值
        int tmp = obj->num;
        return obj->a[tmp];
    }
    // else
    //     return  obj->a[(obj->rear+obj->num)%(obj->num+1)];
    return obj->a[obj->rear-1];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

四、用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

本题要求用两个队列实现栈，两个队列我们就可以互相倒数据，来满足题目对栈的需求！

思路：

入队列：

入不为空的队列

出队列：

利用队列的性质将前n-1个数据放入另一个空的队列中，删除剩下一个数据，这样就完成栈的pop操作！

代码：

typedef struct {
    Que q1;
    Que q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* cur = (MyStack*)malloc(sizeof(MyStack));
    //不能忘记初始化
    QueueInit(&cur->q1);
    QueueInit(&cur->q2);
    return cur;
}

void myStackPush(MyStack* obj, int x) {
    //push到不为空的的队列中
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //先假设q1不为空，q2为空
    Que* empty = &obj->q1;
    Que* nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //如果假设失败，相反
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    while(QueueSize(nonEmpty)>1)
    {
        //开始用函数进行捯数据
        //从前往后的顺序是根据队列pop的顺序定的
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueBack(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    Que* empty = &obj->q1;
    Que* nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //如果假设失败，相反
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    return QueueBack(nonEmpty);
}

bool myStackEmpty(MyStack* obj) {
    //判断两个队列
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    //先对两个队列中的链表进行free
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

五、用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

思路：

本题与上一题用队列实现栈有所差别，可以直接区分push栈和pop栈，如果pop栈为空，就将push栈全部捯到pop栈！

代码：

typedef struct 
{
	ST push;
	ST pop;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* cur = (MyQueue*)malloc(sizeof(MyQueue));
	SLInit(&cur->push);
	SLInit(&cur->pop);
	return cur;
}

void myQueuePush(MyQueue* obj, int x) {
	STPush(&obj->push,x);
}

int myQueuePop(MyQueue* obj) {
	
	int ret = myQueuePeek(obj);
	STPop(&obj->pop);
	return ret;
}

int myQueuePeek(MyQueue* obj) {
	//出栈只能从后往前出
	//如果pop栈为空，就将push栈全部捯到pop栈！
	if(STEmpty(&obj->pop))
	{
		while(!STEmpty(&obj->push))
		{
			STPush(&obj->pop,STTop(&obj->push));
			STPop(&obj->push);
		}
	}
	int ret = STTop(&obj->pop);
	return ret;
}

bool myQueueEmpty(MyQueue* obj) {
	//用函数求解
	return STEmpty(&obj->push) && STEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
	SLDestroy(&obj->pop);
	SLDestroy(&obj->push);
	free(obj);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/78990.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

亿发创新中医药信息化解决方案，自动化煎煮＋调剂，打造智能中药房

亿发创新中医药信息化解决方案，自动化煎煮＋调剂，打造智能中药房

传统中医药行业逐步复兴，同时互联网科技和人工智能等信息科技助力中医药行业逐步实现数字化转型。利用互联网、物联网、大数据等科技，实现现代科学与传统中医药的结合，提供智能配方颗粒调配系统、中药自动化调剂系统、中药煎配智能管理系统、…
阅读更多...
【Docker报错】docker拉取镜像时报错：no such host

【Docker报错】docker拉取镜像时报错：no such host

报错信息 [rootSoft soft]# docker pull mysql Using default tag: latest Error response from daemon: Head "https://registry-1.docker.io/v2/library/mysql/manifests/latest": dial tcp: lookup registry-1.docker.io on 192.168.80.2:53: no such host解决方法…
阅读更多...
Leetcode-每日一题【剑指 Offer 28. 对称的二叉树】

Leetcode-每日一题【剑指 Offer 28. 对称的二叉树】

题目 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称…
阅读更多...
Android 网络编程-网络请求

Android 网络编程-网络请求

Android 网络编程-网络请求 文章目录 Android 网络编程-网络请求一、主要内容二、开发网络请求前的基本准备1、查看需要请求的网址是否有效（1）通过网页在线验证（2）使用专用window网咯请求工具（3）编写app代码…
阅读更多...
多维时序 | MATLAB实现WOA-CNN-BiGRU-Attention多变量时间序列预测

多维时序 | MATLAB实现WOA-CNN-BiGRU-Attention多变量时间序列预测

多维时序 | MATLAB实现WOA-CNN-BiGRU-Attention多变量时间序列预测 目录 多维时序 | MATLAB实现WOA-CNN-BiGRU-Attention多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现WOA-CNN-BiGRU-Attention多变量时间序列预测 1.程…
阅读更多...
LVS负载均衡集群-NAT模式部署

LVS负载均衡集群-NAT模式部署

集群 集群：将多台主机作为一个整体，然后对外提供相同的服务 集群使用场景：高并发的场景 集群的分类 1.负载均衡器集群 减少响应延迟，提高并发处理的能力 2，高可用集群 增强系统的稳定性可靠性&…
阅读更多...
LeetCode 141.环形链表

LeetCode 141.环形链表

文章目录 💡题目分析💡解题思路🔔接口源码💡深度思考❓思考1❓思考2 题目链接👉 LeetCode 141.环形链表👈 💡题目分析 给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中…
阅读更多...
Echarts地图-全国主要城市空气质量【亲测有效】

Echarts地图-全国主要城市空气质量【亲测有效】

参考： Echarts官网实例 效果： 需要通过ajax的方式获取json数据: {"code":100,"msg":"处理成功！","extend":{"items":[{"name":"三亚","value":52},{&qu…
阅读更多...
适合程序员的DB性能测试工具 JMeter

适合程序员的DB性能测试工具 JMeter

背景 1、想要一款既要能压数到mysql，又要能压数到postGre，还要能压数到oracle的自动化工具 2、能够很容易编写insert sql（因为需要指定表和指定字段类型压数据），然后点击运行按钮后，就能直接运行&#xff…
阅读更多...
精彩回顾 | 迪捷软件出席2023ATC汽车电子与软件技术周

精彩回顾 | 迪捷软件出席2023ATC汽车电子与软件技术周

2023年8月18日，由ATC汽车技术会议主办，上海市集成电路行业协会支持的“2023ATC汽车电子与软件技术周”在上海市圆满落幕。迪捷软件上海参展之行圆满收官。 ▲开幕式 本次峰会汇聚了整车厂、汽车零部件集团、软硬件方案提供商、软件工具供应商、软件测试…
阅读更多...
利用console提高写bug的效率

利用console提高写bug的效率

前端面试题库 （面试必备） 推荐：★★★★★ 地址：前端面试题库 自从入坑前端后，日常写bug就没离开过console。 要说用得多，不如说是console.log用得多，console.warn和console.erro…
阅读更多...
shell脚本基础

shell脚本基础

目录 前言 一、概述 （一）、shell脚本基础概念 （二）、shell的类型 二、Shell变量 （一）、组成 1.变量名 2.变量值 （二）、类型 1.系统内置变量（环境变量） 2.自定…
阅读更多...
Spring-3-Spring AOP概念全面解析

Spring-3-Spring AOP概念全面解析

今日目标 能够理解AOP的作用 能够完成AOP的入门案例 能够理解AOP的工作流程 能够说出AOP的五种通知类型 一、AOP 1 AOP简介 思考：什么是AOP,AOP的作用是什么？ 1.1 AOP简介和作用【理解】 AOP(Aspect Oriented Programming)面向切面编程，一…
阅读更多...
c51单片机串口通信（中断方式接收数据）（单片机--单片机通信）示例代码 附proteus图

c51单片机串口通信（中断方式接收数据）（单片机--单片机通信）示例代码 附proteus图

单片机一般采用中断方式接受数据，这样便于及时处理 #include "reg51.h" #include "myheader.h" #define uchar unsigned char int szc[10]{0xc0,0xf9,0xa4,0xb0,0x99,0x92,0x82,0xf8,0x80,0x90}; int bufferc[6]{0}; int sza[6]{0x01,0x02,0x0…
阅读更多...
接口测试及接口抓包常用测试工具和方法？

接口测试及接口抓包常用测试工具和方法？

作为测试领域中不可或缺的一环，接口测试和抓包技术在软件开发过程中扮演着至关重要的角色。不论你是新手还是有一些经验的小伙伴，本篇文章都会为你详细介绍接口测试的基本概念、常用测试工具和实际操作技巧，让你轻松掌握这一技能。 接口测试…
阅读更多...
MySQL之索引和事务

MySQL之索引和事务

什么是索引索引怎么用索引的原理事务使用事务事务特性MySQL隔离级别 什么是索引 索引包含数据表所有记录的引用指针；你可以对某一列或者多列创建索引和指定不同的类型（唯一索引、主键索引、普通索引等不同类型；他们底层实现也是不同的&#…
阅读更多...
【SpringBoot】中的ApplicationRunner接口 和 CommandLineRunner接口

【SpringBoot】中的ApplicationRunner接口 和 CommandLineRunner接口

1. ApplicationRunner接口 用法： 类型： 接口 方法： 只定义了一个run方法 使用场景： springBoot项目启动时，若想在启动之后直接执行某一段代码，就可以用 ApplicationRunner这个接口，并实现接口…
阅读更多...
线程池中的常见面试题

线程池中的常见面试题

目录 1. 线程池相比于线程有什么优点 2. 线程池的参数有哪些 3. 线程工厂有什么用 4. 说一下线程的优先级 5. 说一下线程池的执行流程 6. 线程池的拒绝策略有哪些 7. 如何实现自定义拒绝策略 8. 如何判断线程池中的任务是否执行完成 1. 线程池相比于线程有什么优点 有…
阅读更多...
Rancher管理K8S

Rancher管理K8S

1 介绍 Rancher是一个开源的企业级多集群Kubernetes管理平台，实现了Kubernetes集群在混合云本地数据中心的集中部署与管理，以确保集群的安全性，加速企业数字化转型。Rancher 1.0版本在2016年就已发布，时至今日，Ranche…
阅读更多...
【宝藏应用】AI绘图网站

【宝藏应用】AI绘图网站

序言 这是一个通过AI模型进行绘制图片的网站。 有图有真相 这些是我在上面找的AI生成的图片，感觉怎么样呢？是不是看起来接近真人的精修图片了？ 地址 链接: LiblibAI
阅读更多...
最新文章

Copyright @ 2022~2023