栈和队列(二) 队列操作详解及栈与队列的相互实现

文章目录

  • 四、队列
    • 1、什么是队列
    • 2、队列的基本操作
      • Queue.h
      • Queue.c
        • 初始化队列
        • 队尾入队列
        • 队头出队列
        • 获取队列头部元素
        • 获取队列队尾元素
        • 获取队列中有效元素个数
        • 检测队列是否为空,如果为空返回非零结果,如果非空返回0
        • 销毁队列
  • 五、设计循环队列
  • 六、栈与队列的相互实现
    • 1、用栈实现队列
    • 2、用队列实现栈

栈操作实现:栈和队列(一) 栈操作详解

在这里插入图片描述

四、队列

1、什么是队列

队列就像是高速公路上的一个隧道一样,所有的车辆只允许从入口驶入,从出口驶出,先进先出,不允许逆行。

队列(queue)是一种线性数据结构,队列的元素只能先入先出(First In First Out,简称FIFO)。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

在这里插入图片描述

2、队列的基本操作

利用单链表来实现队列的基本操作

在这里插入图片描述

代码结构设计:

  • Queue.h: 存放队列结构及需要用到的头文件,函数声明等
  • Queue.c: 各种操作函数的具体实现

Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//方便修改数据类型
typedef int QDataType;// 链式结构:表示队列 
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;//队头QNode* rear;//队尾
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"

初始化队列

void QueueInit(Queue* q)
{assert(q);q->front = NULL;q->rear = NULL;
}

队尾入队列

void QueuePush(Queue* q, QDataType data)
{assert(q);//创建一个节点放数据QNode* newNode=(QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->data = data;newNode->next = NULL;//判断是否是第一个入队元素if (q->rear == NULL){q->front = q->rear = newNode;}else{q->rear->next= newNode;q->rear = newNode;}
}

在这里插入图片描述

队头出队列

void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//判断是否只有一个元素if (q->front->next == NULL){free(q->front);q->front = q->rear = NULL;}else{QNode* del = q->front;q->front = q->front->next;free(del);}
}

在这里插入图片描述

获取队列头部元素

front是队头节点,它的数据便是队头元素

QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}

获取队列队尾元素

rear是队尾节点,它的数据便是队尾元素

QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}

获取队列中有效元素个数

遍历一遍链表就能得到有效元素个数,也可以直接给队列的结构里加上一个size

int QueueSize(Queue* q)
{assert(q);QNode* cur = q->front;int size = 0;while (cur){cur = cur->next;size++;}return size;
}

检测队列是否为空,如果为空返回非零结果,如果非空返回0

int QueueEmpty(Queue* q)
{assert(q);//队头节点为空说明队列为空return q->front == NULL;
}

销毁队列

void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* curNext = cur->next;free(cur);cur = curNext;}q->front = q->rear = NULL;
}

五、设计循环队列

循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

设计循环队列实现以下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

创建队列时多开辟一个空间来区分空和满
如下是一个队列长度k=4的循环队列:
在这里插入图片描述
用数组实现

//循环队列结构
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;
//初始化创建
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开一个空间方便区分空和满obj->a=(int*)malloc(sizeof(int)*(k+1));obj->front=0;obj->rear=0;obj->k=k;return obj;
}
//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//当队头和队尾相等时队列为空return obj->front==obj->rear;
}
//判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}

在这里插入图片描述

//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//判断满了没if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->rear]=value;obj->rear++;//特殊情况(obj->rear)%=(obj->k+1);return true;
}

在这里插入图片描述

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是不是空的if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;特殊情况(obj->front)%=(obj->k+1);return true;
}

在这里插入图片描述

//获取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}
//获取队尾元素
//rear是队尾元素下一个元素的下标,所以队尾元素的下标为rear-1
//但当rear等于0的时候队尾元素下标为k,需要特殊处理
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}// if(obj->rear==0)// {//     return obj->a[obj->k];// }else// {//     return obj->a[obj->rear-1];// }return obj->a[((obj->rear)+(obj->k))%(obj->k+1)];
}

在这里插入图片描述

//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

六、栈与队列的相互实现

1、用栈实现队列

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

思路:

用两个栈实现先入先出队列,当有元素入队时,就是在pushst入栈

在这里插入图片描述
当出队时,将pushst中元素依次出栈放进popst中,然后对popst进行出栈操作

在这里插入图片描述

代码实现:

用的是前面自己实现的栈来实现的

typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}int myQueuePop(MyQueue* obj) {int ret=myQueuePeek(obj);STPop(&obj->popst);return ret;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}

2、用队列实现栈

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

思路:

用两个队列q1和q2来实现一个后入先出的栈

入栈:放进不为空的那个队列
在这里插入图片描述

出栈:不为空队列的前n-1个出队列插入空队列,删除剩下的一个即可

在这里插入图片描述
代码实现:

用的是前面自己实现的队列来实现的

typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* p=(MyStack*)malloc(sizeof(MyStack));QueueInit(&p->q1);QueueInit(&p->q2);return p;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* empty=&obj->q1;Queue* noEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noEmpty=&obj->q1;}while(QueueSize(noEmpty)>1){QueuePush(empty,QueueFront(noEmpty));QueuePop(noEmpty);}int top=QueueFront(noEmpty);QueuePop(noEmpty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux的开胃小菜】Linux系统安装后初始化配置操作

我们刚接手一台刚安装好服务器系统之后&#xff0c;可以对系统进行一些基础优化&#xff1a; 常规设定&#xff1a; centos: 1.关闭 iptables 2.关闭 selinux 3.设定 ChronyUbuntu: 4. /etc/security/limits.conf 5. /etc/sysctl.conf1.首先使用国内阿里云的yum源&#xff08…

Electron学习1 安装环境与第一个程序

Electron学习1 安装环境与第一个程序 一、 Electron 简介二、安装 nvm三、安装nodejs四、安装nrm五、安装electron1. npm 初始化2. 创建 package.json3. 安装electron4. 创建一个页面5. 创建文件main.js6. 创建预加载器文件 preload.js7. 启动程序 六、打包 一、 Electron 简介…

windows .gitignore 加入文件名后 依然可以从git status中看到文件问题

最近在学git&#xff0c;对着b站的视频操作&#xff0c;结果很简单的添加.gitignore文件操作&#xff0c;up主的正常隐藏&#xff0c;我的却一直出问题。 百思不得其解&#xff0c;网上各种啥啥啥清缓存都没讲到点上。 最后发现是.gitignore文件有问题&#xff0c;windows默认…

uniapp 实现滑动视图切换 顶部滚动导航栏

无论小程序的时候一般有这个功能,在页面处于首页时候,滑动视图,切换视图顶部滚动导航也跟着切换 1.想要实现这个功能就需要实现顶部导航栏,首先实现顶部滚导航栏 点击高亮颜色显示 模板代码 <scroll-view scroll-x"true" class"scroll-content" > …

IDEA离线安装插件

一、背景 有时&#xff0c;在ideal中我们无法获取到插件&#xff0c;可能是因为内网或者无法访问插件库等原因&#xff0c;此时我们需要离线安装插件 IDEA离线仓库&#xff1a;https://plugins.jetbrains.com/ 二、步骤 2.1 下载插件&#xff1a;https://plugins.jetbrains.…

护网行动 | AD360 在网络安全中的重要作用

随着数字化时代的来临&#xff0c;网络已经成为了人们生活和工作中不可或缺的一部分。然而&#xff0c;随之而来的是网络安全问题日益突出。为了应对这些安全威胁&#xff0c;护网行动应运而生&#xff0c;其中AD360在保障网络安全方面扮演着至关重要的角色。 AD360是一个集成的…

nginx 负载均衡

1.环境准备 我使用的说centos7的系统 1.20版本的nginx 另外还有3台虚拟机 主机&#xff1a;192.168.163.142 两台服务器&#xff1a;服务器A--192.168.163.140 服务器B---192.168.163.141 2.配置服务器A和B 找到nginx下的html目录&#xff0c;编辑其中的index.html(在此…

FreeRTOS(任务管理的创建、删除、挂起、恢复)

目录 一、任务的基本概念 二、任务状态的概念 1、Running—运行态&#xff1a; 2、Ready—就绪态 3、Blocked—阻塞态 4、Suspended—挂起态 三、任务状态的切换 四、系统启动 1、vTaskStartScheduler()函数 1.1 作用 1.2 启动函数介绍 2、空闲任务 2.1 空闲任务的作…

【ChatGPT 指令大全】销售怎么借力ChatGPT提高效率

目录 销售演说 电话销售 产出潜在客户清单 销售领域计划 销售培训计划 总结 随着人工智能技术的不断进步&#xff0c;我们现在有机会利用ChatGPT这样的智能助手来改进我们的销售工作。在接下来的时间里&#xff0c;我将为大家介绍如何运用ChatGPT提高销售效率并取得更好的…

nbcio-boot因升级mybatis-plus到3.5.3.1和JSQLParser 到4.6引起的online表单开发的数据库导入出错解决

更多功能看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/nbcio-boot 前端代码&#xff1a;https://gitee.com/nbacheng/nbcio-vue.git 在线演示&#xff08;包括H5&#xff09; &#xff1a; http://122.227.135.243:9888 nbcio-boot因升级…

专业的ADAS测试记录仪ETHOS

随着ADAS驾驶辅助系统技术的快速发展及日臻成熟&#xff0c;近年来ADAS在全球汽车市场已开始快速普及和商业化&#xff0c;而如何确保ADAS系统的可靠和安全俨然成为汽车领域的重要问题。因此&#xff0c;ADAS驾驶辅助系统的测试也成为了各大整车厂及零部件厂商所关注的焦点。 一…

NodeJS原型链污染ctfshow_nodejs

文章目录 NodeJS原型链污染&ctfshow_nodejs前言0x01.原型与原型链0x02.prototype和__proto__分别是什么&#xff1f;0x03.原型链继承不同对象的原型链* 0x04.原型链污染原理0x05.merge()导致原型链污染0x06.ejs模板引擎RCEejs模板引擎另一处rce 0x07.jade模板引擎RCE【ctfs…

mysql数据库如何转移到oracle

mysql数据库转移到oracle 在研发过程中&#xff0c;可能会用到将表数据库中的表结构及数据迁移到另外一种数据库中&#xff0c; 比如说从mysql中迁移到oracle中&#xff0c; 常用的方法有好些&#xff0c;如下 1、使用powerdesigner&#xff0c;先连接mysql然后生成mysql的p…

自动化测试的生命周期是什么?

软件测试发展到今日&#xff0c;已经逐渐标准化且能力更强&#xff0c;其流程每天都在发展。测试人员的技术熟练程度对于整个测试阶段的成功来说至关重要。测试不再意味着仅仅发现错误&#xff1b;它的范围已经扩大&#xff0c;从任何开发项目开始就可以看出它的重要性。 当谈论…

《合成孔径雷达成像算法与实现》Figure3.9

代码复现如下&#xff1a; clc clear close all% 参数设置 TBP 100; % 时间带宽积 T 7.2e-6; % 脉冲持续时间 t_0 1e-6; % 脉冲回波时延% 参数计算 B TBP/T; …

管理类联考——逻辑——论证逻辑——汇总篇——真题和典例——支持

支持 没有特点的 199-2017-1-30——支持论点 离家300米的学校不能上&#xff0c;却被安排到2千米外的学校就读&#xff0c;某市一位适龄儿童在上小学时就遭遇了所在区教育局这样的安排&#xff0c;而这一安排是区教育局根据儿童户籍所在施教区做出的。根据该市教育局规定的“…

使用 Spring Boot 发送电子邮件(SMTP 集成)

本文探讨了 Spring Boot 与 SMTP 的集成以及如何从您自己的 Spring Boot 应用程序发送电子邮件。 本文探讨如何从您自己的Spring Boot应用程序发送电子邮件。 是的&#xff0c;您可以拥有专用的 REST API&#xff0c;它接受电子邮件发送者和接收者的电子邮件地址、主题…

图的遍历之 深度优先搜索和广度优先搜索

深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search)&#xff0c;和树的先序遍历比较类似。 它的思想&#xff1a;假设初始状态是图中所有顶点均未被访问&#xff0c;则从某个顶点v出发&#xff0c;首先访问该顶点&#xff0c;然后依次从它的各…

虹科新闻 | 虹科与Power-MI正式建立合作伙伴关系

近日&#xff0c;虹科与Power-MI正式建立合作伙伴关系&#xff0c;双方就工业预测性维护领域进行深入的交流与合作&#xff0c;未来将共同致力于为亚洲市场提供完整的、更高质量的预测性维护解决方案&#xff0c;解决亚洲客户的工业自动化挑战。 虹科与Power-MI都表示十分期待…

(2023Arxiv)Meta-Transformer: A Unified Framework for Multimodal Learning

论文链接&#xff1a;https://arxiv.org/abs/2307.10802 代码链接&#xff1a;https://github.com/invictus717/MetaTransformer 项目主页&#xff1a;https://kxgong.github.io/meta_transformer/ 【注】&#xff1a;根据实验结果来看&#xff0c;每次输入一种数据源进行处…