第3章栈和队列


栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制： 栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称它们是运算受限制的线性表。
3.1栈
在现实生活中有很多栈的实例。例如，手枪弹匣中的子弹，总是后压入的先弹出； 再比如，用盘子时，总是后摞上的先使用。
3.1.1栈的定义及运算
1. 栈的定义

栈（Stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除

图3.1栈示意图
的一端称为栈顶（Top），另一端称为栈底(Bottom)。栈的插入操作通常称为入栈或进栈(Push)，而栈的删除操作则称为出栈或退栈(Pop)。当栈中无数据元素时，称为空栈。
根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈； 栈底元素总是最先入栈的，也是最后出栈。这种表是按照后进先出（Last In First Out，LIFO）的原则组织数据的，因此，栈也被称为“后进先出”的线性表，栈的示意图如图3.1所示。

2. 栈的基本操作
在程序设计中，常常需要栈这样的数据结构，使得与保存数据时的相反顺序来使用这些数据。对于栈，常做的基本运算如下：
（1） Init_Stack(s)： 栈初始化。
操作结果： 构造了一个新的空栈。
（2） Empty_Stack(s)： 判别栈空。
操作结果： 如果栈s为空则返回1； 否则返回0。
（3） Top_Stack(s，e)： 读栈顶元素。
操作结果： 在栈s存在且非空的情况下，读出栈顶元素用e返回。
（4） Length_Stack(s)： 求栈的长度。
操作结果： 返回栈s中元素的个数，即栈的长度。
（5） Push_Stack(s,e)： 入栈。
操作结果： 在栈s的栈顶插入一个元素e，使e成为新的栈顶元素。
（6） Pop_Stack(s)： 出栈。
操作结果： 如果栈s存在且非空，则删除s的栈顶元素。
3.1.2栈的顺序存储结构（向量）
既然栈是线性表的特殊形式，所以它也可以采用顺序存储和链式存储两种结构。
1. 顺序存储结构
因为栈的插入和删除只在栈顶进行，不需要对其他数据元素进行移动，所以使用一个数组来存放栈的元素，并用栈顶指针top指向栈顶。对于C语言来讲，由于下标为0的数组元素也可以用来存放数据，所以可以用以下两种方法来实现栈。
（1） 用top=-1表示栈空的初始状态，用栈顶指针top指向栈顶结点在数组中的存储位置。当有新结点进栈时，首先执行top+1，使栈顶指针指向栈顶元素的下一个位置，然后将新结点送到top当前的位置上； 在执行出栈时，首先将栈顶结点送到一个接受变量中，然后执行top-1，使top指向新的栈顶结点，如果表示栈的数组共有Maxsize个元素，则当top=Maxsize-1时表示栈满，栈满时不能入栈。
（2） 用top=0表示栈空的初始状态，栈顶指针top指向栈顶元素的下一个存储位置，当有新的结点进栈时，首先把结点送到top所指的存储位置中，然后执行top+1，让top指向下次结点进栈的存储位置； 在做出栈操作时，首先执行top-1，然后把top所指的数据元素送到一个接受变量中。当top=Maxsize时，表示栈满。
本书中采用第一种方法来实现栈。类似于顺序表的定义，顺序栈中的数据元素用一个预设的足够长度的一维数组来实现： SElemType［Maxsize］，而栈顶是随着数据元素的插入和删除而变化的，用一个int top来作为栈顶指针指向当前栈顶的位置，同时将数组和栈顶指针封装到一个结构中，栈的顺序存储结构的类型描述如下。

#define Maxsize 100//设置栈的最大长度为100，可根据实际情况进行修改

typedef struct SqStack

{

SElemType elem［Maxsize］;//一维数组，用来存放栈中的数据元素

int top;//栈顶指针，用来存放栈顶元素的下标

}SqStack;

如果s为顺序结构栈SqStack类型的变量，则s.elem［0］是第一个进入栈中的数据元素，s.elem［s.top-1］为最后进入栈中的数据元素，即栈顶元素。当s.top=Maxsize-1时栈满，此时若再有元素入栈将会产生越界的错误，称为栈上溢（Overflow）； 反之，top=-1时为栈空，这时若执行出栈操作则产生下溢的错误（Underflow）。图3.2表示了顺序栈中数据元素和栈顶指针之间的对应关系。
图3.2(a)是空栈，图3.2(b)中只有一个元素A入栈，图3.2(c)是继A元素之后B、C、D、E这4个元素依次入栈，图3.2(d)是在图3.2(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素E、D仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则表示D、E已不在栈中了。


图3.2栈顶指针和栈中元素的关系

2. 顺序栈的基本操作
在上述存储结构上基本操作的算法描述如下： 
1） 栈的初始化

SqStack *Init_SqStack(void)

{/*创建一顺序栈，返回一个指向顺序栈的指针，为0表示分配空间失败*/

SqStack S;

S=(SqStack)malloc(sizeof(SqStack));

if (S)

{

S-top=-1;

printf("置空栈成功！＼n");

}

return S;

}

2） 判栈空

int Empty_SqStack(SqStack *S)

{/*判断栈是否为空，返回值为1表示栈空，值为0表示栈非空*/

if (S-top==-1)

return 1;

else

return 0;

}

3） 入栈

int Push_SqStack(SqStack *S)

{/*在栈顶插入一新元素x，返回值为1表示入栈成功，0表示失败*/

if (S-top==Maxsize-1)

return 0; /*栈满不能入栈*/

else 

{scanf(&x);

S-top++;

S-elem［S-top］=x;

return 1;

}

}

4） 出栈

intPop_SqStack(SqStack *S, DataType *x)

{/*删除栈顶元素并保存在变量x中，返回值为1表示出栈成功，为0表示失败*/

if (Empty_SqStack(S))

return 0;/*栈空不能出栈*/

else

{*x=S-elem［S-top］;

S-top--;

return 1;

} 

}

5） 取栈顶元素

intGetTop_SqStack(SqStack *S, DataType *x)

{/*取出栈顶元素，返回值为1表示成功，为0表示失败*/

if (Empty_SqStack(S)) 

return 0;/*栈空*/

else

{*x=S-elem［S-top］;/*栈顶元素存入x中*/

return 1;

}

}

【例3.1】利用顺序栈结构输入一组数据，程序要求实现： 栈的初始化； 数据入栈； 出栈； 取栈顶元素； 输出栈中元素； 退出。
参考程序如下：

#include stdio.h 

#include stdlib.h 

#define MAXSIZE 100 

typedef struct SqStack 

{ 

int elem［MAXSIZE］; 

int top; 

}SqStack,*stack_type; 

stack_type Init_SqStack()

{/*创建一顺序栈，返回一个指向顺序栈的指针，为0表示分配空间失败*/

SqStack *S;

S=(stack_type)malloc(sizeof(SqStack));

if(S)

{

S-top=-1;

printf("置空栈成功！＼n");

}

return S;

}

int Empty_SqStack(stack_type S)

{/*判断栈是否为空，返回值为1表示栈空，为0表示栈非空*/

 if(S-top==-1)

 return 1;

 else

 return 0;

}

int Push_SqStack(stack_type S)

{/*在栈顶插入一新元素x，返回值为1表示入栈成功，为0表示失败*/

 int n;

if (S-top==MAXSIZE-1)

 {printf("栈是满的!＼n");

 return 0; /*栈满不能入栈*/

 }

 else 

 printf("请输入需要入栈的数据个数:＼n");

 scanf("%d",&n);

 printf("请依次输入需要入栈的数据:＼n");

 while(S-topn-1)

 {S-top++;

 scanf("%d",&S-elem［S-top］); 

 }

printf("push success!＼n");

return 1;

}

int Pop_SqStack(stack_type S,int *tmp)

{/*删除栈顶元素并保存在变量x中，返回值为1表示出栈成功，为0表示出栈失败*/

if(Empty_SqStack(S))

{ printf("栈是空的＼n");

return 0;/*栈空不能出栈 */

}

else

{*tmp=S-elem［S-top］;

 S-top--;

 return 1;

} 

}

int GetTop_SqStack(stack_type S,int *tmp)

{/*取出栈顶元素，返回值为1表示成功，为0表示失败*/

if(Empty_SqStack(S)) 

return 0;/*栈空*/

else

{*tmp=S-elem［S-top］;/*栈顶元素存入x中*/

 return 1;

}

}

void Print_SqStack(stack_type s) 

{ 

int i=s-top; 

for(;i=0;i--) 

printf("%d ",s-elem［i］); 

printf("＼n");

} 

void main() 

{ 

int select,data,k,k1; 

stack_type s; 

printf("＼n"); 

printf(" ------------＼n"); 

printf(" 1： 栈的初始化＼n"); 

printf(" 2： 数据入栈＼n"); 

printf(" 3： 出栈＼n");

printf(" 4： 取栈顶元素＼n");

printf(" 5： 输出栈中元素＼n"); 

printf(" 6： 退出＼n"); 

printf("  ------------＼n"); 

printf("请选择相应的选项： ＼n"); 

scanf("%d",&select); 

while(select) 

{ 

switch(select) 

{ 

case 1:s=Init_SqStack();break; 

case 2:Push_SqStack(s); break; 

case 3:k=Pop_SqStack(s,&data);

if(k)printf("出栈的元素为:%d＼n",data); break; 

case 4:k1=GetTop_SqStack(s,&data);

if(k1)printf("当前的栈顶元素为:%d＼n",data);break;

case 5:Print_SqStack(s);break; 

case 6:exit(0);

default: printf("＼ninout error!"); 

} 

printf("请选择相应的选项： ＼n"); 

scanf("%d",&select); 

} 

}

程序运行结果如图3.3所示。


图3.3例3.1程序运行结果

3.1.3栈的链式存储结构
栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表中的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表示，即有

typedef struct node

{ datatype data； 

struct node *next； 

}StackNode，*LinkStack； 

因为栈主要是在栈顶进行插入、删除等运算，显然在链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3.4所示的形式。


图3.4链栈示意图

链栈基本操作的实现如下：
1） 置空栈 

LinkStackInit_LinkStack（）

{returnNULL； 

}

2） 判栈空

intEmpty_LinkStack(LinkStack top)

{if(top==-1) return 1；  

elsereturn 0； 

}

3） 入栈

LinkStack Push_LinkStack(LinkStack top，datatype x)

{ StackNode *s； 

s=(StackNode *)malloc(sizeof(StackNode))； 

s-data=x；  

s-next=top； 

top=s； 

return top； 

}

4） 出栈

LinkStack Pop_LinkStack (LinkStack top，datatype *x)

{StackNode *p； 

if (top==NULL) return NULL； 

else 

{ *x=top-data； 

p=top； 

top=top-next； 

free (p)； 

return top；  

}

}

【例3.2】利用栈的链式存储结构，将一组数据入栈并输出，然后弹出栈中一个元素后再输出栈中元素。
参考程序如下：

#includestdio.h

#includemalloc.h

typedef struct node

{

int data;

struct node*next;

}StackNode,*LinkStack;

LinkStack ls=NULL;

intEmpty_LinkStack(LinkStack p)

{if(p==NULL) return 0; 

elsereturn 1; 

}

void push(LinkStack *ls,int *x)

{ 

LinkStack p;

p=(LinkStack)malloc(sizeof(StackNode));

p-data=*x;

p-next=*ls;

*ls=p;

}

int Pop(LinkStack *ls,int *y)

{

LinkStack p;

if(Empty_LinkStack(*ls))

{

p=*ls;

*y=p-data;

*ls=(*ls)-next;

p-next=NULL;

free(p);

return *y;

}

else

return 0;

}

void print()

{ LinkStack p;

p=ls;

printf("输出栈中元素： ＼n");

while(p !=NULL)

{

printf("%d",p-data);

p=p-next;

}

printf("＼n");

}

void main ()

{

int n,i,x,y;

printf("请输入需要进栈的数据个数:＼n");

scanf("%d",&n);

printf("请输入一组需要进栈的数据:＼n");

for(i=0;in;i++)

{ 

scanf("%d",&x);

push(&ls,&x);

}

print();

printf("弹出的栈顶元素为: %d＼n",Pop(&ls,&y));

print();

}

程序运行结果如图3.5所示。


图3.5例3.2程序运行结果

3.1.4栈的应用
1. 表达式计算

栈的另外一个应用是用来做算术表达式的求值。下面对表达式做出简化： 
 假定所有运算分量都是整数。
 所有运算符都是整数的二元操作，且都用一个字符表示。
1） 后缀表达式的求值
设e是由一个操作数和操作符组成的表达式，如果每一个双目操作符都放在它的两个操作数之间，单目操作符都放在它的操作数前面，这样的表达式叫做中缀（Infix）表达式，如A+B*(C-D)-E/F就是中缀表达式。
后缀（Postfix）表达式也叫做RPN或逆波兰记号，它是中缀表达式的替代形式，参加运算的操作数总是在操作符前面。例如，中缀表达式A+B用后缀表达式可以表示为AB+，更为复杂的中缀表达式A+B*(C-D)-E/F所对应的后缀表达式为ABCD-*+EF/-。
利用后缀表达式求值时，从左向右顺序的扫描表达式，并使用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已经隐含了加括号的优先次序，因而括号在后缀表达式中不出现（这里讲解只涉及双目操作数，不考虑单目操作数）。
通过后缀表达式计算表达式值的过程为： 顺序扫描表达式的每一项，根据它的类型做如下操作： 如果该项是操作数，则将其压入栈中； 如果该项是操作符<op>，则连续从栈中退出两个操作数X和Y，形成运算指令X<op>Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完，栈顶存放的就是最后的计算结果R5。
下面用如表3.1所示的步骤来表示后缀表达式ABCD-*+EF/-的计算过程，它的计算共需要12步。