四、栈与队列

4.1 初始栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许再一端进行插入操作、而在另一端进行删除操作的线性表

4.2 栈的定义

4.2.1 栈的定义

栈的结构类似与弹夹中的子弹，先进去的后出来，后进去的先出来。这就是数据结构中的栈。

生活中，栈这种后进先出数据结构的应用是非常普遍的。像常用的浏览器后面都会有后退键，你点击后可以按访问顺序的逆序加载浏览过的网页。

还有常用的Office都会有撤销的操作。不同软件具体实现代码会有所不同，原理都差不多

栈（stack）是限定仅在表位进行插入和删除操作的线性表

把允许插入和删除的一端称为栈顶(top), 另一端称为栈底(bottom), 不

含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构

1.一些要注意的点

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹

栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹

4.2.2 进栈出栈变化形式

最先进栈的元素，是不是就只能是最后出栈呢?

答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

举例来说，如果现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢?

第一种: 1、2、3进，再3、2、1出。这是最简单的最好理解的一种，出栈

次序为321

第二种: 1进，1出，2进, 2出，3进，3出。也就是进一个就出一个，出

栈次序为123

第三种: 1进，2进，2出，1出，3进，3出。出栈次序为213

第四种: 1进，1出，2进，3进，3出，2出。出栈次序为132

第五种: 1进，2进，2出，3进，3出，1出。出栈次序为231

有没有可能是312这样的次序出栈呢?答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2一定是在1的上面，就是更接近栈顶，那么出栈只可能是321,不然不满足123依次进栈的要求，所以此时不会发生1比2先出栈的情况。

4.3栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop,英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT栈(stack)
Data
  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
  InitStack (*s):初始化操作，建立一个空栈S。
  DestroyStack(*s) :若栈存在，则销毁它。
  ClearStack (*s) :将栈清空。
  StackEmpty(s) :若栈为空，返回true,否则返回false。
  GetTop(s,*e) :若栈存在且非空，用e返回S的栈顶元素。
  Push(*s,e):若栈S存在，插入新元素e到栈S中并成为栈顶元素。
  Pop(*S,*e) :删除栈S中栈顶元素，并用e返回其值。
  StackLength(s) :返回栈S的元素个数。
endADT

由于栈本身就是一个线性表，那么上一章讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

4.4栈的顺序存储结构及实现

4.4.1栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好?

对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，它可以来回移动，意味着栈顶的top 可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize, 则栈顶位置top必须小于StackSize。 当栈存在一个元素时，top 等于0,因此通常把空栈的判定条件定为top等于-1。

typedef int SElemType;    /* SElemType 类型根据实际情况而定，这里假设为int */
typedef struct
{
SElemType data[MAXSIZE];
int top;  /*用于栈顶指针*/
} SqStack;

若现在有一个栈，StackSize 是5,则栈普通情况、空栈和栈满的情况示意图

4.4.2栈的顺序存储结构–进栈操作

对于栈的插入，即进栈操作，其实就是做了下面的处理

/*插入元素e为新的栈顶元素*/
Status Push ( SqStack *S, SElemType e)
{
  if (S->top == MAXSIZE -1) //栈满
  {
  return ERROR;
  }
  s->top++;  /*栈顶指针增加一/
  S->data[S->top]=e;  /*将新插入元素赋值给栈顶空间,将To*/ 
  return OK;
}

4.4.3栈的顺序存储结构–出栈操作

/*插入元素e为新的栈顶元素*/
Status Push ( SqStack *S, SElemType e)
{
  if (S->top -- MAXSIZE -1) //栈满
  {
  return ERROR;
  }
    *e = s->data[s->top]  /*将要删除的栈顶元素赋值给e*/
  s->top--;  /*栈顶指针减一/
  return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是o(1)

4.5 两栈共享空间

其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表

插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。

做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素,就是两端点向中间延伸。

其实关键思路是:它们是在数组的两端，向中间靠拢。top1 和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

从这里也就可以分析出来，栈1为空时，就是top1等于-1时;而当top2等于n时，即是栈2为空时，那什么时候栈满呢?

想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2 等于0时，为栈2满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2 为栈

代码实现如下：

typedef struct StackNode
{
  SElemType data;
  struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack
{
  LinkStackPtr top;
  int count;
} LinkStack;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下:

/*插入元素e为新的栈顶元素*/
Status Push ( SqDoubleStack *S, SElemType e,int stackNumber )
{
    if(s->top1+1==s->top2) /*栈已满，不能再push新元素了*/
  return ERROR;
  if ( stackNumber==1 ) /*栈1有元素进栈*/
  S->data[++S->top1]=e; /*若栈1则先top1+1后给数组元素赋值*/
  else if ( stackNumber==2)  /*栈2有元素进栈*/
  S->data[--s->top2]=e;/*若栈2则先top2-1后给数组元素赋值*/
  return OK;
}

因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担

心溢出问题的。

对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber,

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */
Status Pop ( SqDoubleStack *S, SElemType *e, int stackNumber )
{
    if( stackNumber==1 )
    {
  if (s->top1==-1)
    return ERROR; /*说明栈1已经是空栈，溢出*/
  *e=S->data[s->top1--]; /*将栈1的栈顶元素出栈*/
    }
  else↓if( stackNumber==2 )
  { 
  if(s->top2==MAXSIZE )
    return ERROR; /*说明栈2已经是空栈，溢出*/
  *e=S->data[s->top2++]; /* 将栈2的栈顶元素出栈*/
    }
  return OK;
}