2
回答
聊一聊栈(1)
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

栈是一种非常重要的数据结构,在计算机科学领域有着广泛的应用,本讲将和大家一起来探讨如何利用C语言的数组来实现栈。

 

首先来看一下栈的定义。

我们有编号为ABCDE的五个球,按照A~E的顺序依次放到某容器,如下所示:

图1-1 盛放球的容器

请问此时如果从容器中依次取球,则取出的球的编号是什么?

 

这个问题十分的简单,相信您很快就可以得到答案。刚开始放入的A球会率先进入容器底部,其次是B,C,D,E,最后我们看到位于容器顶部的是编号为E的球,所以取出的次序依次是EDCBA。

 

这就是栈,从上面的分析大家可以看到它的一个显著特点就是“先进后出”或“后进先出”。栈的概念及特点比较好理解,接下来我们来讨论如何利用C语言来实现它。

 

要想用C语言来实现栈,首先我们搞清楚栈的基本要素有哪些。大家从上面的示例看到的第一个要素便是容器,你得有容器存放所有的球。既然是容器,那么C语言中,大家最容易想到的便是数组,我们可以定义一个字符数组来存放所有的球的编号。

 

但是仅有数组就够了吗?

假如我们定义了一个chardata[10],表示我们现在有了一个容器啦,它可以放10个球。虽然现在可以放球了,但是请思考下面的几个问题你是否能回答:

1)当前容器里面你放了几个球?

2)我想从容器顶部取一个球,你能告诉我这个球的编号吗?

3)如何知道容器满了没有?

4)如何知道容器是空的呢?

 

你会发现仅仅定义一个数组是无法回答上面的几个问题的。所以对于栈我们需要定义新的要素。

 

那么如何解决上面的几个问题呢?该定义什么要素呢?接下来我们就要定义一个非常巧妙的标记就是top标记。top指向当前栈的顶部,注意它指向的容器单元不存放任何球,如下所示:

图1-2引入top后的栈

 

 

当前top指向5号单元,则我们可以得出:

1)当前栈的大小为5;

2)栈顶元素的值是data[4]即data[top-1];

 

接下来我们便看一下,依次放入五个球后,栈的变化情况:

 

 

1)刚开始的时候,栈为空,我们让top指向0;

2)当放入A球时,我们将A球放到0号单元,并且top向上挪一位,

data[0] = A;     ==>     data[top] = A;

top++;

3)当放入BCDE球时,我们都执行上述同样的操作。

 

最终我们会得到图示的栈结果。

 

本文通过一个案例给大家介绍了栈的定义,由浅入深的分析了栈的构成要素。另外从上面的分析大家可以看到,一个简单的top标记就可以解决很多问题,设计的非常巧妙。

<无标签>
举报
顶部