当前位置: 首页 > 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": {&…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...