栈和队列的逻辑结构与线性表相同，但是其运算受到限制，统称为运算受限的线性表。
栈， 先进后出
队列，先进先出

栈的定义

栈顶，唯一能操作端
栈底，另一端
空栈，不含元素

栈的基本运算

栈的基本运算

• 初始化空栈：initStack(S)
• 判栈空：isEmpty(S)
• 入栈：push(S,x)元素x加入栈顶，更新栈顶指针
• 出栈：pop(S)删除栈顶元素，更新栈顶指针
• 读栈顶元素：top(S)返回栈顶元素，但不修改栈顶指针

栈的存储结构

栈有顺序存储、链式存储两种存储结构。

• 顺序存储：用地址连续的存储单元存储，需要设置栈顶指针top。栈的存储空间需要预先申请，存储空间有限，入栈前需判断是否栈满，否则会出现上溢问题。
• 链式存储：用链表存储栈，存储单元地址可连续，也可分散。链表的头指针即为栈顶指针top。不存在上溢问题。

栈的应用

栈的典型应用包括：表达式求值、括号匹配、实现计算机语言、将递归过程转变为非递归过程。

表达式求值

使用栈进行表达式求值
① 将表达式转换为后缀表达式，例如3-42转换成3，4，2，，-
② 从左到右扫描后缀表达式
情况一：遇到运算对象，将其压入栈中
情况二：遇到运算符，从栈顶取出数据，进行计算。所取数据先摆放在运算符的右边，不足以完成计算时，再取出栈顶数据，放在运算符左边。完成计算，将计算结果压入栈中。
③ 不断循环，直到后缀表达式结束。

3，4，2，，-
① 3，4，2压入栈中
② 遇到, 弹出2，4，计算4*2=8，压入栈中
③ 遇到-，弹出8，3，计算3-8=-5，压入栈中
④ 表达式结束，栈顶为计算结果