栈的应用场景和介绍 [数据结构][Java]

栈的应用场景和介绍

栈的介绍:

1. 栈的英文名为: stack
2. 栈是一个先入后出的有序列表
   • 将这种先入后出我们称之为: FILO : First In Last Out
3. 栈(stack)是限制线性表中的元素的插入和删除只能是在线性表的同一端进行的一种特殊的线性表
   • 允许插入和删除结点的一段我们称之为栈顶(TOP)
   • 另一端为固定的一端: 称之为: 栈尾(Bottom)
4. 根据栈的定义可知: 最先放入栈中的元素在栈底,最后放入的元素在栈顶
   • 而对于删除元素刚刚是相反的: 最后放入的元素最早删除,最早放入的元素最后删除

栈的应用场景:

1. 子程序的调用:
   • 在跳往子程序之前,会先将下一个指令的地址存放到堆栈中(这里的堆栈就是我们所说的栈),直到子程序执行完之后再将地址取出,以回到原来的程序中
2. 处理递归调用:
   • 和子程序的调用类似,只是出了存储下一个指令的地址以外,也将参数,区域变量等数据存入到堆栈中
3. 表达式的转换与求值:(实际问题)
   • eg:中缀表达式转后缀表达式 (面试和笔试中经常会考)
4. 二叉树的遍历
5. 图形的深度优先(depth-first)搜索法