栈：装水的杯子（一）入门测试题

 

子渊学算法之

——栈：装水的杯子

 

（一）入门测试题

 

首先来介绍我们的主人公：梁子渊，男，12岁，小学六年级学生。

子渊参加了计算机程序设计兴趣小组，学了一个学期的PASCAL语言和简单的组合数学知识，想要向更高级的技术——数据结构和算法发起挑战了。正巧爸爸也是一个算法迷，于是两父子展开了以下的对话：

       “爸爸，我想学习数据结构和算法，老师说掌握它们就可以在计算机的天地里畅通无阻了。爸爸你快教教我吧！”

       “是吗？那你基础打得怎么样了？让我先来考考你，看看你有没有学习算法的潜质。”

“好啊！尽管放马过来吧——只是题目不要太难。”

“你放心，绝对基础题！”

题目：输入一个正整数n，试分离并输出其各位数字。例如，输入n=1234，则输出1，2，3，4。（保证n不超出integer的范围）

子渊一看题目心里就乐了，这么简单啊！我刚学习PASCAL语言的时候就做过这种题目了，不就是考查整除和取余运算吗？

不到三分钟，子渊就把代码交到了爸爸手里：

{代码1：}

{输入一个正整数n，试分离并输出其各位数字}

PROGRAM Separate(INPUT, OUTPUT);

VAR

    v, n : integer;

 

BEGIN {MAIN}

    writeln('Input n:');

    readln(n);

 

    while n <> 0 do

    begin

        v := n mod 10; {分离出n的个位数字}

        write(v:2);

        n := n div 10; {去除n的个位数字}

    end; {while}

END.

爸爸看了代码以后，点了点头，说：“不错不错，代码风格不错！结构整齐，注释完整，基本功还可以。可惜啊！没按题目要求来做。”

子渊一听就急了，“怎么没按题目要求做？我不是从低位到高位把n的各位数字都分离并输出来了吗？”

“你把n的各位数字从低位到高位都分离了是不错，可是你的输出顺序也是从低位到高位，这不符合题目要求，也与我们的书写习惯不同啊。”

“对喔！我刚好弄反了。”子渊这才不会意思的挠了挠脑袋，“这该怎么办呢？”

“再好好想想！如果给定的正整数n是个3位数呢？”爸爸提示道。

“3位数？那很好办啊！只要从高位开始分离数字就好了。”子渊兴奋得跳了起来，“也就是说，我只要先判断出n是个几位数，从高位开始分离数字就好了，因为保证n不超出integer的范围（HIGH(integer) = 32767），所以它至多是个5位整数，这样我至多判断5次就可以知道n是个几位数了。”

不一会儿，新的代码又交到了爸爸的手里：

{代码2：}

{先判断出n是个几位数，再从高位开始分离数字并输出}

PROGRAM Separate(INPUT, OUTPUT);

VAR

    v, n, h : integer;

 

FUNCTION Highest(n : integer) : integer; {判断n是个几位数，最大为32767}

begin

    if n > 10000 then

        Highest := 10000

    else if n > 1000 then

        Highest := 1000

    else if n > 100 then

        Highest := 100

    else if n > 10 then

        Highest := 10

    else

        Highest := 1;

end; {Highest}

 

BEGIN {MAIN}

    writeln('Input n:');

    readln(n);

 

    h := Highest(n); {判断n是个几位数}

    while h <> 0 do {分离数字并将其入栈}

    begin

        v := n div h; {分离出n的最高位数字}

        write(v:2);

        n := n mod h; {去除n的最高位数字}

        h := h div 10;{n位数降1}

    end; {while}

END.

“不错，确实能实现我所要求的功能，反应挺快！可是你不觉的这次的代码很“丑陋”吗？你看，姿态臃肿，一点也不简洁。特别是那个Highest()函数，只能用来判断integer类型数据，通用性很差。我们编写代码也是要讲究美感的啊！”爸爸稍微点了点头就马上叹起气来。

“很丑陋？我怎么没感觉到啊！它不是很好地实现了我们的意图吗？”子渊很是不解。

“实现了所需要的功能不错，可是这种实现的方法不够简洁，美观，缺乏通用性。反正我看着就是不顺眼——就像你这乱七八糟的书桌一样。”话说着，爸爸就帮子渊整理起书桌来：他把摆放得杂乱无章的各种童话，围棋和自然科学书籍一一收起来，放到一旁的储物箱里。

“其实你最初从低位开始分离数字的思路是正确的，因为这样不用事先判断n是个几位数，所以很容易实现。但是你把数字一分离出来就马上输出是不对的，最先分离出的数字是不能最早输出的。”

“最先分离的数字不能最早输出？那我该怎么办呢？”子渊喃喃自语。

“——咦，我的那本《科幻大王》呢？就是放在桌子最上面那本，爸爸你把它弄哪里去了？我还没看完呢！”子渊突然发现自己书桌上的书都不见了，马上嚷嚷起来。

“你嚷嚷什么呀！那些书我都收起来了，全部放在储物箱里。那本《科幻大王》是我最先收起来的，应该在箱子的底部，你自己去拿吧。”

“爸爸你真爱作弄人啊，把它放在最下面了！那我不是要把其他的书都移开才能拿到吗？真麻烦！”

“是啊，最早放进去的书自然是最后拿出来了！”爸爸顺口回答，“其实生活中类似这样的情况还真不少呢，比如你妈妈换蜂窝煤的时候，最先放进去的煤块不也是最后被拿出来吗？”

“我知道我知道！还有杂技演员表演叠罗汉的时候，最后上去的人总是第一个下来。”子渊也不甘示弱地补充。

“是啊，还有我们喝水的时候，最先喝到的总是最上层的水，而它们是最后被倒进去的。”爸爸继续补充，“计算机科学家们还给这种操作特点取了一个优雅的名字——“后进先出”呢。”

“后进先出？”

“是啊，上面所有的例子，不都体现了“后进先出”的特点吗？”

“可是，计算机科学家们为什么要研究它们啊？还给它取一个这么奇怪的名字。”子渊还是不明白爸爸说这些话有什么意思。

““后进先出”(LAST IN FIRST OUT，简称LIFO)只是它的特点，其实这是计算机程序设计中一个常见的数据结构——栈（STACK），它是一种存储数据的容器，就像装水的杯子一样。”爸爸进一步解释，“水杯里的水按照“后进先出”的顺序被倒进倒出，存储在栈中数据也是是按照“后进先出”的方式被插入和删除的。”

“原来是这样啊！”子渊好像明白了些什么，但还是有很多的疑问，“可是这样的数据结构有什么作用呢？”

“要知道栈有什么用途，首先我们要搞清楚它本身的属性和能够实现的基本操作。子渊你想想看，这个像装水的杯子一样的数据容器——栈，它应该具备哪些属性和进行哪些操作呢？”

“存储数据的容器，像装水的杯子一样。。。。。嗯！那它应该可以插入和删除数据。对了，栈用什么来装这些数据啊？”子渊的问题就像水里的气泡一样不断地往外冒。

“栈可不是什么天外来客，它建立在各种程序设计语言的原有数据类型的基础上，比如PASCAL语言，我们可以用内置的数组或链表数据类型来实现栈结构。”爸爸解释道，“那你知道该如何用数组来实现栈的基本属性和操作吗？先考虑栈的属性，它具有哪些基本属性呢？”

“栈的属性？像装水的杯子一样的栈？首先应该要有一个容量属性吧，比如杯子的容量有200ML或500ML等。”子渊回答。

“确实是这样！但不止这一个。实际上栈有三个基本属性：最大容量（最大高度），实际存储量（实际高度），栈空指示标志。计算机科学家用“栈顶”来指示栈的实际高度，用“栈底”来作为栈空指示标志。当栈顶和栈底指向同一位置时，表示栈内没有存储元素，即栈为空。”

“这样啊！那栈的基本操作是不是删除和插入元素呢？”

“不错，这正是栈最基本的操作，就像杯子可以用来装水和倒水一样。需要注意的是，正如杯子的装水和倒水动作都是在最上层的水面进行，栈的插入和删除操作也只能在栈顶进行。我们称插入操作为入栈或进栈，而删除操作为出栈或退栈。”爸爸回答道，“那么，我们是不是只需要这两种基本操作就行了呢？”

“还有别的？那会是什么操作呢？”子渊陷入了沉思。

“子渊，你想想看，我们在往杯子里加水的时候是不是一直不停地加啊？”爸爸又给出了提示。

“啊？不是啊！杯子满了就不能再加了。对了，我们还要做一个判断栈满的操作。”

“还有呢？”

“往里加水的时候要判断栈满，那往外倒水的时候就应该判断栈空了——我们还要做一个判断栈空的操作。”

“不错，能够触类旁通，脑子转得挺快的啊！另外，我们并不是一拿到杯子就要喝水，有些时候我们只是想看看杯子里面的水干不干净，并不一定要往外倒水。这也可以看成是一个基本操作：获取栈顶元素的值。”

“栈顶元素？”

“是啊，我们把栈顶所指的元素称为栈顶元素。”

“原来是这样啊！那栈这种数据结构就是有三个基本属性和五个基本操作了咯？”

“正确。现在就请你写出实现它的PASCAL代码吧。”爸爸又交代了任务，“顺便说一句，那个分离数字的问题用栈可以很漂亮地解决。”

十分钟过去了。。。。。。

子渊在电脑里写出代码，并且编译通过，赶紧把爸爸拉过来请他检查。

下面是代码：

{代码3：}

{利用栈解决分离数字问题：输入一个正整数n，试分离并输出其各位数字}

PROGRAM Separate(INPUT, OUTPUT);

CONST

    MAXCAPACITY = 100; {栈的最大容量}

    BOTTOM = 0;        {栈底标志}

     

TYPE

    ElemType = integer;  {栈内元素数据类型}

    Stack    = array [1..MAXCAPACITY] of ElemType; {用数组表示的栈}

 

VAR

    s    : Stack;       {定义s为栈}

    top  : integer;     {栈顶标志}

    v, n : integer;

 

FUNCTION StackEmpty(s : Stack; top : integer) : boolean; {判断是否栈空}

begin

    StackEmpty := (top = BOTTOM);

end; {StackEmpty}

   

FUNCTION StackFull(s : Stack; top : integer) : boolean; {判断是否栈满}

begin

    StackFull := (top = MAXCAPACITY);

end; {StackFull}

   

FUNCTION GetTop(s : Stack; top : integer)  : ElemType; {获取栈顶元素的值}

begin

    if StackEmpty(s, top) then

        writeln('underflow')

    else

        GetTop := s[top];

end; {GetTop}

 

PROCEDURE Push(var s : Stack; var top : integer; data : ElemType); {入栈}

begin

    if StackFull(s, top) then

        writeln('overflow')

    else

    begin

        inc(top);

        s[top] := data;

    end; {if}

end; {Push}

   

PROCEDURE Pop(var s : Stack; var top : integer) ; {出栈}

begin

    if StackEmpty(s, top) then

        writeln('underflow')

    else

        dec(top);

end; {Pop}

   

BEGIN {MAIN}

    top := 0; {栈顶初始化}

 

    writeln('Input n:');

    readln(n);

   

    while n <> 0 do {分离数字并将其入栈}

    begin

        v := n mod 10; {分离出n的个位数字}

        Push(s, top, v);      {个位数字入栈}

        n := n div 10; {去除n的个位数字}

    end; {while}

   

    while not StackEmpty(s, top) do {输出数字并出栈}

    begin

        write(GetTop(s, top) : 2);

        Pop(s, top);

    end; {while}

END.

 

爸爸终于笑了，子渊长长地舒出一口气——考试通过咯。