关于栈和队列随想
2023-09-27 14:20:25 时间
1 在算法中栈和队列的地位
在算法中,栈和队列就是一个缓存,缓存那些对自己还有用的元素,还不用扔掉的元素。
比如对图的深度优先搜索,搜到某一层时,还只是访问了该元素的一个邻接节点时,是不能随便扔出栈的,因为可能它还有其它的邻接节点,首先它自己肯定是已经被访问了的,但是如果把它扔了,它的其它邻接节点也就被扔了,所以,只有当它的所有的邻接节点也被访问了的时候才可以把它扔掉。
一般情况下,图的深度优先遍历用的是递归,boost graph library中用的就是递归来实现的。不要对递归有偏见,不要对递归的函数调用有偏见,
2 对图进行遍历的时候,如何标记栈中的元素已经被访问的邻接节点和未被访问的邻接节点
图中的每个节点都是有一个label的,并且该label是唯一的,所以,可以弄一个hash表,访问过了的就是true,没有访问的就是false。缺点就是如果用邻接表表示图的话,每次都要遍历一下每个表。
3 邻接表盒邻接矩阵比较
当边比较多的时候,比如满边的时候,用邻接矩阵比较好,因为空间占用上二者一样,但是,邻接矩阵找起邻接关系来更快。
当边比较少的时候,比如没有边的时候,用邻接表会比较好,因为邻接矩阵会有很多空的地方,浪费空间,而邻接表就非常节省空间了。
相关文章
- 【C/C++开发】C++队列缓存的实现
- Spring Boot消息队列应用实践
- 【Rust】标准库-双端队列
- 3-5-表达式求值-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版
- LeetCode_栈_简单_232.用栈实现队列
- 链表实现队列
- 数据结构(C++版)——7-1 队列的实现及基本操作(链栈实现,无上限)
- Laravel/Lumen 使用 redis队列(一)
- 【故障处理】队列等待之enq IV - contention案例
- 剑指 Offer 09. 用两个栈实现队列
- 主流消息队列Kafka和下一代云原生消息平台Pulsar架构分析
- 无锁队列--基于linuxkfifo实现
- ConcurrentQueue<T>高效的线程安全的队列
- uWSGI listen queue 队列溢出的问题
- Linux CFS调度器之队列操作--Linux进程的管理与调度(二十七)