数据结构与算法-栈(LIFO)(经典面试题)
一:面试经典
1. 如何设计一个括号匹配的功能?比如给你一串括号让你判断是否符合我们的括号原则,
栈 力扣2. 如何设计一个浏览器的前进和后退功能?
思想:两个栈,一个栈存放前进栈,一个存放后退栈,刚开始连续点击三个页面,都存放到前进栈里,当点击后退时就出栈顶,然后放入后退栈中,以此重复。3. 简单的四则运算:3+11*2+8-15/5,
思想:两个栈来实现:一个放数字 一个放符号。
解决思路:我们从头开始遍历这个算术表达式:
1.遇到是数字 我们就直接入栈到数字栈里面去。
2.遇到是符号 就把符号栈的栈顶拿出来做比较。如果说他比栈顶符号的优先级高就直接入栈,如果比符号栈顶的优先级低或者相同,就从符号栈里面取栈顶进行计算(从数字栈中取栈顶的2个数),计算完的结果还要再放入到数字栈中。
二: 栈
1.如何理解栈
比如我们在放盘子的时候都是从下往上一个个放,拿的时候是从上往下一个个的那,不能从中间抽,这种其实就是一个典型的栈型数据结构。后进先出即Last In First Out (LIFO)。2.栈如何实现
其实它是一个限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈其实就是一个特殊的链表或者数组。
既然栈也是一个线性表,那么我们肯定会想到数组和链表,而且栈还有这么多限制,那为什么我们还要使用这个数据结构呢?不如直接使用数组和链表来的更直接么?数组和链表暴露太多的接口,实现上更灵活了,有些技术理解不到位的人员就可能出错。所以在某些特定场景下最好是选择栈这个数据结构。
三:栈的分类
3.栈的分类
(1)基于数组的栈——以数组为底层数据结构时,通常以数组头为栈底,数组头到数组尾为栈顶的生长方向

(2)基于单链表的栈——以链表为底层的数据结构时,以链表头为栈顶,便于节点的插入与删除,压栈产生的新节点将一直出现在链表的头部

最大的区别就是扩容,链表天然支持动态扩容。栈溢出。
四:栈的实现
public interface MyStack<Item> {MyStack<Item> push(Item item); //入栈Item pop(); //出栈int size(); // 大小boolean isEmpty();
}public class ArrayStack<Item> implements MyStack<Item>{private Item [] a = (Item[]) new Object[1]; //最好就是开始的时候就设置大小private int n = 0; //大小 初始的元素个数public ArrayStack(int cap) {a = (Item[]) new Object[cap];}public MyStack<Item> push(Item item) { //入栈就完成了 //时间复杂度 O(1)judgeSize();a[n++] = item;return null;}private void judgeSize(){if(n >= a.length){ //元素个数已经超出了数组的个数resize(2 * a.length); //10*2*2=40个大小了,我出栈了20个了,只剩下20了吧。}else if(n > 0 && n < a.length / 2){resize(a.length / 2);}}private void resize(int size){ //扩容O(n)Item[] temp = (Item[]) new Object[size];for(int i = 0 ; i < n; i ++){temp[i] = a[i];}a = temp;}public Item pop() { //出栈 O(1)if(isEmpty()){return null;}//item[n--]//item[--n]Item item = a[--n]; //n不是已经--了么 --n和n-- --n是先把n减了在用,n--先用了在减a[n] = null; //为什么要这一步return item;}public int size() {return n;}public boolean isEmpty() {return n == 0;}}
注意:主要是栈入栈出的核心代码以及扩容的说明,栈入是n++,而栈出为n--,同时还要把这个元素的空间释放掉,n为栈存储的元素个数。
相关文章:
数据结构与算法-栈(LIFO)(经典面试题)
一:面试经典 1. 如何设计一个括号匹配的功能?比如给你一串括号让你判断是否符合我们的括号原则, 栈 力扣 2. 如何设计一个浏览器的前进和后退功能? 思想:两个栈,一个栈存放前进栈&…...
NSI45030AT1G LED驱动器方案为汽车外部及内部照明恒流稳流器(CCR)方案
关于线性恒流调节器(CCR):是一种用于控制电流的稳定输出。它通常由一个功率晶体管和一个参考电流源组成。CCR的工作原理是通过不断调节功率晶体管的导通时间来维持输出电流的恒定。当输出电流超过设定值时,CCR会减少功率晶体管的导…...
uni-app中使用pinia
目录 Pinia 是什么? uni-app 使用Pinia main.js 中引用pinia 创建和注册模块 定义pinia方式 选项options方式 定义pinia 页面中使用 pinia选项options方式 函数方式 定义pinia 页面中使用 函数方式 定义的pinia Pinia 是什么? Pinia࿰…...
Spring之事务管理
文章目录 前言一、事务及其参数含义1.事务的四个特性2.事务的传播行为(propagation)3.事务隔离性4.事务的隔离级别(ioslation)5.timeout(超时)6.readOnly(是否只读)7.rollbackFor&am…...
linux常见的mysql问题
当涉及到MySQL在Linux系统上的常见问题时,以下是10个经常遇到的问题及其解答: 无法连接到MySQL服务器。 确保MySQL服务器正在运行:可以使用systemctl status mysql或service mysql status命令检查MySQL服务状态。确保MySQL服务器网络设置正确…...
常见分辨率时序信息
分辨率列表 分辨率一:640x480(逐行) 分辨率二:800x600(逐行) 分辨率三:1024x768(逐行) 分辨率四:大名鼎鼎720P(逐行) 注:选择720P@30帧的,需拉长HOR TOTAL TIME 分辨率五:1280x800(逐行) 分辨率六:1280x960(逐行...
机器人CPP编程基础-05完结The End
非常不可思议……之前四篇博文竟然有超过100的阅读量…… 此文此部分终结,没有继续写下去的必要了。 插入一个分享: 编程基础不重要了,只要明确需求,借助AI工具就能完成一个项目。 当然也不是一次成功,工具使用也需要…...
数据库应用系统DBAS功能设计与实施(三级数据库)
目录 一、了解软件体系结构及设计过程 1、软件体系结构与设计过程 2、软件设计过程 二、了解DBAS总体设计 1、DBAS体系结构设计 2、软件体系结构设计 3、软硬件选型与配置设计 4、业务规则初步设计 三、了解DBAS功能概要设计 1、表示层概要设计 2、业务逻辑层概要设计…...
快速幂典型
题目描述 求 a 乘 b 对 p 取模的值,其中 1≤a,b,p≤1018。 输入描述: 第一行a,第二行b,第三行p。 输出描述: 一个整数,表示abmodp的值。 示例1 输入 2 3 9 输出 6 #include<bits/stdc.h> using namespace std; t…...
计算机竞赛 python+opencv+机器学习车牌识别
0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 基于机器学习的车牌识别系统 🥇学长这里给一个题目综合评分(每项满分5分) 难度系数:4分工作量:4分创新点:3分 该项目较为新颖,适…...
解决电脑声音正常但就是某些游戏没声音问题
电脑声音正常,玩普遍游戏也正常,就有游戏不出声音 详细介绍经过,不喜欢的请直接跳 第三部分。 一、先说下起因现象。 1 大富翁11 没声音。 前段时间无聊怀旧就买了个大富翁11玩玩,近二十年前的老台式机正常无问题。后来想在性能…...
【UniApp开发小程序】小程序首页(展示商品、商品搜索、商品分类搜索)【后端基于若依管理系统开发】
文章目录 界面效果界面实现工具js页面首页让文字只显示两行路由跳转传递对象将商品分为两列显示使用中划线划掉原价 后端商品controllerservicemappersql 界面效果 【说明】 界面中商品的图片来源于闲鱼,若侵权请联系删除关于商品分类页面的实现,请在我…...
Redis 持久化及集群架构
Redis 持久化及集群架构 本篇技术博文将深入探讨 Redis 持久化机制的原理、配置和使用方式。我们将介绍两种常用的持久化方式:RDB 持久化和 AOF 持久化。您将了解到它们的工作原理、优缺点以及如何根据需求选择合适的持久化方式。 通过深入学习 Redis 持久化及集群…...
FPGA + WS2812采灯控制
文章目录 一、WS2812C-2020-V11、产品概述2、引出端排列及功能3、数据传输时间4、数据传输方法 二、使用WS2812C显示图片1、静态显示2、动态显示 一、WS2812C-2020-V1 1、产品概述 WS2812C-2020-V1是一个集控制电路与发光电路于一体的智能外控LED光源;其外型采用最…...
【视频】使用OBS将MP4推流至腾讯云直播
1、下载OBS OBS官网:https://obsproject.com/ OBS支持Win、Mac、Linux,如果下载速度很慢,建议使用迅雷下载 2、OBS推流设置 2.1 添加场景 默认会有一个“场景”,如果想继续添加可以点击“+”按钮 2.2 添加媒体源 1)点击“来源”窗口中“+”按钮 2)支持的媒体源如…...
Vue基本知识
一、vue入门 Vue为前端的框架,免除了原生js的DOM操作。简化书写。 基于MVVM的思想,实现数据的双向绑定,使编程的重点放在数据上。 1、引入vue.js文件 2、定义vue核心对象,定义数据模型 3、编写视图 //1、引入vue.js <scr…...
item_get_sales-获取商品销量详情
一、接口参数说明: item_get_sales-获取商品销量详情,点击更多API调试,请移步注册API账号点击获取测试key和secret 公共参数 请求地址: https://api-gw.onebound.cn/taobao/item_get_sales 名称类型必须描述keyString是调用key(…...
LangChain手记 Memory
整理并翻译自DeepLearning.AILangChain的官方课程:Memory Memory 使用open ai的API调用GPT都是单次调用,所以模型并不记得之前的对话,多轮对话的实现其实是将前面轮次的对话过程保留,在下次对话时作为输入的message数组的一部分&…...
linux下安装.run后缀名文件
1.文件传输 对于大文件,不能直接拖拽,可以借助工具,例如WinSCP 创建会话时,需要提供虚拟机的主机名,可以采取输入ifconfig的命令,如图所示: ifconfig(接口配置)命令在 …...
Angular 性能优化实战
Angular 性能优化实战 Angular 是一个非常强大的前端框架,但是如果不注意性能优化,应用程序可能会变得非常慢并增加加载时间。 以下是一些Angular性能优化经验的实战建议: 1. 使用 OnPush 变更检测策略 默认情况下,Angular检查…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
