数据结构与算法-栈(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检查…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
