数据结构 3 栈和队列

小咪咪 2022-08-04 13:54 214阅读 0赞

栈和队列也算是 数据类型。  
以为都是在首位操作，栈和队列 克服了 线性表添加删除需要移动大量元素的弱点。

栈仅在尾部进行插入和删除，尾部叫做栈顶， 表头叫做栈底。后进先出。  
last in first out LIFO  
空栈。  
插入叫入栈， 删除元素叫出栈。  
顺序栈，的顺序存储结构是利用一组 地址连续的存储单元，依次存放栈底到栈顶的元素。 top表示栈顶元素的位置，那么 top=0就是空栈。**非空栈的栈顶指针top始终在 栈顶元素的下一个位置。**

代码写的过于聚合，容易造成很高深的错觉，其实，是不容易看出思路来的。

栈的应用  
1，数值转换 [https://github.com/kunpengku/farmer/blob/master/cpp/mod\_2.cpp][https_github.com_kunpengku_farmer_blob_master_cpp_mod_2.cpp]  
2，括号匹配的检验  
3，行编辑程序， 栈用来做 退格功能。  
4，迷宫求解。  
5，表达式求值，算符优先算法。  
任何一个表达式都是由，操作数，操作符，界限符组成。  
括号就是界限符。  
6，栈与 递归  
调用自己的函数 成为递归函数。  
汉诺塔问题。  
函数调用栈：  
在运行被调用函数前，系统要做三件事情：  
1，将所有实参，返回地址传给被调函数保存。  
2，为被调用函数的局部变量分配存储区，  
3，将控制权转移到被调用函数入口。

在被调函数返回前，也要做三件事：  
1，保存计算结果。  
2，释放被调函数的局部变量，  
3，依照保存的返回地址，将控制权交给调用函数。

递归函数方便在 ： 这种编程，不需用户自己，而由系统来管理递归工作栈。

队列就是理想的排队。 这里没有插队的人。  
first in first out FIFO  
在一端插入，另一端删除。  
允许插入的一头叫队尾rear， 允许删除的一头叫 队头front。  
作业队列。  
头节点不是第一个元素。头节点就是头节点。

删除插入，应考虑边界情况。  
在非空队列中，头指针始终指向队头元素， 尾指针始终指向队尾的下一个位置。

[https_github.com_kunpengku_farmer_blob_master_cpp_mod_2.cpp]: https://github.com/kunpengku/farmer/blob/master/cpp/mod_2.cpp