栈的应用

栈是一个线性的数据结构. 它在编程领域有广泛的使用. 比如操作系统会为每个线程分配一个函数调用栈, 用于保存函数内的局部变量.

常见的栈的应用有:

• 函数调用: 用于记录函数返回地址, 当被调用函数执行完后可以将返回值正确还回给函数调用处
• 递归: 递归函数的调用, 通常可以将它们转换成迭代的形式, 这时可以利用栈来存放每次递归调用时的值
• 语法解析: 可以利用栈来检验编程语言中表达式的语法
• 表达式求值: 可以用栈来实现对后缀表达式的求值