《数据结构》第十四篇、栈

怒火攻心-高压电.jpg

引言

hello各位小伙伴，我还在，这一周真是累到吐血，每天都二三点才睡，早上7点又得爬起来上班。。。

不过，总算熬过来了，这一周终于有时间可以更新咯，至于java中的HashSet，HashMap等源码还没有进行解析，咱们别急，我抽空更。。。

今天给大家带来的是数据结构之

栈

不过，由于篇幅原因，今天的文章仅仅是上篇，如果估计没错的话，还有中篇、下篇等着呢，哈哈哈，大家有空时候瞅一眼就好了。

1、什么是栈

洗碗时，将洗好的碗一个叠着一个摆放到柜子中；

用碗时，再讲碗逐个取下来

恩，通常来说，摆放碗时是由下而上依次放置，而取碗时，则是从上到下依次取出。这些都是生活中的常理，这样的顺序，如果用我们的术语说的话，就是碗的取出的原则称为“后进先出”，即最后放的碗在取出的时候是先被取出来的。

“后进先出”记住这个术语

在各种数据结构中，栈 （stack）这个数据结构就遵循这个原则。

栈也是一种线性表，但是他是收到限制的线性表，我们在前边学到的顺序表，链表中，我们可以在他们的两端进行插入，删除操作，而栈呢，他只允许在一端进行插入和删除的操作，正如下图所示

栈的结构示意图.png

如图所示，图中，有栈顶和栈底，

栈顶：栈中允许执行插入和删除操作的一端称为栈顶

栈底：栈中不允许执行插入和删除操作的一端称为栈底

入栈、压栈

向一个栈中插入新元素称之为入栈、压栈

入栈之后，该元素被放在栈顶元素的上边，成为新的栈顶元素。

执行入栈操作时，会先将元素插入到栈中，然后按照数据入栈的先后顺序，从下往上依次排列。

每当插入新的元素时，栈顶指针就会向上移动，指向新插入的元素。

当栈已满时，不能继续执行入栈操作。

出栈、弹栈

从一个栈中删除元素又称之为出栈、弹栈

把栈顶元素删除，使其下面的相邻元素成为新的栈顶元素

执行出栈操作时，栈顶元素会先被弹出，接着按照后进先出的原则将栈中的元素依次弹出，。

弹出栈顶元素后，栈顶指针就会向下移动，指向原来栈顶下面的元素，这个元素就成为了新的栈顶元素。

当栈为空时，不能继续执行出栈操作。

注意

如果要从栈中获取元素，只能通过栈顶指针取到栈顶元素，然后依次取出，除此之外没有别的方式。正如上图所示，如果栈顶元素an没有弹出时，an下边的元素是不能取到的。

由于栈遵循后进先出（Last In First Out,LIFO）原则，因此又把栈称为后进先出表

栈的常用操作如下：

进栈、出栈相当于线性表中的插入和删除操作，两者不同的是，栈顶是栈读取、插入的唯一出入口。

2、栈的实现

栈也是线性表，因此线性表的存储结构对栈也适用，栈也分为

顺序栈

链栈

两种存储结构。存储结构的不同使得实现栈的基本算法也有所不同。

2.1.1栈的顺序存储实现

栈的顺序存储也称为顺序栈，他利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时设置栈顶标识top来指示栈顶元素在顺序栈中的位置。向顺序栈中插入元素时，其过程如下图所示：

向顺序栈中插入元素.png

如上图所示，向栈中插入元素时，需先使top指针指向栈顶上面的空位，然后再进行赋值

删除栈中元素时，只将top指针向下移动，指向新的栈顶元素，删除过程如下图所示

顺序栈弹栈.png

由上图我们知道，弹栈是将top指针移动，指向新的栈顶位置，原来的栈顶元素依然存在于存储单元中，但是无法通过栈进行访问。

注意，我们介绍栈的时候画的是上下结构的，现在画的是水平结构的，这个只是表示形式，并不是栈真实的结构，真实的结构就是一堆内存地址，更表现形式没关系，知道这点就行了。

学习完栈的入栈，弹栈，原理后，下面通过代码实现了一个顺序栈，这个顺序栈所具备的功能如下：

请看下方代码

seqstack.h(头文件)：

seqstack.c(函数实现文件)

下面是测试文件

main.c

2.1.2栈的链式存储实现

栈的链式存储也称为链栈，他和链表的存储原理一样，多可以利用闲散的空间来存储元素，用指针来建立个结点之间的逻辑关系。

链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。

他和链表区别是，只能在一段进行各种操作，如下所示

链栈.png

如图所示，链栈就是一个单端操作的链表，他的插入、删除操作就是在链表的一端进行。

接下来，我们实现一个链栈，其功能如下：

然后，会在main.c中进行测试

代码如下

linkstack.h 头文件

linkstack.c 操作函数实现文件

测试文件 main.c

总结

ok,看完了上面的两个例子，大家应该对顺序栈和链栈有了一个认识了吧，其实这些思想和顺序表和链表很相似，只不过出入口变成了一个，这些东西还得需要大家好好领悟，好好练习下本文中的代码哟。

持续更新，谢谢关注~~~