聊一聊栈（1）

栈是一种非常重要的数据结构，在计算机科学领域有着广泛的应用，本讲将和大家一起来探讨如何利用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标记就可以解决很多问题，设计的非常巧妙。