堆栈与深度优先搜索基础知识

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项目



这篇关于堆栈与深度优先搜索基础知识的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程