栈的应用举例

Published: by Creative Commons Licence

栈结构的固有特性：后进先出

数制转换

这是利用栈的后进先出特性的最简单的例子。

使用原因

举例：十进制转八进制

计算过程是从低位到高位顺序产生八进制的各数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。

因此，将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

void conversion() {
    InitStack(S);
    scanf("%d", &N);
    while(N) {
        Push(S, N % 8);
        N /= 8;
    }
    while(!StackEmpty(S)) {
        Pop(S, e);
        print("%d", e);
    }
}

括号匹配的检验

在算法中设置一个栈，每次读入一个括号：

  • 若为右括号
    • 或者使置于栈顶的最急迫的期待得以消解；
    • 或者不合法的情况
  • 若为左括号
    • 作为一个新的更急迫的期待压入栈中(自然使所有在栈中未消解的期待的迫切性都降了级)

如果在算法的开始和结束的时候，栈应该都是空的。

行编辑程序

行编辑

一个简单的行编辑程序的功能：接受用户从终端输入的程序或者数据，并存入用户的数据区。

但是，用户在终端上进行输入时，不能保证不出差错，于是较好的处理方法如下：

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。

允许用户输入出差错，并在发现有误的时候可以及时更正。

设这个输入缓冲区为一个栈结构

处理方法：

  • 每当从终端接受了一个字符之后先做如下判断
    • 如果它既不是退格符也不是退行符，则将该字符压入栈顶；
    • 如果是一个退格符，则从栈顶山区一个字符；
    • 如果是一个退行符，则将该字符栈清为空栈。

迷宫求解

以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，

  • “纳入路径”的操作即为“当前位置入栈”；
  • “从当前路径上删除前一通道块”的操作即为“出栈”。

求迷宫中一条从入口到出口的路径的算法可简单描述如下：

do {
    若当前位置可通，
    则 {
        将当前位置压入栈顶;                         //纳入路径
        若当前位置是出口位置,则结束;                 //求得路径存放在栈中
        否则切换当前为止的东邻方块为新的当前位置;
    }
    否则 {
        若栈不空且栈顶位置尚有其他方向未经搜索,
            则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块;
        若栈不空但栈顶位置的四周皆不可通，
            则{
                删去栈顶位置;                      //从路径中删去该通道块
                若栈不空，则重新测试新的栈顶位置,
                    直到找到一个可通的相邻块或出栈至栈空;
            }
    }
} while (栈不空);

当前位置可通，指的是：未曾走到过的通道块 行走方向：东南西北

表达式求值

此处介绍一种简单直观、广为使用的算法：算符优先法。

任何一个表达都是由操作数operand、运算符operator和界限符delimiter组成，称他们为单词。

操作数：既可以是常数，也可以是被说明为变量或常量的标志符； 运算符：分为算术运算符、关系运算符和逻辑运算符； 基本界限符：左右括号和表达式结束符等。

运算符和界限符统称为算符(他们构成的集合命名为OP)。

实现

为实现算法优先运算，可以使用两个工作栈。

  • 一个称作OPTR，用以寄存运算符；
  • 一个称作OPND，用以寄存操作数或运算结果。

算法的基本思想：

  1. 首先置操作数栈OPND为空栈。表达式起始符#为运算符栈的栈底元素；
  2. 依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶元算符比较优先权后作相应比较，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为#)

例子