栈是一种特殊的线性表，元素的插入和删除被限定在表的一端进行，允许插入和删除的一端称为栈顶，另一端称为栈底，最先入栈的元素在栈底，最后入栈的元素在栈顶。当表中没有元素时，称为空栈。若给定栈：
S=(a1，a2，……，an)
则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，栈结构也称为后进先出线性表，如下图所示。
图3-1栈结构
栈结构在实际编程中有哪些应用呢？表达式求值、函数调用、递归问题、树结构的遍历、图的深度优先搜索都会应用到栈结构，这些应用我们在后面的课程都会讨论。下面重点讨论表达式求值问题。
在编程语言中，表达式是由数值、变量、常量和运算符的组合，它执行计算并返回计算结果。例如计算球体的体积公式：
球体的体积公式是一个表达式，其中“/”、“*”是运算符，4和3是数值常量，“π”、“r”是变量，变量或数值常量称为操作数。
从形式上看，表达式是一个字符序列，对表达式求值要能够正确解析表达式。程序扫描表达式字符序列时，需要从字符序列中解析出操作数、运算符、界限符（表达式的左右括号、结束符等），并按照运算规则执行运算。例如，要对下面的算术表达式求值：
12*（1+6）
表达式求值程序不仅要解析出12、1、6操作数，还要解析出*、+运算符，也要解析出左右小括号。同时还要按照算术四则运算的规则执行运算，即先乘除，后加减；从左算到右；先括号内，后括号外。
为了简述简便，本文仅讨论简单算术表达式的求值问题，运算符也限于加、减、乘、除四中运算符，界限符仅限于小括号。读者不难将它推广到更一般的表达式上。
表达式求值算法的基本思想是建立两个栈结构：一个栈结构存储操作数；一个栈结构存储运算符。算法对表达式字符序列自左向右进行扫描，遇到操作数入操作数栈。遇到运算符，需要将当前运算符与运算符栈的栈顶运算符比较优先级，若栈顶运算符的优先级高于当前运算符，则栈顶运算符出栈并执行运算，计算结果入操作数栈，否则将当前运算符入运算符栈，直至整个表达式求值完毕。
订阅解锁TA的全部专属内容