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

栈(定义,基本操作,顺序存储,链式存储)

目录

  • 1.栈的定义
    • 1.重要术语
    • 2.特点
  • 2.栈的基本操作
  • 3.栈的顺序存储
    • 1.顺序栈的定义
    • 2.基本操作
      • 1.初始化
      • 2.进栈
      • 3.出栈
      • 4.读栈顶
    • 3.共享栈
  • 4.栈的链式存储

1.栈的定义

栈( Stack)是只允许在一端进行插入或删除操作的线性表
一种受限的线性表,只能在栈顶进行插入删除。

1.重要术语

栈顶:允许插入和删除的一端。
栈底:不允许插入和删除的一端。
空栈:对应线性表的空表。
栈顶元素
栈底元素

2.特点

后进先出:Last In First Out (LIFO)

2.栈的基本操作

  1. InitStack(&S):初始化栈。构造一个空栈S,分配内存空间。
  2. DestroyStack(&L):销毁栈。销毁并释放栈S所占用的内存空间。
  3. Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶。
  4. Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。(删除栈顶元素)
  5. GetTop(S,&x):读栈顶元素。若栈S非空,则用x返回栈顶元素。(不删除栈顶元素)
  6. StackEmpty(S):判断一个栈S是否为空。若S为空,则返回true,否则返回false。

n个不同元素进栈,出栈元素不同排列的个数为 1 n + 1 C 2 n n \frac{1}{n+1}C_{2n}^n n+11C2nn
上述公式称为卡特兰(Catalan)数,可采用数学归纳法证明。

3.栈的顺序存储

顺序存储:给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType)
静态数组实现,并需要记录栈顶指针。

1.顺序栈的定义

顺序栈的缺点:栈的大小不可变。

在这里插入图片描述

2.基本操作

1.初始化

在这里插入图片描述

2.进栈

在这里插入图片描述

3.出栈

在这里插入图片描述

4.读栈顶

在这里插入图片描述

3.共享栈

两个栈共享同一片内存空间,两个栈从两边往中间增长。

在这里插入图片描述

栈满的条件: top0 + 1 == top1

4.栈的链式存储

本质上用链式存储实现栈就是只允许在单链表的一段进行插入和删除操作。
进栈对应插入操作,出栈对应删除操作。

在这里插入图片描述

进栈/出栈都只能在栈顶一端进行(链头作为栈顶)。

相关文章:

栈(定义,基本操作,顺序存储,链式存储)

目录 1.栈的定义1.重要术语2.特点 2.栈的基本操作3.栈的顺序存储1.顺序栈的定义2.基本操作1.初始化2.进栈3.出栈4.读栈顶 3.共享栈 4.栈的链式存储 1.栈的定义 栈( Stack)是只允许在一端进行插入或删除操作的线性表。 一种受限的线性表,只能在栈顶进行插…...

在HTML单页面中,使用Bootstrap框架的多选框如何提交数据

1.引入Bootstrap CSS和JavaScript文件&#xff1a;确保在HTML页面的标签内引入Bootstrap的CSS和JavaScript文件。可以使用CDN链接或者下载本地文件。 <link rel"stylesheet" href"https://maxcdn.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css&q…...

当爱好变成职业,会不会就失去了兴趣?

当爱好变成职业&#xff0c;会不会就失去了兴趣&#xff1f; 当兴趣变成职业 1、学习能力变强了&#xff0c;积极主动性增加了。 2、学习努力变现了&#xff0c;赚到的更钱多了。 3、赚钱能力变强了&#xff0c;反过来再次促使兴趣发展&#xff08;兴趣更大了....干劲更足了&…...

3-知识补充-MVC框架

3-知识补充-MVC框架 文章目录 3-知识补充-MVC框架MVC概述M、V、C各自负责功能及常用包MVC框架图非前后端分离框架图前后端分离框架图 MVC概述 MVC&#xff08;Model、View、Controller&#xff09;是软件工程中的一种**软件架构模式&#xff0c;它把软件系统分为模型、视图和控…...

leetcode:141. 环形链表

一、题目 函数原型&#xff1a; bool hasCycle(struct ListNode *head) 二、算法 判断不是环形链表&#xff0c;只需遍历链表找到空结点即可。 判断是环形链表&#xff0c;由于链表是环形的&#xff0c;遍历不会永远不会结束。所以要设置快慢指针&#xff0c;慢指针一次走一步&…...

了解企业邮箱的外观和功能特点

企业邮箱是什么样子的&#xff1f;企业邮箱不是单一产品&#xff0c;而是由一系列电子邮件服务组成的生态系统。这些服务包括但不限于邮件服务器、客户端、安全解决方案等。这些服务共同构成了企业邮箱的基础设施。 在外观上&#xff0c;企业邮箱和个人邮箱没有太大区别。用户通…...

配置阿里云镜像加速器 -docker

1.百度aliyun 2.找到镜像服务ACR 3.搞一个个人版&#xff0c;身份验证一下就行了很简单 4.找到镜像加速器Centos 5.执行下面4条命令&#xff1a;4条命令直接从上面操作文档中粘贴&#xff0c;不容易出错 sudo mkdir -p /etc/docker sudo tee /etc/docker/daemon.json <<…...

11 抽象向量空间

抽象向量空间 向量是什么函数什么是线性推论向量空间 这是关于3Blue1Brown "线性代数的本质"的学习笔记。 向量是什么 可以是一个箭头&#xff0c;可以是一组实数&#xff0c;即一个坐标对。 箭头在高维&#xff08;4维&#xff0c;甚至更高&#xff09;空间&…...

干洗店洗鞋店管理系统app小程序;

干洗店洗鞋店管理系统是一款专业的洗衣店管理软件&#xff0c;集成了前台收费收银系统、会员卡管理系统和财务报表系统等强大功能。界面简洁优美&#xff0c;操作直观简单。这款系统为干洗店和洗衣店提供了成本分析、利润分析、洗衣流程管理等诸多实用功能&#xff0c;用全新的…...

NOIP2023模拟13联测34 总结

NOIP2023模拟13联测34 总结 文章目录 NOIP2023模拟13联测34 总结比赛过程题目A. origen题目大意思路 B.competition题目大意思路 C. tour题目大意 D.abstract题目大意 比赛过程 看了一下题&#xff0c;感觉就 T 2 T2 T2 有一点思路。 T 1 T1 T1 先打一个 30 30 30 分暴力&am…...

Python武器库开发-常用模块之subprocess模块(十九)

常用模块之subprocess模块(十九) subprocess模块介绍 subprocess 模块允许我们启动一个新进程&#xff0c;并连接到它们的输入/输出/错误管道&#xff0c;从而获取返回值。subprocess 它可以用来调用第三方工具&#xff08;例如&#xff1a;exe、另一个python文件、命令行工具…...

java验证 Map 的 key、value 是否可以为空

1、验证示例代码 Map<String, Object> maps new HashMap<>();maps.put("a", "1");maps.put(null, null);maps.put("c", null);System.out.println("maps " maps);Object o maps.get(null);System.out.println("o…...

编写MBR主引导记录

BIOS 检测&#xff0c;初始化硬件。挑一些重要的&#xff0c;能保证计算机能运行那些硬件的基本IO操作。 唤醒BIOS 唤醒BIOS需要知道其入口地址&#xff0c;在最后将跳转到0x7c00处 接电的一瞬间&#xff0c;cs:ip寄存器被初始化为0xF000:0xFFF0&#xff0c;所以等效地址是0…...

从零开始搭建React+TypeScript+webpack开发环境-自定义配置化的模拟服务器

技术栈 我们将使用Node.js和Express.js作为我们的后端框架&#xff0c;以及Node.js的文件系统(fs)模块来操作文件和文件夹。此外&#xff0c;我们将使用Node.js的require和delete require.cache来加载和更新模拟数据。 项目结构 首先&#xff0c;让我们定义一个简单的项目结…...

python 之字典的相关知识

文章目录 字典的基本特点&#xff1a;1. 定义2. 键唯一性3. 可变性4. 键的类型 基本操作&#xff1a;字典的创建1. 花括号 {}2. dict() 构造函数3. 键值对的 dict() 构造函数使用 zip() 函数创建字典&#xff1a;注意事项访问字典中的值修改和添加键值对删除键值对 字典方法&am…...

上下游系统对接的沟通与协作

在工作中&#xff0c;有时会有对接其他部门系统的需求&#xff0c;这种需求虽然不复杂&#xff0c;但是跨部门协作&#xff0c;往往会出现各种难以沟通、协调的情况。 踩的坑多了&#xff0c;就记录下来。 注意&#xff1a;在本文中&#xff0c;A系统调用B系统&#xff0c;A依…...

pytest 的使用===谨记

发现用例的规则 a) 文件test_.py开头和_test.py结尾 b) Test开头的类中test开头的方法&#xff08;测试类不能带有__init__方法&#xff09; c) 模块中test开头的函数&#xff08;可以不在class中&#xff09; 注意点&#xff1a; pytest是以方法为单位发现用例的&#xff0c;你…...

Qt 4.8.6 的下载与安装

Qt 4.8.6 的下载与安装 Qt 4.8.6 的下载与安装下载并解压 MinGW 4.8.2Qt4.8.6 库的安装Qt Creator 3.3.0 的安装配置 Qt Creator测试 官方博客&#xff1a;https://www.yafeilinux.com/ Qt开源社区&#xff1a;https://www.qter.org/ Qt 4.8.6 的下载与安装 学习《Qt Creato…...

图形推理 | 判断推理

文章目录 一、位置规律二、样式规律三、属性规律四、数量规律 一、位置规律 平移 方向&#xff1a;直线&#xff08;上下、左右、斜对角线&#xff09;、绕圈&#xff08;顺逆时针&#xff09;常见步数&#xff1a;恒定、递增&#xff08;等差&#xff09; 旋转 方向&#xff…...

npm的使用

package.json 快速生成package.json npm init -y “version”: “~1.1.0” 格式为&#xff1a;「主版本号. 次版本号. 修订号」。 修改主版本号是做了大的功能性的改动 修改次版本号是新增了新功能 修改修订号就是修复了一些bug dependencies "dependencies": {&…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...