数据结构——栈和队列OJ题

栈和队列小提升!
- 前言
- 一、用队列实现栈
- 队列接口实现
- (1)栈的接口定义
- (2)栈的初始化
- (3)入栈函数的定义
- (4)出栈函数的定义
- (5)查找栈顶元素
- (6)判空函数的定义
- (7)销毁函数的定义
- 二、用栈实现队列
- 栈的接口实现
- (1)队列的接口定义
- (2)队列的初始化
- (3)入队函数的定义
- (4)出队函数的定义
- (5)查找队头函数的定义
- (6)判空函数的定义
- (7)销毁函数的定义
- 三、设计循环队列
- (1)循环队列的接口定义
- (2)循环队列的初始化
- (3)判空函数的定义
- (4)判满函数的定义
- (5)循环队列插入函数的定义
- (6)循环队列删除函数的定义
- (7)查找队头函数的定义
- (8)查找队尾函数的定义
- (9)销毁函数的定义
- 总结
前言
欢迎来到专项提升小课堂!
今天的题目稍稍有难度哦!
但是只要用心,是难不倒同学们的!
一、用队列实现栈
题目链接:OJ链接


提示:
1 <= x <= 9;
最多调用100 次 push、pop、top 和 empty ;
每次调用 pop 和 top 都保证栈不为空;
核心思想:
用队列模拟出栈的先入后出这一特性!
解题思路:
此题可以用两个队列去实现一个栈,每次始终保持一个队列为空,
入栈操作相当于给非空队列进行入队操作
出栈操作相当于非空队列的队尾元素出队,此时需要把非空队列除最后一个元素之外的其余元素入队到空队列,然后出队最后一个队尾元素
图例解析:


代码示例:
队列接口实现
先将队列的实现接口导入
这里涉及到之前队列建立的内容啦!
如果不了解的可以去看看:栈和队列
//头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(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->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);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);return pq->size;
}
队列实现栈的功能函数的定义
(1)栈的接口定义
typedef struct {Que q1;Que q2;
} MyStack;
(2)栈的初始化
MyStack* myStackCreate() {MyStack*pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}
(3)入栈函数的定义
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}
(4)出栈函数的定义
int myStackPop(MyStack* obj) {Que*Empty=&obj->q1;Que*nonEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){Empty=&obj->q2;nonEmpty=&obj->q1;}while(QueueSize(nonEmpty)>1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}
(5)查找栈顶元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}
(6)判空函数的定义
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
(7)销毁函数的定义
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}
二、用栈实现队列
题目链接:OJ链接


提示:
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的(例如,一个空的队列不会调用 pop 或者 peek 操作)
核心思想:
用栈模拟出队列的先入先出这一特性!
解题思路:
此题可以用两个栈实现,一个栈进行入队操作,另一个栈进行出队操作
出队操作: 当出队的栈不为空是,直接进行出栈操作,如果为空,需要把入队的栈元素全部导入到出队的栈,然后再进行出栈操作
图例解析

代码示例:
栈的接口实现
先将栈的实现接口导入
这里涉及到之前栈的建立的内容啦!
如果不了解的可以去看看:栈和队列
//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);--ps->top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps->top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
栈实现队列的功能函数的定义
(1)队列的接口定义
typedef struct {ST pushst;ST popst;
} MyQueue;
(2)队列的初始化
MyQueue* myQueueCreate() {MyQueue*obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}
(3)入队函数的定义
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);
}
(4)出队函数的定义
int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}
(5)查找队头函数的定义
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);
}
(6)判空函数的定义
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}
(7)销毁函数的定义
void myQueueFree(MyQueue* obj) {STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);
}
三、设计循环队列
题目链接:OJ链接


提示:
所有的值都在 0 至 1000 的范围内;
操作数将在 1 至 1000 的范围内;
请不要使用内置的队列库。
核心思想:
首尾相连循环即为环形!
解题思路:
通过一个定长数组实现循环队列
入队:首先要判断队列是否已满,再进行入队的操作,入队操作需要考虑索引循环的问题,当索引越界,需要让它变成最小值
出队:首先要判断队列是否为空,再进行出队操作,出队也需要考虑索引循环的问题
判空: 队头 == 队尾
判满: 队尾 + 1 == 队头
图例解析:



代码示例:
(1)循环队列的接口定义
typedef struct {int *a;int front;int rear;int k;
} MyCircularQueue;
(2)循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->front=obj->rear=0;obj->k=k;return obj;
}
(3)判空函数的定义
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}
(4)判满函数的定义
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}
(5)循环队列插入函数的定义
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;
}
(6)循环队列删除函数的定义
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front%=(obj->k+1);return true;
}
(7)查找队头函数的定义
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}
(8)查找队尾函数的定义
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
(9)销毁函数的定义
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
总结
今天的题目难度真的不小哦!
但也要相信自己!
自信就是最好解决问题的方法!
相关文章:
数据结构——栈和队列OJ题
栈和队列小提升! 前言一、用队列实现栈队列接口实现(1)栈的接口定义(2)栈的初始化(3)入栈函数的定义(4)出栈函数的定义(5)查找栈顶元素࿰…...
同态排序算法
参考文献: [Batcher68] Batcher K E. Sorting networks and their applications[C]//Proceedings of the April 30–May 2, 1968, spring joint computer conference. 1968: 307-314. [SV11] Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. IA…...
“深入探索JVM内部机制:解析Java虚拟机的工作原理“
标题:深入探索JVM内部机制:解析Java虚拟机的工作原理 摘要:本文将介绍Java虚拟机(JVM)的工作原理,包括类加载、内存管理、垃圾回收和字节码执行等方面。通过深入理解JVM的内部机制,开发人员可以…...
为应用程序接入阿里云CDN优化网站访问速度
文章目录 1.KodCloud云盘系统接入CDN之前的效果2.配置KodCloud云盘接入CDN加速器2.1.添加CDN域名2.2.配置域名信息2.3.CDN推荐配置设置2.4.CDN加速器配置完成 3.配置云解析DNS增加CDN域名的解析4.为CDN加速器配置HTTPS5.验证网站是否接入CDN6.访问应用程序观察请求速度7.观察CD…...
索引设计规范
索引是帮助数据库高效获取数据的数据结构。索引是加速查询的常用技术手段。在设计索引时,要遵循索引设计规范,避免不必要的踩坑。 【推荐】索引存储结构推荐BTREE InnoDB和MyISAM存储引擎表,索引类型必须为BTRER,MEMORY表可以根…...
Appium 2安装与使用java对Android进行自动化测试
文章目录 1、Appium 2.1安装1.1、系统要求1.2、安装Appium2.1服务1.3、安装UiAutomator2驱动1.4、安装Android SDK platform tools1.5、下载OpenJDK 2、Android自动代码例子2.1、安装Android自动化测试元素定位工具Appium Inspector2.2、编写android app自动化测试代码和使用ex…...
小程序运营方式有哪些?如何构建小程序运营框架?
如今,每个企业基本都做过至少一个小程序,但由于小程序本身不具备流量、也很少有自然流量,因此并不是每个企业都懂如何运营小程序。想了解小程序运营方式方法有哪些? 在正式运营小程序前,了解小程序的功能与企业实际经…...
【golang】for语句和switch语句
使用携带range子句的for语句时需要注意哪些细节? numbers1 : []int{1, 2, 3, 4, 5, 6} for i : range numbers1 {if i 3 {numbers1[i] | i} } fmt.Println(numbers1)这段代码执行后会打印出什么内容? 答案:[1 2 3 7 5 6] 当for语句被执行…...
三、数据库索引
1、索引介绍 索引是一种用于快速查询和检索数据的数据结构,其本质可以看成是一种排序好的数据结构。 常见的索引结构有:B数,B树,Hash和红黑树等。在MySQL中,无论是 InnoDB还是MyISAM,都使用了B树作为索引…...
长时间带什么耳机最舒服,分享长时间佩戴舒服的耳机推荐
时代在进步,科技在不断革新。近年来,一种崭新的耳机——骨传导耳机,如火如荼地进驻耳机市场,引起一阵热潮。不论是平日里的工作出勤还是运动时的挥洒汗水,相比传统耳机,骨传导耳机无疑更加贴合现代生活的需…...
Yolov8小目标检测(1)
💡💡💡本文目标:通过原始基于yolov8的红外弱小目标检测,训练得到初版模型,进行问题点分析; 💡💡💡Yolo小目标检测,独家首发创新(原创),适用于Yolov5、Yolov7、Yolov8等各个Yolo系列,专栏文章提供每一步步骤和源码,带你轻松实现小目标检测涨点 💡💡…...
GPS定位漂移问题分析
有很多种因素会影响到GPS的准确率,以下是一个GPS误差引入简表: l 卫星时钟误差:0-1.5米 l 卫星轨道误差:1-5米 l 电离层引入的误差:0-30米 l 大气层引入的误差:0-30米 l 接收机…...
前端简介(HTML+CSS+JS)
学习Django过程中遇到一些前端相关的内容,于是整理了一下相关概念。 前端开发是创建WEB页面或APP等前端界面呈现给用户的过程。 如果只是想要入门前端,只要学习网页三剑客(HTML、CSS、JavaScript)即可。 如果把网页比喻成一个房子,HTML就是…...
List与String数组互转
一.List 转为 String 数组 1.使用toArray方法 public static void main(String[] args) {List<String> list Lists.newArrayList("1","2","3");// Java6以前版本String[] str1 list.toArray(new String[list.size()]);// Java6以后版本…...
MySQL中的数据类型
文章目录 1 常见的数据类型2 整数类型2.1 属性 M2.2 属性 UNSIGNED2.3 属性 ZEROFILL2.4 整数类型的适用场景 3 浮点类型4 定点类型5 位类型6 日期与时间类型6.1 YEAR 类型6.2 DATE 类型6.3 TIME 类型6.4 DATETIME 类型6.5 TIMESTAMP 类型 1 常见的数据类型 类型类型分类整数类…...
python多任务
一、多任务 1.1 概念 多任务就是指:同一时间能执行多个任务。比方我们的电脑能一边QQ聊天,一边写论文,还能听歌。 1.2 多任务的优势: 多任务的最大好处是 充分利用CPU资源,提高程序的执行效率。 1.3 多任务的两种表…...
c语言 - inline关键字(内联函数)
概念 在编程中,inline是一个关键字,用于修饰函数。inline函数是一种对编译器的提示,表示这个函数在编译时应该进行内联展开。 内联展开是指将函数的代码插入到调用该函数的地方,而不是通过函数调用的方式执行。这样可以减少函数调…...
如何在Ubuntu 18.04上安装PHP 7.4并搭建本地开发环境
引言 PHP是一种流行的服务器脚本语言,用于创建动态和交互式web页面。开始使用你选择的语言是学习编程的第一步。 本教程将指导您在Ubuntu上安装PHP 7.4,并通过命令行设置本地编程环境。您还将安装依赖管理器Composer,并通过运行脚本来测试您…...
狭义相对论
文章目录 一、为什么光速不变?二、为什么爱因斯坦坚信“相对性原理”三、逻辑和数学显威力,狭义相对论时空变换(洛伦兹变换)推导四、新时空变换带来的新时空观1、有关相对论时间的“傻问题”2、关于相对论的“怪问题”3、关于“双…...
仓库使用综合练习
目录 1、使用mysql:5.6和 owncloud 镜像,构建一个个人网盘。 2、安装搭建私有仓库 Harbor 3、编写Dockerfile制作Web应用系统nginx镜像,生成镜像nginx:v1.1,并推送其到私有仓库。 4、Dockerfile快速搭建自己专属的LAMP环境,生…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
