3.栈和队列
栈是一种限定只能在表的一端进行插入和删除运算的线性表.
将允许插入或删除的一端称为栈顶, 另一端称为栈底.
栈又称为后进先出 (LIFO) 表.
插入称为进栈, 删除称为退栈.
栈的顺序存储结构称为顺序栈, 类似于顺序表, 顺序栈也使用数组实现.
一般将栈底设置在数组最低端 (下标 0), 并设置栈顶指针指示栈顶位置.
当栈满时, 进栈会导致上溢; 当栈空时, 退栈会导致下溢.
如果将多个栈分配在同一个顺序存储空间内, 则可以相互进行调节, 既节约空间, 又可降低 发生溢出的概率. 比如, 可以将两个栈的栈底分别设在顺序存储空间的两端, 让两个栈各自 向中间延伸.
栈的链式存储结构称为链栈, 它是运算受限的单链表. 不必设置头结点. 链栈可以克 服顺序栈的溢出和空间浪费问题.
栈的应用非常广泛, 只要问题满足 LIFO 原则, 都可使用栈作为数据结构, 如:
- 圆括号匹配的检验.
- 字符串回文的判断.
- 数值转换.
- 通过递归工作栈, 实现递归.
- 实现程序设计语言的函数调用和返回.
队列也是一种操作受限的线性表, 它只允许在表的一端进行插入, 而在另一端进行删除.
插入的一端称为队尾, 删除的一端称为队头. 元素的插入称为入队, 删除称为 出队. 又称队列为先进先出 (FIFO) 表.
队列的顺序存储结构称为顺序队列. 需要设置队头指针 front 和队尾指针 rear.
它们的初值为 0.
- 入队: 将元素插入队尾指针所指位置, 并将队尾指针加 1.
- 出队: 将队头指针加 1, 并返回被删除的元素.
- 判空: 头尾指针相等时队列为空.
如果用数组实现顺序队列, 当队尾指针指向数组最后一个元素时, 继续插入新元素, 则会发 生上溢, 而出队的位置又无法再利用. 为了克服这两个问题,可将数组想象为一个*环状空间 *, 称这种环状数组表示的队列为循环队列:
- 可用求余运算, 判断发生上溢时, 进入下一个循环.
- 队列无论是空是满, 都有
队头指针 == 队尾指针. 因此为了判断队列是空是满, 有几 种常用方法:- 另设一个标志位, 标记队列是空是满.
- 设置计数器记录队列中元素个数.
- 少用一个元素空间, 即
rear所指向的单元始终为空. 约定入队前, 测试rear + 1是否等于头指针. 是则队满.
队列的链式存储结构称为链队列. 对于链队列需增设一个尾指针以方便在表尾做插入操 作. 于是一个链队列就由一个头指针和一个尾指针唯一确定. 为了简化边界条件的处理, 队 头结点之前也附加一个头结点, 并设头指针指向此结点.
用一个带头结点的循环单链表表示队列, 称为循环链队列. 该队列只设一个队尾结点指
针 rear, 不设头指针. 且 rear->next回指到头结点.
我们平时写的计算式如 (8+5)*(7-3), 因为运算符放到操作数中间, 称为**中缀表达式
**.
为了方便计算机处理, 可以把运算符放到操作数后面, 即后缀表达式. 如 8 5 + 7 3 - *, 又叫逆波兰表示法. 要计算该表达式, 可以:
- 从左向右扫描, 直到遇到一个运算符后即开始运算.
- 遇到
+, 计算8 + 5, 得到13, 原计算式变为13 7 3 - *. - 遇见
-, 计算7 - 3, 计算式变为13 4 *. - 遇见
*, 计算13 * 4. 得到了最终结果.
后缀表达式的这种计算规则, 正是运用栈和队列的典型例子:
-
先通过栈和输出队列, 将中缀表达式变为后缀表达式:
从例子中可以看到, 将中缀表达式变为后缀表达式时, 运算符依据优先级从高到低从左 向右的排列. 转换过程如下:
- 顺序扫描中缀表达式, 遇到数字时, 将其送至输出队列中.
- 遇到运算符时, 将栈中所有优先级高于或等于该运算符的运算符弹出, 送至输出队 列, 再将当前运算符入栈.
- 遇到左括号时, 入栈.
- 遇到右括号时, 将靠近栈顶的第一个左括号上面的运算符全部依次弹出, 送至输出 队列中, 再删除栈中的左括号.
-
然后计算后缀表达式:
因为运算符已经按照优先级顺序排好, 所以很容易用计算机实现. 因为计算后缀表达式 时, 最后保存的值最先取出参与运算, 所以需要栈保存中间结果.