聊一聊栈（1）
栈是一种非常重要的数据结构，在计算机科学领域有着广泛的应用，本讲将和大家一起来探讨如何利用C语言的数组来实现栈。首先来看一下栈的定义。
我们有编号为ABCDE的五个球，按照A~E的顺序依次放到某容器，如下所示：
图1-1 盛放球的容器
请问此时如果从容器中依次取球，则取出的球的编号是什么？
这个问题十分的简单，相信您很快就可以得到答案。刚开始放入的A球会率先进入容器底部，其次是B，C，D，E，最后我们看到位于容器顶部的是编号为E的球，所以取出的次序依次是EDCBA。
这就是栈，从上面的分析大家可以看到它的一个显著特点就是“先进后出”或“后进先出”。栈的概念及特点比较好理解，接下来我们来讨论如何利用C语言来实现它。
要想用C语言来实现栈，首先我们搞清楚栈的基本要素有哪些。大家从上面的示例看到的第一个要素便是容器，你得有容器存放所有的球。既然是容器，那么C语言中，大家最容易想到的便是数组，我们可以定义一个字符数组来存放所有的球的编号。
但是仅有数组就够了吗？
假如我们定义了一个chardata，表示我们现在有了一个容器啦，它可以放10个球。虽然现在可以放球了，但是请思考下面的几个问题你是否能回答：
1）当前容器里面你放了几个球？
2）我想从容器顶部取一个球，你能告诉我这个球的编号吗？
3）如何知道容器满了没有？
4）如何知道容器是空的呢？
你会发现仅仅定义一个数组是无法回答上面的几个问题的。所以对于栈我们需要定义新的要素。
那么如何解决上面的几个问题呢？该定义什么要素呢？接下来我们就要定义一个非常巧妙的标记就是top标记。top指向当前栈的顶部，注意它指向的容器单元不存放任何球，如下所示：
图1-2引入top后的栈
当前top指向5号单元，则我们可以得出：
1）当前栈的大小为5；
2）栈顶元素的值是data即data；
接下来我们便看一下，依次放入五个球后，栈的变化情况：
1）刚开始的时候，栈为空，我们让top指向0；
2）当放入A球时，我们将A球放到0号单元，并且top向上挪一位，
data = A; ==> data = A;
top++;
3）当放入BCDE球时，我们都执行上述同样的操作。
最终我们会得到图示的栈结果。
本文通过一个案例给大家介绍了栈的定义，由浅入深的分析了栈的构成要素。另外从上面的分析大家可以看到，一个简单的top标记就可以解决很多问题，设计的非常巧妙。
页:
[1]