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

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

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

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

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...