数据结构day04

一 栈和队列

1栈的基本概念

 各位同学大家好，从这个小节开始，我们会正式进入第三章的学习，我们会学习栈和队列，那这个小节中我们会先认识栈的基本概念。我们会从栈的定义和栈的基本操作来认识栈这种数据结构，也就是要探讨栈的逻辑结构，还有我们需要实现的一些基本运算。在后续的小节，我们再来探讨用不同的存储结构实现栈。

那这一页的课件和线性表的第一页课件，其实几乎是一模一样的。因为无论我们讨论什么样的数据结构，肯定都需要从数据结构的三要素作为出发点来依次分析和探讨。那我们这个小节中要学习的栈和线性表之间其实有很紧密的联系，

那这是我们之前学过的线性表的概念。

1.1 栈的定义

而栈其实也是一种特殊的线性表，只不过对于普通的线性表来说，当我们要插入一个数据元素或者删除一个数据元素的时候，我们可以在任意一个地方插入和删除，但是对于栈这种数据结构来说，我们会限制它的插入和删除操作。插入和删除操作只能在线性表的一端进行。也就说，如果我们要插入一个数据元素，那我们只能在表尾的这个位置进行。我们不可以在其他的这些地方进行插入操作，这是栈这种数据结构所不允许的。同样的，如果要删除一个数据元素的话，那我们同样只能从这边进行依次的删除。

其实栈的英文术语也就是stack，它的含义可以很好的表现出它这所说的这种性质来看一下。stack有个含义，叫做整齐的一堆，这儿给了一张图片，一个整齐的小石头堆好，那现在如果你有一个新的石头，想要放到这个石头堆里，你是不是只能放到？这个石头堆堆顶的位置啊。而如果你要拿走一个石头的话，你也只能从顶部拿走一个，如果你强行把中间的某一个石头直接抽掉的话，

那整个石头堆它就散了，对吧？所以其实这个英文术语的含义更能体现栈这种数据结构的一个呃核心的特性

那我们的生活中其实也有很多栈，比如说大家帮家里洗碗的时候呃，你洗的这些碟子一个一个落起来，这其实也是一个栈。如果你想放入一个新的盘子，那你是不是只能放到这个顶部，也就只能从顶部这一端进行插入操作？同样的，如果你想拿走一个盘子的话，那同样的，你只能从顶部拿走，最上面这个盘子。也就是从顶部这一端进行删除操作。

另外还有大家吃的烤串，那些烤串师傅在穿这些肉串的时候，肯定是先把下面的这些肉给穿进去。永远是从上方进行插入操作，同样的，当你在吃烤串的时候，你是不是也只能从上往下吃啊？也是只能从上面这一端进行删除操作。所以这就是栈，它也是一种线性表，因为这些数据元素之间，我们从逻辑上看，它也是穿成了一条线，也是有这样一前一后一对一的关系。只不过栈这种特殊的线性表，它的插入操作和删除操作是有限制的，只能从其中的一端进行插入和删除

好，接下来看一下和栈相关的几个比较重要的术语，栈顶栈底和空栈，那空栈很简单，就是这个栈里边没有存任何数据元素。其实就对应线性表的空表对吧，然后我们往一个栈里边放入元素的时候，肯定是从其中一端一个一个压入的。所以栈顶和栈底这两个术语其实也很直观，栈顶就是指允许进行插入和删除的这一端，而栈底指的是不允许插入和删除的这一端。那相应的，最上面的这个元素被称为栈顶元素，最下面的这个称为栈底元素。

那刚才的动画中，这几个数据元素的进栈顺序分别是a1a2a3a4a5，依次被压入栈中。那接下来如果让这几个数据元素出栈，或者说依次删除这些数据元素的话，那么出栈的顺序应该是a5先出，接下来是a4a3a2a1。刚好是进栈顺序的一个逆序。所以栈的特点就是后进先出，后进入这个栈的数据元素，会先出栈。那很多地方，在描述后进先出这种特性的时候，会用这样的一个英文缩写。lifo就是last in first out一个缩写。

因此，通过刚才的这些讲解，可以看到栈是一种特殊的线性表，它和普通的线性表相比，其实逻辑结构是一样的。这些数据元素之间有这样一对一，一前一后的逻辑关系。只不过和普通的线性表相比，栈这种数据结构，它的插入和删除操作只能在栈顶的这一端进行。这一点是和普通的线性表有区别的

 1.2 栈的基本操作

那接下来我们要看一下栈相关的基本操作，首先快速的回顾一下线性表相关的基本操作。其实就是创建销毁，还有增删查这几个基本操作，

那栈需要实现的基本操作也是一样的，首先是创建和销毁。创建一个栈，也就是初始化一个栈，就是要分配相应的内存空间，而销毁一个栈，就是要释放这个栈所占用的内存空间。那接下来是增删两个操作，我们用push和pop来表示进栈和出栈，也就分别对应增加一个数据元素和删除一个数据元素，这两个基本操作。所谓进栈，就是要把数据元素x放到栈s的栈顶，而出栈，就是要把栈s它的栈顶元素给删除，并且用x这个变量给带回去。所以这才加了一个引用符号。

好再往后的操作，是读取栈顶元素get top会用变量x返回这个栈顶的元素。那这个基本操作和上面这个基本操作（pop）的区别是上面出栈的这个基本操作，除了返回栈点元素之外，还会把栈点元素给删除。但是get top这个基本操作，它只会读取栈点元素，用x来返回，但是并不会把栈点元素给删除。那get top这个基本操作，其实就是对应了查，在普通的线性表当中，我们需要实现按位序查找这样的功能，但是对于栈的使用场景来说。大部分情况下，当我们要访问一个数据元素的时候，通常只需要访问栈顶的这个元素，所以在查找数据元素的时候，通常我们只需要找到这个栈顶的元素就可以。

好再往后还有比较常用的这个基本操作，就是判断这个栈是否是一个空栈，如果是空的话返回去，否则返回FALSE这个和线性表的判空是。是几乎一样的。好，那这是栈相关的重要的基本操作，

总之核心就是我们要知道栈这种数据结构，我们的插入和删除操作只能在栈顶进行。它是一种操作受限的线性表，而由于插入和删除，只能在栈顶进行，因此它就拥有一个特性，叫做后进先出，后进入栈的数据元素，反而会先出栈。

2 顺序栈的实现

各位同学大家好，在这个小节中，我们会探讨顺序栈的实现，也就是怎么用顺序存储的方式来实现一个栈。那在确定了存储结构之后，根据这个存储结构还需要探讨与它相对应的一系列基本操作应该怎么完成，那顺序栈相关的基本操作其实和我们之前学过的顺序表链表那些是很类似的。比较重要的是，如何初始化，然后怎么实现进栈，也就是怎么增加一个数据元素，还有怎么实现出栈，也就是删除一个数据元素。另外，还需要探讨如何获取栈点元素，还有如何判断一个栈空，如何判断栈满这几个问题。

 2.1 顺序栈的定义

 它既然是用顺序存储的方式实现的，那它的代码的定义实现方式其实就和我们的顺序表是非常类似的，你看这个地方定义了一个struct结构体，然后我们用type def把它重命名为SqStack，然后这个结构体里边包含了一个静态的数组data用于存放栈中的各个元素，那这地方SQ就是sequence的缩写，也就是顺序的意思，所以接下来我们就可以在自己的函数里边用这样的方式声明一个顺序栈。

那在执行了这句代码之后，就会在内存当中分配这样的一整片的连续的空间，这整片空间的大小应该是max size，也就是栈的最大容量再乘以每一个数据元素，它的大小，另外还需要在内存当中分配四个字节的大小，用于存放top这个变量。那这个变量，它其实是栈顶指针，就是用于指向此时这个栈的栈顶元素。一般来说，这个栈顶指针，它记录的是数组的下标，也就是从零开始的好，

那假设现在我们的栈中已经压入了这样的几个数据元素，那此时这个栈顶指针的值就应该是四，也就是指向栈顶元素的这个位置，这个是数组的下标

2.2顺序栈的初始化操作

那在分配了存储空间之后，接下来需要进行初始化的操作。那刚才我们说过，这个栈顶指针要让它指向此时栈顶元素的位置，所以刚开始的时候top指针指向零这个位置其实是不合理的。因为data 0这个位置，此时还没有存放数据元素，所以刚开始我们可以让top的值指向负一。

因此，按照这儿的逻辑，我们要判断一个栈是否为空的时候，只需要判断它的top指针是否等于负一就可以。好，那到这一步，我们就完成了栈的初始化工作，接下来就可以进行一些后续的操作，也就是增删改查那些东西，对吧？

 2.3进栈操作（增）

我们首先来看一下增，也就是增加一个数据元素的操作，那对于栈这种数据结构的插入操作，我们通常把它称为进栈。

好来看一下，怎么把数据元素x放到栈s当中？首先第一步需要判断这个栈此时是否已满，

因为顺序栈是用静态数组的方式实现的，它有一个最大容量的上限好，那在右边这种情况下，此时暂时不满的，因此可以继续往后执行。接下来我们是不是想往这个data【 0】这个位置给插入一个新的数据元素？因此，我们可以把top指针先让它加一，也就是从负一变为零，然后接下来把此次传入的这个数据元素x把它存到data数组里边，也就是此时top指针所指向的这个位置，也就是放到这个地方。然后给调用者返回一个true表示，此次入栈操作成功好，

那接下来如果还要进行进栈操作的话，那是不是依然需要把top指针？让它往后移一位，然后再把这一次的数据元素给放到相应的位置，总之由于我们的top指针，它永远都是指向此时的这个栈顶元素的位置。因此，当一个新元素入栈的时候，我们肯定都需要先让top指针加一，然后再往top指针指向的位置放入新的元素，

那我们的课本当中给了一种更简洁的写法，就是这样的。这儿用的是加加top，而不是top加加，这个跨考的同学需要注意一下，那这句代码和左边的这种写法是等价的，

加加top的意思就是说先让top的值加一，然后再来使用这个top的值。而如果你没注意写成了top加加的话，那么就相当于你先使用了top的值，然后再让top的值加一。放在右边这个例子当中，假设我们此时想要插入一个新的数据元素c，那c，这个数据元素它合法的呃，我们期待的插入位置应该是插入到这个地方，也就data 【2】这个位置。好！此时top的值是一，那如果你使用的是top加加这样的写法的话，那么就相当于你先把此次要传入的这个数据元素c。先把它放到了呃data 【1】当中，也就相当于你让数据元素c把以前的这个数据元素b给覆盖了。然后接下来才进行top+1的操作，也就让top指针指向这个位置。所以这种执行就是一种错误的结果，因此基础不太好的同学一定要注意这个小细节啊，比较容易出错。

好，接下来看一下这个顺序栈已经存满的情况，那我们的顺序栈它的容量是十。此时已经全部存满了那top指针，指向栈顶元素，也就指向这个位置，它的值应该是九，在这种情况下，

如果继续调用入栈操作，那么由于top的值此时是等于max- 1，也就是等于九，所以这就意味着此时栈已经满了，因此会直接返回一个FALSE给函数的调用者一个反馈。好，那这是进栈操作的实现

2.4出栈操作（删）

接下来看一下出栈操作，出栈操作其实就对应了增删改查的删，也就是要删除栈顶的一个元素，并且用变量x来返回。那这个地方x这个变量加了引用符号，也就是说这个出栈操作的调用者，他首先会在自己的函数里边定义一个。一个变量叫做x，这个变量存放在内存中的某一个位置，那由于这儿加了引用符号，所以在出栈操作里边操作的这个变量x和函数的调用者定义的这个变量x对应的是同一份数据，而不是它的复制品。好，接下来要判断这个栈是否为空，如果栈空的话，那么肯定不能让它进行删除的操作，也就是出栈的操作。

那在右边这个例子当中，此时栈是非空的，所以接下来会把栈顶指针所指向的这个元素，把它赋给x，这个变量也就是把这个值复制到内存里的这小片区域当中。接下来让top的值减一，也就是栈顶指针下移，然后给函数的调用者返回。一个true表示，此次的调用成功。

那在这个删除操作当中，我们把top指针让它往下移了一位，其实只是在逻辑上删除了之前的这个栈顶元素，但是其实k这个数据元素的数据依然还是残留在内存当中的。它只是在逻辑上被删除了而已，

那和入栈操作类似，我们可以把这两句代码合并成一个更简洁的写法，这使用了top减减，也就是说。先使用top的值，再让top的值减一类似的，如果你写的是减减top，那你的这些代码运行就会出现问题。

来看右边这个例子，此时栈顶元素应该是j这个元素，也就是说我们要让x返回的是j这个数据元素，那如果说我们使用的是减减top这样的写法的话。那首先会让top的值减一，也就是先让top指向这个位置，接下来才把top指向的这个元素把它赋给变量x。也就说x返回的是I这个元素，而不是j这个元素，那这并不是我们所期待的正确结果，所以这个跨考的同学一定要注意。

当然，这个代码千万不要背，一定是要基于理解的基础上能够自己分析到底用哪种写法。好，那这是出栈操作

 2.5读栈顶元素的操作（查）

接下来看读取栈顶元素的操作，其实这个操作和出栈操作几乎一模一样，唯一不同的是出栈操作会让top指针减减往下移一位。但是读栈顶元素这个操作，它只是把此时top指针指向的这些数据元素用x给返回，但并不会让top指针减减。所以这个很简单，就不再赘述好， 

那刚才我们提到所有的这些代码都是让top指针指向此时的栈顶元素，用了这样的一个方案。

那其实我们还可以用另外一种方式来设计，我们可以让top指针刚开始指向零这个位置，那相应的判断栈是否为空，就是看top是否为零。那这儿的这种实现方式，我们是让top指针指向了下一个，我们可以插入元素的位置。因此，如果接下来有一些数据元素入栈的话，那么top指针应该是指向这个位置。

好，那如果我们这么设计的话，那当我们想要让一个新的数据元素x入栈的时候，我们是不是需要先把x？放到此时top指针指向的这个位置，

然后再让top指针加一对吧，这和之前的那种方式刚好是相反的，在这种情况下，我们就应该用top加加，而不是加加top。

那类似的，如果此时要让栈顶元素出栈的话，那么我们应该先让top的值先减一，然后再把top指向的数据元素给传回去，因此就应该用减减top这样的操作。所以大家在做题的时候一定要注意审题，这个top指针它到底是要让它指向栈顶元素，还是要让它指向栈顶元素后面的一个位置？两种方式的实现代码是不一样的

如果这个栈已经存满了的话，那么top指针它的值应该是等于max size，也就是等于十。因此，判断栈满的条件也会不一样。那可以看到，由于顺序栈是用了一个静态数组来存放数据元素，因此当这个静态数组被存满的时候，它的容量是不可以改变的。那这是顺序栈的一个缺点，

如何解决这个问题呢？可以用链式存储的方式来实现栈，或者我们也可以在刚开始的时候给这个栈分配一个比较大片的连续的存储空间。但是刚开始就分配大片的存储空间，这会导致内存资源的浪费，

那其实可以用共享栈的方式来提高这一整片内存空间的利用率。共享栈的意思就是说两个栈共享同一片存储空间，我们会设置两个栈顶指针，分别是零号栈和一号栈的栈顶指针。然后零号栈的栈顶指针刚开始是负一，一号站的栈顶指针，刚开始是max size，接下来如果要往零号栈放入数据元素的话，那么就是从下往上依次递增的。而如果要往一号栈放入数据元素的话，那么这个栈的栈顶又是从上往下依次递增的，那这样的话，在逻辑上，我们这实现了两个栈。但是物理上它们又是共享着同一片的存储空间。这就会提高内存资源的利用率好，

那这个共享栈它也是会被存满的，判断共享栈是否满了的条件就是你判断一下top 0它再加一是否等于top 1的值。好，那共享栈相关的代码，有兴趣的同学也可以自己去实现一下

这一小节中，我们学习了如何用顺序存储的方式实现栈？那用这种方式实现的栈就称为顺序栈。我们要定义一个静态数组来存放数据元素，另外还需要在struct结构体里边啊，定义一个栈顶指针。我们可以让这个栈顶指针指向当前的栈顶元素，也可以让栈顶指针指向接下来可以插入数据元素的这个位置。两种设计方式所对应的初始化操作会各不相同，

另外再增加一个数据元素和删除一个数据元素的时候，代码实现也会有所不同。这个是比较容易错的地方，所有的这些基本操作都可以在o（1）的时间复杂度内完成。那怎么销毁一个顺序栈呢？首先是要在逻辑上把这个栈给清空，接下来再回收这个栈所占用的内存资源。在逻辑上，清空一个栈其实只需要让top指针指向初始化的那个位置就可以了。在这个小节的代码当中，我们是使用了变量声明的这种方式来分配相应的内存空间，并没有使用malloc函数。所以给这个栈分配的内存空间也会在你的这个函数结束之后，由系统自动的回收，所以其实回收内存资源这个事情你并不需要管。

3 链栈的实现

各位同学大家好，在这个小节中我们会学习如何用链式存储的方式来实现栈，那用链式存储的方式实现的栈叫做链栈。同样的，在确定了存储结构之后，我们也需要探讨基于这种存储结构怎么实现相应的这些重要的基本操作。 

好，那我们先穿越到之前单链表相关的一个课件，用头插法来建立单链表，所谓用头插法建立一个单链表，就是指当我们要插入一个数据元素的时候，我们都是把它插入到这个头结点之后的位置。就像这个样子。那可以看到，刚才我们对这个单链表进行插入操作的时候，都是在这一端进行插入的，那这其实不就是栈的进栈操作吗？如果我们规定只能在单链表的这一端进行插入操作的话，那这就是进栈操作，

好那类似的，如果我们规定当我们对这个单链表进行删除操作的时候，我们同样只能在这一端进行删除操作，就像这个样子。那这种有限制的删除操作，不就是我们栈里边的出栈操作吗？

所以其实用链式存储实现的栈，它本质上也是一个单链表，只不过我们会规定只能在这个单链表的这一端进行插入和删除操作，也就是把链头的这一端把它看作是我们的栈顶的一端。

所以大家会看到，对于链栈的定义，其实和单链表的定义几乎没有任何区别，只是这些名字稍微改了一下而已。

 

那和单链表类似，当我们用链式存储的方式来实现链栈的时候，我们是不是也可以实现带头节点的版本和不带头节点的版本？当然，两种设计方式对于栈是否为空的这个判断会不一样。那进栈和出栈操作，其实就是对应了单链表当中的插入数据元素和删除数据元素的操作，只不过插入和删除我们只能在这个表头的位置进行。

那如何在表头的位置插入和删除这个，我们在单链表那个小节当中已经讲的非常详细了，这就不再赘述。