数据结构与算法之堆栈和队列_堆栈和序列

开发工具与关键技术：数据结构与算法
作者：超级小贱贱
撰写时间：2020年5月08日
1
2
3

继着上次的线“性表的运算”性表的运算，这次呢我将带来有点抽象的“堆栈和队列”，首先呢，先讲讲堆栈的定义。举个例子，餐厅里摆放整齐的盘子，盘子的摆放是不是由下往上一张一张的叠放上去的？而取出来的时候却是先从最顶上，也就是最后叠上去的那张先取出来，对不对？总不可能从底下先取着用吧，这样的话很容易打烂，所以呢，堆栈有个特点，也是定义：先进后出，后进先出。堆栈还有个简称，叫做“栈”，做个比方，我面前有4个盘子，这4个盘子叠放组合起来的就叫做“栈”，其中最底下的那张盘子叫做“栈底”，而最顶端的盘子就叫做“栈顶”，而每当我们想叠一张新的盘子的时候，就叫做“入栈”，相反，我想拿出一张盘子的时候就是“出栈”，这个就是“栈”的定义和特点，其中“栈”又分为两种存储结构，分别为：1、顺序栈—采用顺序结构存储。2、链栈—采用链式结构存储。
接下来就以顺序栈，来说说堆栈的压入和弹出，如图

这里我们要进行的操作呢就是将A-F按顺序填入只有4个位置的堆栈中，首先将A填入，A进入的位置呢就是堆栈的栈底，也就是最底下，接着将B填入，然后B就会去到倒数第二个位置，也就是A的头上，现在再来试一下弹出，此时此刻呢，点一下弹出的按钮，B就会率先去到“出栈序列里头”，反应了它们遵循着定义，后进先出，并且只有栈顶可以操作，而且那个“Top”也要随着元素的出栈而变化。当然如果4个位置都满了，就得出栈一些元素，从而让新的元素在进来，那么这时候问题又来了，栈满和栈空的条件又是什么呢？答案分别是：1、栈满：top=Maxsize-1。2、栈空：top=-1。其中“Maxsize”指的是堆栈可能达到的最大长度。
堆栈结束后，接下来就是队列，队列有点抽象，我也是比较难理解，有什么说不对的地方还请指教。
队列分为顺序队列和循环队列，队列就是你一条长长的队伍，都是非常有秩序的排着队，而不会存在任意的插队和加塞，所以队列的特点就是先进先出，与堆栈反着来的。队列又简称为队，是限定只能在表的一段作插入运算、另一端作删除运算的特殊线性表，而在表中，允许被插入的一端称作“队尾”，反之另一端允许删除的就叫做“队首”，或“队头”。队列的存储结构同样也分为两种：1、顺序队列—采用顺序结构存储。2、链式队列—采用链式结构存储。下面用图片来讲解队列的插入和删除方式。

如图，入队元素分别为“A、B、C、D”，首先将A元素移入队列中，会发现只有“rear”发生了变化，因为是在队尾插入了元素，而“front”不会发生任何变化，而当我们把A元素移入到“出队元素”那之后，“front”就往前移动了一个单位，因为进行了删除的操作。下面是详细过程图

其中需要注意的是，队满和队空的条件是什么，队空的条件就是当“front”等于“rear”的时候，即front=rear，而队满的条件就是rear=Maxsize-1，这里的“Maxsize”指的是最大的空间大小，即表示图中那5个位置，但这时候又有一个问题来了，当rear=Maxsize-1时，队列为满，如果在加入新的元素，就会产生“溢出”。但这种“溢出”却又不是真正的溢出，在数组的前端还可能有空的位置，所以这是一种假的溢出。但平时作业中我们又不希望假溢出的出现，那如何解决呢？解决办法就是：循环队列。怎么循环法？当每天的时间到23时59分59秒的时候，它是不是会重新跳回0点，重新开始计算，没错，队头和队尾连起来，形成一个环，即把存储队列元素的表从逻辑上看作是一个环，便成为了循环队列。如下图所示

这里的队头指针加一指的是“出队”，同理队尾指针加一指的是“入队”，而当队满的时候（看最左下角的图），也就是满足下面条件：front==（rear+1）%MaxSize，我们就默认为“rear”的下一个元素等于“front”。