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

栈和队列(1)——栈

栈的基本概念

1. 栈的定义:只允许在一端进行插入或删除操作的线性表(可以理解为操作受限的线性表)。

2. 栈的特点:后进先出(LIFO)。

3. 栈的基本操作:初始化、销毁、进栈、出栈、读栈顶元素等。

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

栈的常考题型:进栈顺序与出栈顺序的关系。

n个不同的元素进栈,出栈元素不同排列的个数为\frac{1}{n+1}\textrm{C}_{2n}^{n}

栈的顺序存储实现(顺序栈)

顺序存储:给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType)。

顺序栈的定义

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态链表中存放栈中元素int top; //指向栈顶元素
} SqStack;

我们通过top的值指向栈顶元素,即top的范围数组索引值[0,n-1]。因此如果栈是空栈,就令top=-1。

顺序栈的初始化与判断栈空

void InitStack(SqStack &S){S.top==-1; //初始化栈顶指针
}
bool StackEmpty(SqStack S){if(S.top==-1)return true;elsereturn false;
}

新元素入栈

bool PushStack(SqStack &S,ElemType x){if(S.top==MaxSize-1) //判断是否满栈return false;S.data[++S.top]==x;return true;
}

由于S.top是索引指向当前的栈顶位置,因此S.data[++S.top]==x,而不是S.data[S.top++]==x。对于后者我们可以采取另一种方式——让top指向下一个可以插入的位置,这时需要将top初始化为0,判断栈满的条件也变成了:top==MaxSize。

出栈

bool PopStack(SqStack &S,ElemType &x){if(S.top==-1) //栈空,报错return false;x=S.data[S.top--];return true;
}

读取栈顶元素

bool GetTop(SqStack S,ElemType &x){if(S.top==-1)return false;x=S.data[S.top]; //记录栈顶元素,引用返回return true;
}

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

共享栈

共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间;
两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。

栈满的条件:top0+1=top1;(top是int类型,是数组的索引值)

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0; //0号栈栈顶指针int top1; //1号栈栈顶指针
} ShStack;
void InitStack(ShStack &S){S.top0=-1;S.top1=MaxSize;
}

链栈

1. 栈的链式存储实现通过单链表模拟,进栈采用头插法。

2. 出栈操作对应单链表的删除操作,需对头结点进行“后删”处理。

3. 链栈定义及初始化,带头结点的链栈便于操作。

#include<stdlib.h>
#include<stdio.h>#define MAXSIZE 10typedef int ElemType;typedef struct Linknode {ElemType data;struct Linknode*next;
}*LiStack;

带头结点的链栈

//初始化
void InitLiStack(LiStack &s){s=(Linknode*)malloc(sizeof(Linknode));if(s==NULL){printf("内存分配失败!\n");return ;}s->next=NULL;printf("空间申请成功!\n");
} //销毁
void DestryLiStack(LiStack &s){Linknode* p=s->next;while(p!=NULL){Linknode* r=p;p->next=r->next;free(r);}free(s);printf("销毁成功!\n");
} //入栈
void PushLiStack(LiStack &s,ElemType e){Linknode* r=(Linknode*)malloc(sizeof(Linknode));r->data=e;r->next=s->next;s->next=r;printf("插入节点成功!\n"); 
} //出栈
void PopLiStack(LiStack &s,ElemType &e){if(s->next==NULL){printf("栈空!\n");return;}Linknode* p=s->next;e=p->data;s->next=p->next;free(p);printf("出栈成功!\n"); 
} //获取栈顶节点
Linknode* GetElem(LiStack &s,ElemType &e){if(s->next==NULL){printf("栈空!\n");return NULL;}Linknode* p=s->next;e=p->data;
} 

不带头结点的链栈

//初始化
void InitLiStack(LiStack &s){s=NULL;printf("申请空间成功!\n"); 
} //销毁
void DestryLiStack(LiStack&s){Linknode* p=s;while(p->next!=NULL){Linknode* r=p;p=r->next;free(r);}//最后一个节点特殊处理free(p); printf("销毁成功!\n");
} //入栈
void PushLiStack(LiStack &s,ElemType e){//如果开始没有节点,特殊处理 if(s==NULL){Linknode* r=(Linknode*)malloc(sizeof(Linknode));r->data=e;r->next=NULL;s=r;printf("插入节点成功!\n"); return ; } Linknode* r=(Linknode*)malloc(sizeof(Linknode));//首先将头结点的值修改为要插入的值e,将r->data=s->data,最后直接在头结点后面插入节点r即可 r->data=s->data;s->data=e;r->next=s->next;s->next=r;printf("插入节点成功!\n"); 
} //出栈
void PopLiStack(LiStack &s,ElemType &e){if(s==NULL){printf("栈空!\n");return;}//只有一个节点的时候特殊处理 if(s->next==NULL){e=s->data; free(s);return ;} Linknode* p=s;e=p->data;s->next=p->next;free(p);printf("出栈成功!\n"); 
} //获取栈顶节点
Linknode* GetElem(LiStack &s,ElemType &e){if(s==NULL){printf("栈空!\n");return NULL;}Linknode* p=s;e=p->data;
} 

相关文章:

栈和队列(1)——栈

栈的基本概念 1. 栈的定义&#xff1a;只允许在一端进行插入或删除操作的线性表&#xff08;可以理解为操作受限的线性表&#xff09;。 2. 栈的特点&#xff1a;后进先出&#xff08;LIFO&#xff09;。 3. 栈的基本操作&#xff1a;初始化、销毁、进栈、出栈、读栈顶元素等…...

Java中的反射(Reflection)

先上两张图来系统的看一下反射的作用和具体的实现方法 接下来详细说一下反射的步骤以及之中使用的方法&#xff1a; 获取Class对象&#xff1a; 要使用反射&#xff0c;首先需要获得一个Class对象&#xff0c;该对象是反射的入口点。可以通过以下几种方式获取Class对象&#x…...

【IC验证】linux系统下基于QuestaSim的systemverilog仿真TCL命令

linux系统下基于QuestaSim的systemverilog仿真TCL命令 一.终端打开QuestaSim二.QuestaSim中TCL脚本指令1.仿真库的创建&#xff08;vlib&#xff09;-非必要2.编译命令&#xff08;vlog&#xff09;3.仿真命令&#xff08;vlog&#xff09;4.运行命令&#xff08;run&#xff0…...

Python图像处理库PIL,实现旋转缩放、剪切拼接以及滤波

文章目录 切割缩放和旋转拼接 PIL的Image类&#xff0c;提供了一些常用的图像处理方法。 切割缩放和旋转 PIL可以很方便地实现如下效果 代码如下 from PIL import Image path lena.jpg img Image.open(path) # 读取 img.resize((50, 50), resampleImage.Resampling.NEARE…...

xhr的readyState和status

XMLHttpRequest&#xff08;XHR&#xff09;对象中的readyState和status用于监控异步 HTTP 请求的状态。它们分别表示请求的当前阶段和服务器的响应状态。 readyState 用于判断请求所处的阶段&#xff0c;确保数据完全接收。 status 用于判断请求的结果状态&#xff08;如200表…...

Rust 力扣 - 238. 除自身以外数组的乘积

文章目录 题目描述题解思路题解代码题解链接 题目描述 题解思路 这题主要有个关键点&#xff0c;就是元素能取0&#xff0c;然后我们分类讨论元素为0的数量 如果数组中存在至少两个元素为0&#xff0c;则每个元素的除自身以外的乘积为0如果数组中仅存在一个0&#xff0c;则为…...

【Vue框架】基础语法练习(1)

其实更多知识点已经在Vue.js官网十分清楚了&#xff0c;大家也可以去官网进行更细节的学习 https://cn.vuejs.org/ 说明&#xff1a;目前最新是Vue3版本的&#xff0c;但是Vue2已经深得人心&#xff0c;所以就是可以支持二者合用。它们最大的区别就是Vue3是组合式API&#xf…...

开源一款基于 JAVA 的仓库管理系统,支持三方物流和厂内物流,包含 PDA 和 WEB 端的源码

大家好&#xff0c;我是一颗甜苞谷&#xff0c;今天分享一款基于 JAVA 的仓库管理系统,支持三方物流和厂内物流,包含 PDA 和 WEB 端的源码。 前言 在当前的物流仓储行业&#xff0c;企业面临着信息化升级的迫切需求&#xff0c;但往往受限于高昂的软件采购和维护成本。现有的…...

开源一套基于若依的wms仓库管理系统,支持lodop和网页打印入库单、出库单的源码

大家好&#xff0c;我是一颗甜苞谷&#xff0c;今天分享一款基于若依的wms仓库管理系统&#xff0c;支持lodop和网页打印入库单、出库单的源码。 前言 在当今快速发展的商业环境中&#xff0c;库存管理对于企业来说至关重要。然而&#xff0c;许多企业仍然依赖于传统的、手动…...

HTML+JavaScript案例分享: 打造经典俄罗斯方块,详解实现全过程

在本文中,我们将深入探讨如何使用 JavaScript 实现经典的俄罗斯方块游戏。俄罗斯方块是一款广为人知的益智游戏,通过操纵各种形状的方块,使其在游戏区域内排列整齐,以消除完整的行来获得分数。 效果图如下: 一、游戏界面与布局 我们首先使用 HTML 和 CSS 来创建游戏的界面…...

【网页布局技术】项目五 使用CSS设置导航栏

《CSSDIV网页样式与布局案例教程》 徐琴 目录 任务一 制作简单纵向导航栏支撑知识点1&#xff0e;合理利用display:block属性2&#xff0e;利用margin-bottom设置间隔效果3&#xff0e;利用border设置特殊边框 任务二 制作简单横向导航栏任务三 制作带图片效果的横向导航栏任务…...

自学网络安全,网络安全入门学习路线,收藏这篇就够了

在当今高度数字化的时代&#xff0c;网络安全已经成为了一个至关重要的领域。随着网络威胁的不断演变和增长&#xff0c;对于专业网络安全人才的需求也在急剧上升。对于那些对网络安全充满热情并且渴望自学成才的人来说&#xff0c;制定一个系统、全面且高效的学习路线和规划是…...

React Query已过时?新一代请求工具横空出世

大家好&#xff01;今天我想和你们聊聊一个让我兴奋不已的话题 —— 分页列表请求策略。你们知道吗&#xff1f;这个策略真的帮了我大忙&#xff01;它不仅让我的代码更简洁&#xff0c;还大大提升了用户体验。说实话&#xff0c;每次用到这个功能&#xff0c;我都忍不住赞叹。…...

视频怎么进行格式转换?6款视频转换MP4格式的免费软件!

在数字时代&#xff0c;视频格式的多样性为我们提供了丰富的观看和编辑选择&#xff0c;但同时也带来了格式不兼容的困扰&#xff1a;MOV、AVI、WMV、MKV……这些格式多多少少都会遇到因不兼容而无法播放或下载分享的场景。当你想要将视频文件从一种格式转换为另一种格式&#…...

智能文档处理平台:免费体验智能化医疗信息提取

前提&#xff1a;医疗行业信息碎片化问题普遍&#xff0c;手工数据录入效率低且易错&#xff0c;导致数据管理难度大。本系统可帮助医疗机构在信息管理上迈向智能化&#xff0c;优化流程并提升效率。 系统概述&#xff1a; 思通数科推出的智能文档处理系统&#xff0c;专为解…...

Java 中 InputStream 的使用:try-with-resources 与传统方式的比较

在 Java 中&#xff0c;处理输入输出流时&#xff0c;确保资源的正确管理至关重要。特别是 InputStream 这样的流&#xff0c;一旦使用完成&#xff0c;必须正确关闭以释放资源。本文将对两种常见的资源管理方式进行比较&#xff1a;try-with-resources 语句和传统的 try-catch…...

【MATLAB源码-第271期】基于matlab的雷达发射回波模拟,包括匹配滤波,加窗旁瓣控制,以及MTD处理。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 雷达系统是一种广泛应用于目标探测和跟踪的技术&#xff0c;其核心在于发射电磁波并分析返回信号。本文将探讨雷达发射波形、回波信号的模拟、匹配滤波的过程、加窗控制旁瓣的策略以及慢时间MTD处理的整体系统框架。 一、雷…...

Linux系统编程——信号量

一、信号量的定义和原理 1、概念 原子操作&#xff1a;不可中断的一个或者一系列的操作&#xff0c;即一件事要么做要么不做。临界资源&#xff1a;不同进程能够看到的一份公共资源&#xff0c;一次只能被一个进程使用。PV操作&#xff1a;由于信号量只能进行两种操作等待和发…...

Oracle索引问题汇总

一、oracle 数据库TIMESTAMP 时间字段&#xff0c;设置索引后&#xff0c;通过该字段进行排序&#xff0c;索引排序不生效问题 1. 记录下在工作中遇到的一次索引问题 问题描述&#xff1a; 数据库&#xff1a;oracle&#xff1b; 日志记录表中的一个创建时间&#xff08;create…...

基于QT用工厂模式实现串口通信与网络通信激光器的控制

配置文件网络配置:IP+Port 串口配置:端口号+波特率 首先,我们需要创建一个配置文件 config.ini,内容如下: [SerialLaser] portName = COM1 baudRate = 9600[NetworkLaser] ipAddress = 192.168.1.1 port = 1234两类激光器的实现: #include <QCoreApplicat…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...