谈“堆栈”与“队列”的认识
谈“堆栈”与“队列”的认识
开发工具与关键技术：Visual Studio 2015 谈“栈”的认识
作者：李国旭
撰写时间：2020年5月28日
刚刚接触这个“堆栈”，简称——栈。它呢是我在这个《数据结构与算法》中第一次看到的一个陌生的词，也是我学编程的这一段时间以来的第一次接触；对于初学者的我们来说就会疑问了，什么是“栈”？在电视上我们看得那些古装剧里面就有这个客栈，而我们说的并不是这个；它们的意义上可以说是一个意思，我就是这样理解这个栈的，而且它这个栈呢有进栈有出栈等等。
下面我们来看一下栈的定义：堆栈简称为栈，是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶”而另一端呢称作“栈底”。通常将元素插入栈顶的操作称作为“入栈”（进栈或压栈），称删除栈顶元素的操作为“出栈”。如下图所示：（图来自唐懿芳老师）
在我们删除的时候呢为了避免删除了找不到，所以我们就需要一个备份
public Object delete(int i)throws Exception
{
index(i-1);//定位
Object obj=current.next.getElement();//取元素
current.setNext(current.next.next);
size--;//元素个数减1
return obj;
}接着上面的就是栈的储存结构了，它分为俩种存储结构：
（1）顺序栈——采用顺序结构存储
（2）链栈——采用链式结构存储
#define MaxSize 堆栈可能达到的最大长度
typedef struct{
ElementType elem[MaxSize];
int top;//栈顶位置
}SeqStack
//入栈
public void push(Object obj)throws Exception
{
if(top==maxSize-1){
throw new Exception("堆栈已满！");
}
top++;
stack[top]=obj;
}
//出栈
public Object pop()throws Exception
{
if(top==-1){
throw new Exception("堆栈已空！");
}
Object obj=stack[top]
top--;
return obj;
}如下图所示出栈和入栈的情况，出栈就一个放入备用空间，防止找不到，入栈就增加一个空间，例如：就好像我们家里碗柜的摆放都是叠着的，我们拿的时候呢就只能从上面开始拿，不能从下面开始拿这是肯定的，如果我们从下开始那么那些上面的盘子就会掉，都是同样的道理（下图来自唐懿芳老师）
与此相反，我们的队列也是“先进先出”的原理。队列简称为队，是限定只能在表的一端作插入运算、在另一端作删除运算的线性表；在表中，允许插入的一端称作“队尾”，允许删除的另一端称作“队首”（或“队头”）；它呢通常会将元素插入队尾的操作称作为入队列（或入队），称作除队。
这个堆栈跟“队列”是相反的，它特点是“后进先出”。它后面来，反而它能最先走，所以我们说它是不讲道理的堆栈。接着上面的队列，那么当rear=MaxSize-1时，队列为满，如果再加入新元素，就会产生“溢出”。但是这种“溢出”并不是真正的溢出，在数组的前端还有可能有空的位置，所以我们说这是一种假溢出。如下图所示：它的各种队列的情况（图来自唐懿芳老师）
针对上面的假溢出的解决办法就是：循环队列。那么它的删除队首元素是这样的，请看下面的代码
DeleteQueue(q)删除队首元素
ElementType DeleteQueue(CirQueue*q)
{
ElementType e;
If(q->front==q->rear)
{
Return(-1);
}
else
{
e=q->elem[(q->front+1)% MaxSize];
return(e);
}
}队列的存储结构
两种结构：（1）顺序队列——采用顺序结构存储
（2）链接队列——采用链式结构存储
队列的顺序存储结构，当front和rear相等时，队列为空。
队满：rear==Maxsize-1