当前位置: 首页 > news >正文

【使用两个栈实现队列】

文章目录

  • 一、栈和队列的基本特点
  • 二、基本接口函数的实现
    • 1.栈的接口
    • 2.创建队列骨架
    • 3.入队操作
    • 4.取出队列元素
    • 5.返回队首元素
    • 6.判断队列是否为空
    • 7.销毁队列
  • 总结


一、栈和队列的基本特点

栈的特点是后进先出,而队列的特点是先进先出。
使用两个栈实现队列,必须具备队列的先进先出的功能。

举个例子:
在这里插入图片描述
向其中一个栈中放入4个元素,那么按照队列的特点,出队时是1先出队,所以需要把栈的所有元素全部出栈转移到空栈中。

再逐一出元素。

假如出栈一次后,又需要入栈,如下图:
在这里插入图片描述
则需要把元素存入空栈中,出栈的时候就出右边的非空栈。
出完右边的非空栈后,假如还想出栈,应该出的是5,那么就把左边的元素导入到右边的空栈,再出栈。

在这里插入图片描述

题目如下:
两个栈实现队列

在这里插入图片描述

二、基本接口函数的实现

1.栈的接口

typedef int STDataType;//采用顺序表来实现栈和队列
//采用链表形式来实现也可以,不过更加推荐顺序表,顺序表
//最大的优点就是支持随机访问typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);//取栈顶数据
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps); //也可以用int作为类型返回值void StackPrint(const ST *ps);void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;//top也可以给-1,给0的意思是,先给值,再++。---指向栈顶数据的下一个//top给-1是先++再给值。---指向栈顶数据。}void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity)//空间不足,增容{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);//当ps->a 为NULL时,realloc相当于malloc。不用分类讨论ps->a是否为空assert(tmp != NULL);ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;}void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;}
void StackPop(ST* ps)//取栈顶数据
{assert(ps);//assert(ps->top > 0);assert(!StackEmpty(ps));//也可以这样写ps->top--;//但是这里有问题,top会减到小于0,所以需要断言top要>0
}//取栈顶数据
STDataType StackTop(ST* ps)
{assert(ps);//这里也需要给定,top必须大于0,assert(ps->top > 0);return ps->a[ps->top - 1];//顺序表相当于数组,下标从0开始,并且top也是从0开始的,所以需要-1
}int StackSize(ST* ps)//返回栈的元素个数
{assert(ps);return ps->top;
}bool StackEmpty(ST* ps)//判断栈内是否还有元素
{assert(ps);//if (ps->top == 0)//{//	return true;//}//else//{//	return false;//}return ps->top == 0;//表达式为真,返回逻辑真,为假,返回逻辑假
}void StackPrint(const ST*ps)//栈要保证后进先出。
{assert(ps);for (int i = ps->top-1; i>=0; --i){printf("%d ",ps->a[i]);}printf("\n");
}

2.创建队列骨架

typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*q = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&q->pushST);StackInit(&q->popST);return q;
}

这里可以细致地将两个栈分为入数据栈(pushST)和出数据栈(popST),便于操作。

3.入队操作

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

4.取出队列元素

int myQueuePop(MyQueue* obj) 
{//应该先要判断popST中是否有元素,如果有元素,那就直接pop掉//popST中的元素,如果没有元素,先全部导入进去,然后再popif(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;
}

注意,取出队列元素时,先判断popST栈是否为空,如果不为空,直接在这个栈中出元素。
如果为空,先将pushST栈的元素导入到popST栈,再从popST栈出元素


5.返回队首元素

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) 
{//如果popST还有元素,则直接在这里返回,如果没有元素,则应该先把pushST的元素全部导入PopST,再取栈顶元素if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);
}

这里也有需要注意的点:
返回队首元素应先判断pushST栈是否为空,如果不为空直接从这个栈返回栈顶元素,如果为空,应该先从pushST栈导入数据到popST,再从popST栈中出栈顶元素。

6.判断队列是否为空

bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

判断队列是否为空,等同于判断完两个栈是否为空。

7.销毁队列

void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);
}

先释放两个栈,再释放这两个栈所在的结构体。

总结

以上就是今天要讲的内容,本文简单介绍了两个栈实现队列的方法。

相关文章:

【使用两个栈实现队列】

文章目录一、栈和队列的基本特点二、基本接口函数的实现1.栈的接口2.创建队列骨架3.入队操作4.取出队列元素5.返回队首元素6.判断队列是否为空7.销毁队列总结一、栈和队列的基本特点 栈的特点是后进先出,而队列的特点是先进先出。 使用两个栈实现队列,必…...

web,h5海康视频接入监控视频流记录一

项目需求,web端实现海康监控视频对接接入,需实现实时预览,云台功能,回放功能。 web端要播放视频,有三种方式,一种是装浏览器装插件,一种是装客户端exe,还有就是无插件了。浏览器装插…...

做毕业设计,前端部分你需要掌握的6个核心技能

其实前端新手如果想要自己实现一套毕业设计项目并非简单的事,因为之前很多人一直还停留在知识点的阶段,而且管理系统和C端网站都需要开发,但现在需要点连成线了。所以在启动项目开发之前呢,针对前端部分,我列举一些非常…...

Read book Netty in action(Chapter VIII)--EventLoop and thread model

前言 简单地说,线程模型指定了操作系统、编程语言、框架或者应用程序的上下文中的线程管理的关键方面。显而易见地,如何以及何时创建线程将对应用程序代码的执行产生显著的影响,因此开发人员需要理解与不同模型相关的权衡。无论是他们自己选…...

番外11:使用ADS对射频功率放大器进行非线性测试3(使用带宽5MHz的WCDMA信号进行ACLR测试)

番外11:使用ADS对射频功率放大器进行非线性测试3(使用带宽5MHz的WCDMA信号进行ACLR测试) 其他测试: 番外9:使用ADS对射频功率放大器进行非线性测试1(以IMD3测试为例) 番外10:使用AD…...

Linux libpqxx 库安装及使用

记录一下linux安装 libpqxx遇到的一些问题 1.准备安装包: 1.准备安装包,以libpqxx-4.0.1.tar.gz为例子 链接如下:https://launchpad.net/libpqxx/milestone/4.0.1 2.上传并安装 上传到安装目录并安装,我是放到/use/local下面 c…...

如何使用COM-Hunter检测持久化COM劫持漏洞

关于COM-Hunter COM- Hunter是一款针对持久化COM劫持漏洞的安全检测工具,该工具基于C#语言开发,可以帮助广大研究人员通过持久化COM劫持技术来检测目标应用程序的安全性。 关于COM劫持 微软在Windows 3.11中引入了(Component Object Model, COM)&…...

Cartesi 举办的2023 黑客马拉松

Cartesi 是具有 Linux 运行时的特定于应用程序的Rollups执行层。Cartesi 的特定应用程序 Optimistic Rollup 框架使区块链堆栈足够强大,开发人员可以构建计算密集型和以前不可能的去中心化实例。Cartesi 的 RISC-V 虚拟机支持 Linux 运行时环境,允许像你…...

架构篇--代码质量手册

目前团队缺少SA(研发经理)的角色,大家代码写的有点随意,老板让我写一份开发手册。嗯!!!当时我稍微纠结了一下,感觉这个似乎不是我的工作范畴,但是本着"我就是块砖&a…...

那些年用过的IDEA插件

今天和大家分享一下经常使用的IDEA的插件,希望有所帮助。一、IDEA插件CodeGlance2显示代码缩略图插件,方便查看代码。Lombok用于编译期间自动生成getter、setter、构造、toString等方法,简化代码。Mybatis Builder或MybatisXMapper接口和xml双…...

python+requests实现接口自动化测试

这两天一直在找直接用python做接口自动化的方法,在网上也搜了一些博客参考,今天自己动手试了一下。 一、整体结构 上图是项目的目录结构,下面主要介绍下每个目录的作用。 Common:公共方法:主要放置公共的操作的类,比如数据库sqlhe…...

rtthread 线程

创建动态线程最简单代码 #include <rtthread.h>//包含头文件static rt_thread_t thread1 RT_NULL; //创建线程控制块指针&#xff0c;指向空static void thread1_entry(void *parameter)//线程入口&#xff08;干什么&#xff09; {rt_kprintf("do something"…...

伯恩光学再成被执行人:多次因劳动纠纷被起诉,曾冲刺港交所上市

近日&#xff0c;贝多财经从天眼查APP了解到&#xff0c;伯恩光学&#xff08;深圳&#xff09;有限公司&#xff08;下称“伯恩光学”&#xff09;因《伯恩光学&#xff08;深圳&#xff09;有限公司与温*燕劳动合同纠纷的案件》一事&#xff0c;被广东省深圳市龙岗区人民法院…...

mysql基础操作2

通配符_&#xff1a;一个任意字符&#xff0c;like ‘张_’%&#xff1a;任意长度的字符串&#xff0c;like ‘co%’&#xff0c;‘%co’&#xff0c;‘%co%’【】&#xff1a;括号中所指定范围内的一个字符&#xff0c;like ‘9W0【1-2】’【^】&#xff1a;不在括号中所指定范…...

指针的进阶【下篇】

文章目录&#x1f4c0;8.指向函数指针数组的指针&#x1f4c0;9.回调函数&#x1f4c0;8.指向函数指针数组的指针 &#x1f330;请看代码与注释&#x1f447; int Add(int x, int y) {return x y; } int Sub(int x, int y) {return x - y; } int main() {int (*pf)(int, int…...

不同序列模型的输入和输出总结

不同序列模型的输入和输出总结 文章目录不同序列模型的输入和输出总结RNNLSTMGRURNN RNN 是迭代输出&#xff1a; 输入第一个 -> 输出第二个&#xff0c; 输入第二个 -> 输出第三个&#xff0c; 输出倒数第二个 -> 输出最后一个。 LSTM LSTM 也是迭代输出&#xff…...

基于神经网络补偿的主动悬架自适应控制

目录 前言 1. 1/4悬架模型 2.仿真分析 2.1仿真模型 2.2仿真结果 2.1 形① 2.2 形② 3. 总结 前言 上两篇博客我们介绍了神经网络补偿控制律的仿真测试&#xff0c;从仿真结果我们可以得知神经网络具有逼近扰动&#xff0c;并将其补偿的作用。 上两篇文章链接&#xf…...

什么是链表,如何实现?(单链表篇)

欢迎来到 Claffic 的博客 &#x1f49e;&#x1f49e;&#x1f49e; “仅仅活着是不够的&#xff0c;还需要有阳光&#xff0c;自由和花的芬芳。” 前言&#xff1a; 在日常使用的网站和软件中&#xff0c;列表属于最常见的一种东西了&#xff0c;其实现形式有顺序表&#xff0…...

探针台简介

探针台&#xff0c;是我们半导体实验室电学性能测试的常用设备&#xff0c;也是各大实验室以及芯片设计、封装测试的熟客。设备具备各项优势&#xff0c;高性能低成本&#xff0c;用途广&#xff0c;操作方便&#xff0c;在不同测试环境下&#xff0c;测试结果稳定&#xff0c;…...

ABAP 辨析 标准表|排序表|哈希表

1、文档介绍 本文档将介绍内表的区别和用法&#xff0c;涉及标准表、排序表、哈希表 2、用法与区别 2.1、内表种类 内表顶层为任意表&#xff0c;任意表分为索引表和哈希表&#xff0c;索引表又可分为标准表和排序表&#xff0c;结构如图&#xff1a; 2.2、内表用法 2.2.1…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

Java设计模式:责任链模式

一、什么是责任链模式&#xff1f; 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09; 是一种 行为型设计模式&#xff0c;它通过将请求沿着一条处理链传递&#xff0c;直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者&#xff0c;…...

EC2安装WebRTC sdk-c环境、构建、编译

1、登录新的ec2实例&#xff0c;证书可以跟之前的实例用一个&#xff1a; ssh -v -i ~/Documents/cert/qa.pem ec2-user70.xxx.165.xxx 2、按照sdk-c demo中readme的描述开始安装环境&#xff1a; https://github.com/awslabs/amazon-kinesis-video-streams-webrtc-sdk-c 2…...