数据结构学习笔记（三）

大家好，今天的内容是数据结构中关于栈的部分。前两篇文章分别介绍了线性结构的两种存储方式：数组和链表。我们先来总结一下数组和链表的区别

区别

先来看看数组：在内存中，数组是一块连续的区域。 拿看电影来说，平常和朋友去电影院看电影，和朋友几个人在电影院中必须坐在一起。数组的特点是，在使用数组之前，必须先申请内存空间。这样就存在一种空间浪费的情况，比如几个人看电影，预定了5个座位，可结果只来了3个人，最后两个座位就浪费掉了。随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到下一个地址的数据。但不利于扩展，数组定义的空间不够时要重新定义数组。

其次是链表：在内存中，链表的每个结点不要求连续。还用看电影来举例，这时不要求几个人坐在一起，他们可以坐在电影院的任何位置。但是， 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号。换句话说，每一个数据都保存了下一个数据的内存地址，通过这个地址可以找到下一个数据。

栈

知道了数组和链表的不同，我们就可以把它们应用到实际。栈(Stack)是一种可以实现“先进后出”的存储结构或存储方式。栈类似于没有盖的箱子，当每次往里放书时，最先放进去的总是最后才能拿出来，最后放进去的总是在箱子的顶部。并且规定，不能从箱子的底部放书和拿书。满足这个条件的我们称之为“栈”。

栈分为静态栈与动态栈。静态栈是以“数组”为内核的，动态栈是以"链表"为内核的。这里讨论动态栈。

栈主要有两种操作，出栈和压栈（入栈）

实战

创建一个栈，首先要知道栈里有什么。箱子有顶部和底部，那么栈就有栈顶和栈底；用一个指针指向栈顶，另一个指向栈底。为了方便今后操作整个栈，在栈的底部加一个没有实际意义的结点，并且将栈底指针指向它。

栈用一个结构体来表示，它有两个成员分别是栈顶指针和栈底指针。栈里的每一个结点用一个包含数据域和指针域的结构体来表示，对应到代码，如下所示：

这里的pTop指向栈顶元素，pBottom指向最后一个有效元素的下一个元素。现在如果执行一句STACK S内存中的情景为：

这样还不能称为一个栈，栈里必须有元素，也就是要有一个结点。首先初始化出来一个空栈，空栈里只有一个没有意义的栈底元素，也就是最后一个有效元素的下一个元素。此时，pTop和pBottom均应指向该元素，因为，此时它既是栈顶也是栈底。我们希望一个空栈应该是这样的：

代码如下：

这样，就完成了初始化栈的操作。

栈程序

这里，我写了几个栈的基本操作，实现如下：

END