栈和队列专题(LeetCode)

news/2024/7/20 18:18:35/文章来源:https://blog.csdn.net/2301_79722622/article/details/139040184

目录

  • 有效的括号
    • 题解
    • 代码加解释
  • 用队列实现栈
    • 题解
    • 代码加解释
  • 设计循环队列
    • 题解
    • 代码加解释
  • 用栈实现队列
    • 题解
    • 代码加解释

有效的括号

在这里插入图片描述

题解

左括号从s字符串中取出来放入
s中就只有右括号
那么栈顶的左括号和s的右括号匹配即可
代码中也详细解释了左括号和右括号多少的问题

代码加解释

bool isValid(char* s) 
{Stack sl;StackInit(&sl);while(*s){//先插入左括号if(*s == '('||*s == '{'||*s == '['){StackPush(&sl,*s);}else//右括号取栈顶左括号尝试匹配{if(STEmpty(&sl)){//解决右括号比左括号多的情况//s中只有右括号,top == 0StackDestroy(&sl);//释放sl指向的空间return false;}//取栈顶数据char top = STTop(&sl);//把栈顶的括号取出来和右括号匹配StackPop(&sl);//弹出栈顶数据,方便取下一个数据//不匹配if(top == '('&& *s != ')'||top == '['&&*s != ']'||top == '{'&&*s != '}'){StackDestroy(&sl);return false;}}s++;}//栈不为空,左括号的数量比右括号的数量多,数量不匹配//只有一个左括号,假//解决的是右括号和左括号一样多和左括号多的情况bool ret = STEmpty(&sl);//栈为空,top == 0,真StackDestroy(&sl);return ret; 
}

用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

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

注意:

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

示例:

输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示:

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶:你能否仅用一个队列来实现栈。

题解

实现各个接口,用两个队列实现栈
主体思路还是保证一个队列是空的,一个队列是非空的
空的队列用于导数据,比如非空队列 1 2 3 4,1 2 3导到空的队列中,4直接pop,对应栈顶的删除
非空的队列直接插入数据,因为队列是尾插,也就是栈顶的插入
在这里插入图片描述
MyStack下有一个重要的说明
1.后取地址,相当于开了一个新的队列,在新的队列中许多值是未定义的,相当于随机值,所以不能后取地址
在这里插入图片描述

2.先取地址,是对原队列进行操作,指针指向原队列
在这里插入图片描述

代码加解释

//C语言要造轮子,前面的接口在上一个博客,需要的可以自取
typedef struct 
{Queue q;//队列1Queue p;//队列2
} MyStack;MyStack* myStackCreate() 
{//一个队列为空,另一个队列为有数据//把数据插入非空队列中,空的队列用来导数据MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//不能和题里创建一样的指针,重定义QueueInit(&(obj->p));QueueInit(&(obj->q));//初始化队列1和队列2return obj;
}void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->p))){QueuePush(&(obj->p),x);//第一个队列是非空的就插入第一个队列中}   else//1.p空q非空,插入队列q 2.p空q空,这种随便插入那个队列{QueuePush(&(obj->q),x);}
}int myStackPop(MyStack* obj) 
{//你不知道q,p那个队列是空,所以要假设//用空队列导一下//假设法,假设队列p为非空,队列q为空Queue* Noempty = &(obj->p);Queue* Empty = &(obj->q);if(!QueueEmpty(&(obj->q))){Empty = &(obj->p);Noempty = &(obj->q);}   while(QueueSize(Noempty) > 1){QueuePush(Empty, QueueTop(Noempty));QueuePop(Noempty);//卡在这个地方,把对头数据取出来,然后头删,再尾插入空的队列}int top = QueueTop(Noempty);QueuePop(Noempty); //把栈顶数据取出来,返回栈顶数据//再删掉最后的栈顶数据    return top;
}int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&(obj->q))){return QueueTail(&(obj->q));}  else{return QueueTail(&(obj->p));}
}bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&(obj->q)) && QueueEmpty(&(obj->p));    
}void myStackFree(MyStack* obj) 
{QueueDestroy(&(obj->q));QueueDestroy(&(obj->p));free(obj);    
}/**  * Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);*/

设计循环队列

在这里插入图片描述

题解

主要多开一个空间为了解决假溢出问题
代码里也有写

队列为空 -> head == tail
在这里插入图片描述

队列为满 -> (tail+1)% (k+1) == head
%k+1 为了解决回绕问题
普通的情况tail + 1 = head
在这里插入图片描述

  • 插入数据 -> (obj->tail) %= (obj->k+1);
    tail++ 变成5又要解决回绕问题,%k+1回到0位置可以插入数据
  • 删除数据 -> obj->head %= (obj->k+1)
    head++ 变成5又要解决回绕问题,%k+1回到0位置可以删除数据
  • 取队头数据 -> obj->a[obj->head]
    head指向头直接取队头数据
  • 取队尾数据 ->
    1.return obj->a[(obj->tail-1 + obj->k+1) % (obj->k+1)]
    2.return obj->tail == 0 ? obj->a[obj->k] : obj->a[obj->tail-1]

tail是指向队尾的下一个位置
取队尾数据要tail - 1,但是tail == 0时,tail - 1就会越界,
tail == 0时要回绕到 tail == k 是队尾数据的下标

有两种方法可以理解第二种比较好理解
第一种取一个数据也比较好理解
比如tail = 0,k = 4 时,-1+5 = 4 % k+1 = 4,就取到队尾的下标了

代码加解释

typedef struct 
{int* a;int head;//指向头int tail;//指向尾int k;     
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*(k+1));//多开一个空间,为了解决循环队列的假溢出问题//假溢出问题:比如开四个空间,head == tail是空,head == tail也是满obj->head = 0;obj->tail = 0;    obj->k = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->head == obj->tail;    
}bool myCircularQueueIsFull(MyCircularQueue* obj)  
{// tail + 1 == head;return (obj->tail+1) % (obj->k+1) == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->tail] = value;obj->tail++;(obj->tail) %= (obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return false;}    obj->head++;obj->head %= (obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->tail-1 + obj->k+1) % (obj->k+1)];//return obj->tail == 0 ? obj->a[obj->k] : obj->a[obj->tail-1];
}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->a);//先把数组释放,再把结构体释放free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

用栈实现队列

在这里插入图片描述

题解

设计一个为poplist的栈和pushlist的栈
一个栈专门插入数据
一个栈专门删除数据
StackPush(&(obj->pushlist),x)
直接入栈达到了先进的效果
将pushlist中的数据导入poplist中,先进的数据就达到先出的效果了
poplist中有数据直接出
没有数据从pushlist中导数据在出数据
所以两个栈只要有一个栈是非空的就可以出数据
只要有一个栈是非空的,就是非空队列
在这里插入图片描述

代码加解释

typedef struct 
{Stack pushlist;Stack poplist;//后进先出栈实现先进先出队列
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(obj->pushlist));StackInit(&(obj->poplist));return obj;
}void myQueuePush(MyQueue* obj, int x) 
{//直接插入pushlist的队列,队尾入数据也就是栈顶入数据StackPush(&(obj->pushlist),x);
}int myQueuePop(MyQueue* obj) 
{int front = myQueuePeek(obj);//push pop//传过去的应该是obj,指向两个栈的结构体指针StackPop(&(obj->poplist));return front;
}int myQueuePeek(MyQueue* obj) 
{if(STEmpty(&(obj->poplist))){while(!STEmpty(&(obj->pushlist))){StackPush(&(obj->poplist),STTop(&(obj->pushlist)));StackPop(&(obj->pushlist));}}int ret = STTop(&(obj->poplist));return ret;
}bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&(obj->pushlist)) && STEmpty(&(obj->poplist));    
}void myQueueFree(MyQueue* obj) 
{StackDestroy(&(obj->pushlist));StackDestroy(&(obj->poplist));free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

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

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

相关文章

【Linux】自己实现一个bash进程

bash就是命令行解释器&#xff0c;就是Linux操作系统让我们看到的&#xff0c;与用户进行交互的一种外壳&#xff08;shell&#xff09;&#xff0c;当然了bash也是一个进程&#xff0c;它有时候就是通过创建子进程来执行我们输入的命令的。这无疑就离不开我们上篇博客所说的进…

继承详解——C++深度学习解析

前言 &#xff1a; 本节内容是讲解面向对象中三大特性之一的继承。 继承是面向对象程序设计中代码复用的一种重要手段。 通过继承&#xff0c; 我们就可以在原本的代码上进行扩展&#xff0c; 而不是重新写一段代码&#xff0c; 让代码变得冗余。 同时&#xff0c; 继承也体现了…

摸鱼大数据——Hive表操作——复杂类型

1、hvie的SerDe机制 其中ROW FORMAT是语法关键字&#xff0c;DELIMITED和SERDE二选其一。本次我们主要学习DELIMITED关键字相关知识点 如果使用delimited: 表示底层默认使用的Serde类:LazySimpleSerDe类来处理数据。 如果使用serde:表示指定其他的Serde类来处理数据,支持用户自…

破解面试难题:面试经典150题 之双指针法详解与代码实现

面试经典 150 题 - 学习计划 - 力扣&#xff08;LeetCode&#xff09;全球极客挚爱的技术成长平台https://leetcode.cn/studyplan/top-interview-150/ 125. 验证回文串 125. 验证回文串 STL容器 思路&#xff1a; 遍历输入的字符串&#xff0c;将其中的字母字符转换为小写&am…

排序进阶----插入排序,希尔排序

各位看官们好&#xff0c;接下来鄙人想与大家分享的实现被称为六大排序之一的插入排序。其实关于这六大排序在我们最开始就已经接触过了。我们在最开始学习c语言的时候&#xff0c;我们要学习到其中之一的冒泡排序。虽然现在看起来冒泡排序确实是没有太大的实际效果&#xff0c…

【物联网实战项目】STM32C8T6+esp8266/mqtt+dht11+onenet+uniapp

一、实物图 前端uniapp效果图&#xff08;实现与onenet同步更新数据&#xff09; 首先要确定接线图和接线顺序&#xff1a; 1、stm32c8t6开发板连接stlinkv2下载线 ST-LINK V2STM323.3V3.3VSWDIOSWIOSWCLKSWCLKGNDGND 2、ch340串口连接底座&#xff08;注意RXD和TXD的连接方式…

kali下载zsteg和stegpy

1.kali下载zsteg 从 GitHub 上克隆zsteg到kali git clone https://github.com/zed-0xff/zsteg 切换目录 cd zsteg 用于安装名为 zsteg 的 Ruby Gem 包 gem install zsteg 2.kali下载stegpy 下载网站内的stegpy-master压缩包GitCode - 开发者的代码家园 并拉到kali中 切换到s…

【豆伴匠】L1-L12更新完,一站式解决文史积累、阅读、写作难题,弯道超车,寒假必备

合抱之木&#xff0c;生于毫末&#xff1b; 九层之台&#xff0c;起于垒土&#xff1b; 千里之行&#xff0c;始于足下。 豆伴匠是什么&#xff1f; 豆伴匠内容包括&#xff1a;人、文、史、作四个模块&#xff0c;全面覆盖文史知识及读写技巧。 目前&#xff0c;豆伴匠有L…

【MySQL】SQL 基础

文章目录 【 1. SQL 的书写规则 】1.1 大小写规则1.2 常量的表示1.3 注释1.4 HELP 系统帮助 【 2. 常用数据库函数 】2.1 SHOW DATABASES 显示数据库2.2 CREATE DATABASE 创建数据库2.3 ALTER DATABASE 修改数据库2.4 DROP DATABASE 删除数据库2.5 USE 选择数据库 【 3. RDBMS …

PyTorch张量索引用法速查

作为数据科学家或软件工程师&#xff0c;你可能经常处理大型数据集和复杂的数学运算&#xff0c;这些运算需要高效且可扩展的计算。PyTorch 是一个流行的开源机器学习库&#xff0c;它通过 GPU 加速提供快速灵活的张量计算。在本文中&#xff0c;我们将深入研究 PyTorch 张量索…

【架构-19】架构风格比较

独立构件风格(Independent Components): 适用场景:需要灵活扩展和组合的复杂大数据应用 特点: 高度解耦:各组件之间高度独立,可单独开发和部署 灵活性和可扩展性:易于根据需求添加或替换组件 复杂度高:需要管理多个独立的组件及其交互 通信开销:组件间需要通过网络通信,可能会…

深入探索C++继承机制:从概念到实践的全面指南

目录 继承的概念及定义 继承的概念 继承的定义 定义格式 继承方式和访问限定符 继承基类成员访问方式的变化 默认继承方式 基类和派生类对象赋值转换 继承中的作用域 派生类的默认成员函数 继承与友元 继承与静态成员 继承的方式 菱形虚拟继承 菱形虚拟继承原理 继承…

超详细的前后端实战项目(Spring系列加上vue3)前端篇+后端篇(三)(一步步实现+源码)

好了&#xff0c;兄弟们&#xff0c;继昨天的项目之后&#xff0c;开始继续敲前端代码&#xff0c;完成前端部分&#xff08;今天应该能把前端大概完成开启后端部分了&#xff09; 昨天补充了一下登录界面加上了文章管理界面和用户个人中心界面 完善用户个人中心界面 修改一…

华为设备WLAN配置之AP上线

WLAN基础配置之AP上线 配置WLAN无线网络的第一阶段&#xff0c;AP上线技术&#xff1a; 实验目标&#xff1a;使得AP能够获得来自AC的DHCP地址服务的地址&#xff0c;且是该网段地址池中的IP。 实验步骤&#xff1a; 1.把AC当作三层交换机配置虚拟网关 sys Enter system view,…

halcon SVM 缺陷检测分类

一、概述 训练数据 二、算子解释 compactness Halcon 算子 compactness_halcon compactness-CSDN博客 *计算输入区域的紧凑度 compactness (Region, Compactness) 原理解释 convexity 每个输入区域的凸度 Halcon 算子 convexity_halcon convexity-CSDN博客 *计算每个输…

Unity LayerMask避坑笔记

今天使用Physics2D.OverlapAreaNonAlloc进行物理检测时候&#xff0c;通过LayerMask.NameToLayer传入了int值的LayerMask&#xff0c;结果一直识别不到&#xff0c;经过Debug才找到问题&#xff0c;竟是LayerMask的“值”传输有问题&#xff0c;记录一下。 直接贴代码输出结果&…

《SpringBoot》系列文章目录

SpringBoot是由Pivotal团队提供的全新框架&#xff0c;旨在简化新Spring应用的初始搭建以及开发过程。以下是一些关于SpringBoot的详细介绍&#xff1a; 设计目的&#xff1a;SpringBoot通过特定的方式来进行配置&#xff0c;使得开发人员不再需要定义样板化的配置&#xff0c…

HNU-计算机体系结构-实验1-RISC-V流水线

计算机体系结构 实验1 计科210X 甘晴void 202108010XXX 1 实验目的 参考提供为了更好的理解RISC-V&#xff0c;通过学习RV32I Core的设计图&#xff0c;理解每条指令的数据流和控制信号&#xff0c;为之后指令流水线及乱序发射实验打下基础。 参考资料&#xff1a; RISC-…

【引领光子学革命:机器学习与深度学习重塑设计与应用新纪元】

光子器件的逆向设计&#xff1a;利用深度学习技术&#xff0c;可以优化多参数光子器件的设计。通过大量的数据分析和模式识别&#xff0c;深度学习算法能够预测和优化光子器件的性能&#xff0c;从而缩短设计周期并降低设计成本。 超构表面与超材料设计&#xff1a;在新型光学材…

浅谈金融行业数据安全分类分级

数据安全管理是一项从上而下的、多方配合开展的工作。在进行数据安全管理组织架构建设时&#xff0c;需要从上而下建设&#xff1b;从而全面推动数据安全管理工作的执行和落地&#xff1b;以保证数据安全的合法合规、并长效推动业务的发展和稳定运行。 金融行业机构应设立数据…