堆栈与深度优先搜索基础知识
2022/9/16 23:18:29
本文主要是介绍堆栈与深度优先搜索基础知识,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
堆栈
堆栈(Stack):简称为栈。一种线性表数据结构,是一种只允许在表的一端进行插入和删除操作的线性表。
栈有两种存储表示方法:「顺序栈」 和 「链式栈」。
- 「顺序栈」:即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素,同时使用指针
top
指示栈顶元素在顺序栈中的位置。 - 「链式栈」:即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前,并使用栈顶指针
top
指示栈顶元素,top
永远指向链表的头节点位置。
栈作为一种线性表来说,理论上应该具备线性表所有的操作特性,但由于「后进先出」的特殊性,所以针对栈的操作进行了一些变化。尤其是插入操作和删除操作,改为了入栈(push)和出栈(pop)。
堆栈的基本操作如下:
-
初始化空栈:创建一个空栈,定义栈的大小
size
,以及栈顶元素指针top
。 -
判断栈是否为空:当堆栈为空时,返回
True
。当堆栈不为空时,返回False
。一般只用于栈中删除操作和获取当前栈顶元素操作中。 -
判断栈是否已满:当堆栈已满时,返回
True
,当堆栈未满时,返回False
。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。 -
插入元素(进栈、入栈):相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针
top
的指向位置。 -
删除元素(出栈、退栈):相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针
top
的指向位置。 -
获取栈顶元素:相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是,该操作并不改变栈顶指针
top
的指向位置。
深度优先搜索基础
深度优先搜索算法**(Depth First Search):英文缩写为 DFS。是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点,会尽可能深的搜索树的分支。当节点
v
的所在边都己被探寻过,搜索将回溯到发现节点v
的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。
深度优先搜索使用的是回溯思想,这种思想很适合使用「递归」来实现。而递归对问题的处理顺序,遵循了「后进先出」的规律。所以递归问题的处理,需要借助「堆栈」来实现。
参考源:gitee.com-leetcode-py项目
这篇关于堆栈与深度优先搜索基础知识的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-15Springboot应用的多环境打包学习
- 2024-10-15Springboot应用的生产发布学习
- 2024-10-15创建Springboot项目学习:新手入门教程
- 2024-10-15创建springboot项目学习:新手入门教程
- 2024-10-14Java创业学习:新手入门教程
- 2024-10-14JAVA创业学习:新手入门教程
- 2024-10-14Java创业学习:从零开始的Java编程教程
- 2024-10-14Java对接阿里云智能语音服务学习
- 2024-10-14JAVA对接阿里云智能语音服务学习教程
- 2024-10-14Java副业学习:从入门到实战的简单教程