数据结构【第4章】——栈与队列

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

栈

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

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

问题：最先进栈的元素,是不是就只能是最后出栈呢?

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

栈的抽象数据类型

对干栈来讲，理论上线性表的操作特性它都具备，可由干它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop。

由于栈本身就是一个线性表，因此线性表的顺序存储和链式存储，对于栈来说，也是同样适用。

栈的顺序存储结构及实现

栈是线性表的特例，因此栈的顺序存储也是线性表顺序存储的简化，我们简称为顺序栈。

线性表是用数组来实现的，用数组的下标0作为栈底比较好，因为首元素都会存在栈底，变化量小。

我们定义一个top变量来指示栈顶元素在数组中的位置，它可以来回移动，意味着栈顶的top可以变大变小，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在—个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 顺序栈结构 */
typedef struct
{SElemType data[MAXSIZE];int top; /* 用于栈顶指针 */
}SqStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(SqStack *S)
{ /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */S->top=-1;return OK;
}/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ S->top=-1;return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqStack S)
{ if (S.top==-1)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(SqStack S)
{ return S.top+1;
}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{if (S.top==-1)return ERROR;else*e=S.data[S.top];return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{if(S->top == MAXSIZE -1) /* 栈满 */{return ERROR;}S->top++;				/* 栈顶指针增加一 */S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */return OK;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ if(S->top==-1)return ERROR;*e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */S->top--;				/* 栈顶指针减一 */return OK;
}/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{int i;i=0;while(i<=S.top){visit(S.data[i++]);}printf("\n");return OK;
}int main()
{int j;SqStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("栈中元素依次为：");StackTraverse(s);Pop(&s,&e);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));ClearStack(&s);printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

两栈共享空间

前提：两个栈中的数据类型相同
使用场景：通常是当两个栈的空间需求有相反关系时，即一个栈增长时另一个栈在缩短。

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 两栈共享空间结构 */
typedef struct 
{SElemType data[MAXSIZE];int top1;	/* 栈1栈顶指针 */int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(SqDoubleStack *S)
{ S->top1=-1;S->top2=MAXSIZE;return OK;
}/* 把S置为空栈 */
Status ClearStack(SqDoubleStack *S)
{ S->top1=-1;S->top2=MAXSIZE;return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqDoubleStack S)
{ if (S.top1==-1 && S.top2==MAXSIZE)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(SqDoubleStack S)
{ return (S.top1+1)+(MAXSIZE-S.top2);
}/* 插入元素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;
}/* 若栈不空，则删除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;
}Status StackTraverse(SqDoubleStack S)
{int i;i=0;while(i<=S.top1){visit(S.data[i++]);}i=S.top2;while(i<MAXSIZE){visit(S.data[i++]);}printf("\n");return OK;
}int main()
{int j;SqDoubleStack s;int e;if(InitStack(&s)==OK){for(j=1;j<=5;j++)Push(&s,j,1);for(j=MAXSIZE;j>=MAXSIZE-2;j--)Push(&s,j,2);}printf("栈中元素依次为：");StackTraverse(s);printf("当前栈中元素有：%d \n",StackLength(s));Pop(&s,&e,2);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));for(j=6;j<=MAXSIZE-2;j++)Push(&s,j,1);printf("栈中元素依次为：");StackTraverse(s);printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));ClearStack(&s);printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

栈的链式存储结构及实现

栈的链式存储结构，简称为链栈。

栈只是栈顶来做插入和删除操作，栈顶应该在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必需的，所以好的办法是把栈顶放在单链表的头部。

因为已经有栈顶在头部了，所以单链表中的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top＝NULL的时候。

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 链栈结构 */
typedef struct StackNode
{SElemType data;struct StackNode *next;
}StackNode,*LinkStackPtr;typedef struct
{LinkStackPtr top;int count;
}LinkStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(LinkStack *S)
{ S->top = (LinkStackPtr)malloc(sizeof(StackNode));if(!S->top)return ERROR;S->top=NULL;S->count=0;return OK;
}/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{ LinkStackPtr p,q;p=S->top;while(p){  q=p;p=p->next;free(q);} S->count=0;return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(LinkStack S)
{ if (S.count==0)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(LinkStack S)
{ return S.count;
}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(LinkStack S,SElemType *e)
{if (S.top==NULL)return ERROR;else*e=S.top->data;return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */S->count++;return OK;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{ LinkStackPtr p;if(StackEmpty(*S))return ERROR;*e=S->top->data;p=S->top;					/* 将栈顶结点赋值给p，见图中③ */S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */free(p);                    /* 释放结点p */        S->count--;return OK;
}Status StackTraverse(LinkStack S)
{LinkStackPtr p;p=S.top;while(p){visit(p->data);p=p->next;}printf("\n");return OK;
}int main()
{int j;LinkStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("栈中元素依次为：");StackTraverse(s);Pop(&s,&e);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));ClearStack(&s);printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

顺序栈与链栈对比

对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了—些内存开销，但对于栈的长度无限制。

所以它们的区别和线性表—样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈。反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

而像线性表顺序存储结构用到的数组，因为要分散精力去考虑数组的下标增减等细节问题反而掩盖了问题的本质。

栈的应用——递归

斐波那契数列

#include "stdio.h"/* 斐波那契的递归函数 */
int Fbi(int i)  
{if( i < 2 )return i == 0 ? 0 : 1;  return Fbi(i - 1) + Fbi(i - 2);  /* 这里Fbi就是函数自己，等于在调用自己 */
}  int main()
{int i;int a[40];  printf("迭代显示斐波那契数列：\n");a[0]=0;a[1]=1;printf("%d ",a[0]);  printf("%d ",a[1]);  for(i = 2;i < 40;i++)  { a[i] = a[i-1] + a[i-2];  printf("%d ",a[i]);  } printf("\n");printf("递归显示斐波那契数列：\n");for(i = 0;i < 40;i++)  printf("%d ", Fbi(i));  return 0;
}

迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符台栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。

简单地说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳了。

栈的应用—四则运算表达式求值

"9 3 1 -3 *＋10 2／＋”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。