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

栈和队列修炼指南(基本操作+OJ练习)

栈和队列修炼指南

1. 栈

1. 1 概念及结构

  • 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶,另一端为栈底

  • 栈中的数据元素遵守后进先出原则(LIFO)原则

  • 压栈:栈的插入操作称为进栈/压栈/入栈,其位置在栈顶

  • 出栈:栈的删除操作称为出栈,其位置也在栈顶

1.2 分类(数组栈和链式栈)

数组栈(推荐方式,因为在数组尾插代价更小)

链式栈:相较数组栈无优势,且一般将链表尾作为栈底,链表头作为栈顶(单链表情况下)

1.3 数组栈

1.3.1 结构的定义

typedef int STElemType;
typedef struct Stack
{STElemType *data;	//动态栈int top;int capacity;
}ST;

1.3.2 初始化

void StackInit(ST *pt)
{pt->data = (SElemType *)malloc(N*sizeof(SElemTyp  e));if (!pt->data){perror("malloc");exit(1);}pt->capacity = N;	//N表示初始的最大容量pt->top = 0;	//此时top指向的是栈顶元素的下一个位置,也可以定义为pt->top=-1,这样,top就是指向栈顶元素
} 

1.3.3 销毁

void StackDestroy(ST *pt)
{free(pt->data);pt->top=pt->capacity=0;
} 

1.3.4 判断栈是否为空

bool StackEmpty(ST *pt)
{return pt->top==0; 	//若为真即栈为空,则返回1,否则返回0
} 

1.3.5入栈

void StackPush(ST *pt,SElemType x)
{if(pt->top==pt->capacity)			//如果容量已满{pt->capacity *= 2;		//将容量扩为原来的两倍ST* temp = realloc(pt->data, pt->capacity*sizeof(SElemType));if(!temp){perror("malloc");exit(1);}pt->data = temp;}//入栈pt->data[pt->top]=x;pt->top++;
}

1.3.6 出栈

void StackPop(ST *pt) 
{assert(!stackEmpty(pt));	//栈不能为空//出栈pt->top--;
}

1.3.7 返回栈顶元素

SElemType StackTop(ST *pt)
{assert(!stackEmpty(pt));	//栈不能为空return pt->data[pt->top-1]; 
} 

1.3.8 返回栈的元素个数

int StackSize(ST *pt)
{return pt->top;
} 

1.3.9 将栈的元素全部取出

void StackPrint(ST *pt)
{assert(!stackEmpty(pt));	//栈不能为空while(!StackEmpty(pt)){printf("%d ",StackTop(pt));	//遵循先入后出原则,从上往下取pt->top--;}
} 

1.4 练习

学习完栈的基本概念和相关操作后,你可以利用栈的特性做下面的OJ题:

有效括号序列👉题目解析

逆波兰表达式求值👉题目解析

删除字符串中的所有相邻重复项👉题目解析

包含min函数的栈👉题目解析


2. 队列

2.1 概念及结构

  • 队列:只允许在一端进行入数据操作,在另一端进行删除数据操作的特殊线性表
  • 遵循先进先出的原则FIFO
  • 入队列:进行插入操作的一段叫做队尾
  • 出队列:进行删除操作的一段叫做队头
    在这里插入图片描述

2.2. 分类(数组队列和链队列)

数组队列:由于出队列出的是队头元素,因此数组队列出数据的效率低下,不推荐使用

链队列:入和出数据的效率都很高,是队列常用的表示法

2.3 链队列

2.3.1 结构的定义

typedef int QDataType;	//存储的数据类型typedef struct QueueNode	//链队列的节点
{struct QueueNode *next;QDataType data;
}QueueNode;typedef struct Queue	//定义存放指向队头,队尾指针的结构体
{QueueNode *head;	//指向队头QueueNode *tail;	//指向队尾
}Queue;

2.3.2 初始化

void QueueInit(Queue *pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}

2.3.3 销毁

void QueueDestroy(Queue *pq)
{QueueNode *cur = pq->head;	//定义临时变量while (cur){  pq->head = pq->head->next;	//链表下滑free(cur);		//释放空间cur = pq->head;	//更新临时变量} pq->tail = NULL;	//空间释放完毕后head已经为空,但tail成为了野指针,所以要置空
}

2.3.4 判断队列是否为空

bool QueueEmpty(Queue *pq) 
{assert(pq);return pq->head == NULL;
}

2.3.4 入队

void QueuePush(Queue *pq,QDataType x)
{assert(pq);QueueNode *newnode=(QueueNode *)malloc(sizeof(QueueNode));		//创建新节点if (NULL == newNode){perror("malloc");exit(1);}newnode->data=x;newnode->next=NULL;if(QueueEmpty(pq))	//如果队列为空{pq->head=newnode;	//使队头、队尾指针同时指向新节点pq->tail=newnode;}else{pq->tail->next=newnode;	//使队尾指针的指向下一个节点的指针指向新节点pq->tail=newnode;	//更新队尾指针}
}

2.3.5 出队

void QueuePop(Queue *pq) 
{assert(pq);assert(!QueueEmpty(pq));	//队列不能为空QueueNode *cur=pq->head;	//定义临时变量保存队头指针pq->head=pq->head->next;	//使队头指针指向下一个节点free(cur);		//释放原来的队头if(pq->head==NULL)pq->tail=NULL;	//如果节点已经全部出队,则要将队尾指针置空,防止形成野指针
}

2.3.6 返回队头/队尾数据域

//返回队头元素
QDataType QueueFront(Queue *pq)	 
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//返回队尾元素 
QDataType QueueBack(Queue *pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

2.3.7 返回队列元素个数

int QueueSize(Queue *pq)
{QueueNode *cur=pq->head;int size=0;while(cur){size++;cur=cur->next;}return size;
}
//也可以在队列结构体中增加size变量,每入队一个size就加一

2.4 练习

队列常常被用来对一些复杂数据结构的广度优先遍历,但由于目前还未学习,故不作深入讨论

除了这种最基本的只能从队尾插入数据,从队头删除数据的队列外,其实还有循环队列、双端队列、单调队列等许多复杂但功能强大的队列结构,如果小伙伴们感兴趣,也可以看看:

👉循环队列

👉双端队列 & 单调队列

如果小伙伴们愿意挑战,也可以做一做滑动窗口的最大值👉题目解析


3. 栈和队列的相互表示

这里拿两道OJ题来进行说明:

用两个栈表示队列👉题目解析

用两个队列表示栈👉题目解析

相关文章:

栈和队列修炼指南(基本操作+OJ练习)

栈和队列修炼指南 1. 栈 1. 1 概念及结构 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶,另一端为栈底。 栈中的数据元素遵守后进先出原则(LIFO)原则 压栈:栈的…...

伪类和伪元素有何区别?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 伪类(Pseudo-class)⭐ 伪元素(Pseudo-element)⭐ 区别总结⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前…...

自动测试框架airtest应用一:将XX读书书籍保存为PDF

一、Airtest的简介 Airtest是网易出品的一款基于图像识别和poco控件识别的一款UI自动化测试工具。Airtest的框架是网易团队自己开发的一个图像识别框架,这个框架的祖宗就是一种新颖的图形脚本语言Sikuli。Sikuli这个框架的原理是这样的,计算机用户不需要…...

ValueError:The following settings are not supported :{‘username‘: ‘neo4j“}

py2neo版本不同所导致的问题,下面我通过一段代码说明该问题。 import py2neoif py2neo.__version__ 4.3.0:graph Graph(http://localhost:7474, username config.neo4j_username, password config.neo4j_password) elif py2neo.__version__ 2021.2.3:graph G…...

360安全卫士右下角广告弹窗太多怎么彻底关闭?

360安全卫士右下角广告弹窗太多怎么彻底关闭? 1、卸载360安全卫士,选择继续卸载,并点击下一步; 2、选择广告弹窗太多,并点击下一步; 3、然后被告知升级极速版永久去广告,可以点击一键去广告。 …...

链表有无环以及确定入环口详解

142.环形链表 II 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测…...

chrome插件开发实例08- 使用Vue.js开发chrome插件

目录 背景 演示 功能介绍 插件下载 注意写法: 背景 将 下面的两个插件 改写成vue.js , elementui 实现chrome插件开发实例0...

PCL 计算外接圆的半径

目录 一、算法原理1、计算公式2、主要函数3、源码解析二、代码实现三、结果展示四、参考链接本文由CSDN点云侠原创,原文链接。爬虫自重。 一、算法原理 1、计算公式...

Matlab实现神经网络SOM算法(附上完整仿真源码)

神经网络SOM算法是一种基于自组织的无监督学习算法,其全称为Self-Organizing Map,可以用来对数据进行聚类和可视化。本文将介绍如何使用Matlab实现神经网络SOM算法。 文章目录 一、准备工作二、数据准备三、SOM算法实现四、聚类结果分析五、总结六、完整…...

【遍历】非递归法 二叉树的前中后序遍历

文章目录 非递归法前序遍历后序遍历中序遍历 递归法DFS 非递归法 通过栈Stack来模拟递归。 前序遍历 LeetCode 144 前序遍历:1 2 3 定义:存放答案的List、栈Stack 将root入栈出栈:node,为null则舍弃将node放入list将node.r…...

Python将tiff转换成png

文章目录 问题描述解决方案压缩并转换参考文献 问题描述 base64 的 image/tiff 无法在页面直接展示,将其转换为 image/png 解决方案 from io import BytesIOfrom PIL import Imagewith Image.open(a.tiff) as image:bytesIO BytesIO()image.save(bytesIO, format…...

【大数据】-- 部署 Flink kubernetes operator

目录 1.说明 1.1 版本 1.2 kubernetes 环境 1.3 参考 2.安装步骤 2.1 安装本地 kubernetes 环境...

能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式

【计算机组成原理错题】能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式。 A.立即寻址 B.隐含寻址 C.间接寻址 D.基址寻址 正确答案:B 因为另一个操作数来自于累加器ACC,而这种方式属于隐含寻址。 在指令…...

数据库数据恢复-Oracle数据库数据恢复案例

数据库数据恢复环境: Oracle数据库ASM磁盘组有4块成员盘。 数据库故障&分析: Oracle数据库ASM磁盘组掉线 ,ASM实例无法挂载,用户联系我们要求恢复oracle数据库。 数据库数据恢复工程师拿到磁盘后,先将所有磁盘以只…...

对于msvcr120.dll丢失的问题,分享几种解决方法

msvcr120.dll的作用是提供一系列的运行时函数和功能,以便应用程序能够正常运行。这些函数和功能包括内存管理、异常处理、输入输出操作、数学运算等。在没有这个库文件的情况下,应用程序可能无法正常启动或执行特定的功能,甚至会出现错误提示…...

网络安全进阶学习第十三课——SQL注入Bypass姿势

文章目录 一、等号被过滤二、substr、mid等被过滤三、逗号被过滤四、and/or被过滤五、空格被过滤五、其他绕过方式 一、等号被过滤 1、like&#xff0c;rlike语句&#xff0c;其中rlike是正则2、大于号>&#xff0c;小于号<3、符号<>&#xff1a;<>为不等于…...

vue3 provide inject实现强制刷新

1、在 App.vue 文件里写入 provide 的方法 <template> <div id"app"><keep-alive> <router-view v-if"isRouterAlive"></router-view></keep-alive> </div> </template> <script> export default …...

Neo4j笔记-数据迁移(导出/导入)

这里先说明以下几点&#xff1a; Neo4j在4.0下版本默认的库名是&#xff1a;graph.db Neo4j在4.0上版本默认的库名是&#xff1a;neo4j.db 不管是Neo4j&#xff0c;还是Neo4j Desktop&#xff0c;都会在bin目录下有neo4j、neo4j-admin软件。在conf目录下&#xff0c;有neo4j.…...

请求转发和请求重定向

目录 1. 定义层面 2. 请求方层面 3. 数据共享层面 4. 最终 url 层面 5. 代码实现层面 请求转发 请求重定向 在Java中&#xff0c;跳转网页的方式有两种&#xff0c;一种是请求转发&#xff0c;另一种是请求重定向&#xff0c;而实际上&#xff0c;这两种方式是有着明显…...

TOMCAT的多实例部署和动静分离

tomcat的多实例 动静分离 排错小工具&#xff1a; telnet工具&#xff1a;yum -y install telnet telnet工具用于测试端口是否正常 telnet 20.0.0.101 80Tomcat多实例部署&#xff1a; 一台服务器上有多个tomcat的服务 1.安装好 jdk 2.安装 tomcat cd /opt tar zxvf apache-…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...