3.1 栈
在第2章中学习了线性表，其中对于线性表的操作允许在表的任何位置进行，使用比较灵活，同时也使得实现操作时需要考虑的因素较多。本章要介绍的栈和队列是一类操作受限制的特殊线性表，其特殊性在于限制线性表插入和删除等运算的位置。栈和队列在各种类型的软件系统中应用广泛。栈技术被广泛应用于编译软件和程序设计中，队列技术被广泛应用在操作系统和事务管理中。
栈和队列是两种重要的线性数据结构，也是两种特殊的线性数据结构。从数据的逻辑结构角度看，栈和队列是线性表；从运算的角度看，栈和队列的基本运算是线性表运算的子集，是操作受限的线性表。本章介绍栈和队列的概念、存储结构和基本运算的实现算法。
本章主要内容
& 栈和队列的特性及它们之间的差异
& 顺序栈上和链栈上实现栈的基本操作
& 链队上和顺序队上实现队列的基本操作
& 栈和队列各种基本操作的实现原理
3.1 栈
我们在编写程序的时候经常会发现，程序中处理的信息往往具有线性的结构，但并不需要用到线性表数据类型中的所有操作。在某些特定的应用中，检查、修改、插入和删除操作仅在表的一端进行。由于这种受限的线性结构在程序设计中用得十分普遍，因此，有必要将它作为单独的抽象数据类型来考虑。本节将讨论这种重要的受限线性结构——栈。
3.1.1 抽象数据类型栈的定义
栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。
栈的特点是后进先出。举一个例子说明栈结构的特征，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有5个人，分别编号为①～⑤，按编号的顺序依次进入此胡同，如图3-1所示。此时若编号为④的人要退出胡同，必须等⑤退出后才可以。若①要退出，则必须等到⑤④③②依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。死胡同示意图如图3-1所示。
|
图3-1 死胡同示意图
|
栈的基本运算至少应包括以下5种：
（1）初始化栈InitStack(st)。其作用是设置一个空栈st。
（2）进栈Push(st,x)。其作用是将元素x插入栈st中，使x成为栈st的栈顶元素。
（3）出栈Pop(st,x)。其作用是当栈st不空时，将栈顶元素赋给x，并从栈中删除当前栈顶。
（4）取栈顶元素GetTop(st)。若栈st不空，则由x返回栈顶元素；当栈st为空时，结果为一特殊标志。
（5）判断栈空StackEmpty(st)。若栈st为空栈，则结果为1；否则结果为0。
【例3-1】跟踪以下代码，显示每次调用后栈中的内容。
InitStack(st); /*设置一个空栈st*/
Push(st,'A'); /*将元素A插入栈st中*/
Push(st,'B'); /*将元素B插入栈st中*/
Push(st,'C'); /*将元素C插入栈st中*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
Push(st,'D'); /*将元素D插入栈st中*/
Push(st,'E'); /*将元素E插入栈st中*/
Push(st,'F'); /*将元素F插入栈st中*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
Push(st,'G'); /*将元素G插入栈st中*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
Pop(st,x); /*从栈中删除当前栈顶元素*/
解：栈中的内容见以下说明。
InitStack(st); /*空栈*/
Push(st,'A'); /*栈内容：A*/
Push(st,'B'); /*栈内容：A,B*/
Push(st,'C'); /*栈内容：A,B,C*/
Pop(st,x); /*栈内容：A,B*/
Pop(st,x); /*栈内容：A*/
Push(st,'D'); /*栈内容：A,D*/
Push(st,'E'); /*栈内容：A,D,E*/
Push(st,'F'); /*栈内容：A,D,E,F*/
Pop(st,x); /*栈内容：A,D,E*/
Push(st,'G'); /*栈内容：A,D,E,G*/
Pop(st,x); /*栈内容：A,D,E*/
Pop(st,x); /*栈内容：A,D*/
Pop(st,x); /*栈内容：A*/
3.1.2 栈的表示和实现
1．栈的顺序存储及其基本运算
和线性表类似，栈也有两种存储结构：顺序存储结构和链式存储结构。
栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。假设用一维数组sq[5]（下标0～4）表示一个栈，则需使用一个变量top记录当前栈顶下标值。图3-2所示为这个顺序栈的几种状态。
图3-2 顺序栈的几种状态
（a）表示顺序栈为空栈，这也是初始化运算得到的结果。此时栈顶下标值top= -1。如果作出栈运算，则产生“下溢”。
（b）表示栈中只含一个元素A，在（a）的基础上用进栈运算Push(sq,'A')，可以得到这种状态。此时栈顶下标值top=0。
（c）表示在（b）基础上又有2个元素B、C先后进栈，此时栈顶下标值top=2。
（d）表示在（c）状态下，执行一次Pop(sq,x)运算得到。此时栈顶下标值top=1。故B为当前的栈顶元素。
（e）表示在（d）状态下，执行2次Pop(sq,x)运算得到。此时栈顶下标值top= -1，又变成空栈状态。
顺序栈类型定义如下：
#define StackSize /*顺序栈的初始分配空间*/
typedef struct
{
ElemType data[StackSize]; /*保存栈中元素*/
int top; /*栈指针*/
} SqStack;
顺序栈被定义为一个结构体类型，它有两个域：data和top。data为一个一维数组，用于存储栈中元素，ElemType为栈元素的数据类型，可以根据需要而指定为某种具体的类型。top为int型，它的实际取值范围为0～StackSize-1。
顺序栈st的四要素：
· 栈空 st.top= -1
· 栈满 st.top=StackSize-1
· 进栈操作 st.top++; st.data[st.top]=x
· 出栈操作 x=st.data[st.top]; st.to--
顺序栈的基本运算算法如下。
（1）初始化栈运算算法。
用于创建一个空栈，并将栈顶下标top初始化为-1。
void InitStack(SqStack &st) /*st为引用型参数*/
{
st.top=-1;
}
（2）进栈运算算法。
其主要操作是：栈指针加1，将进栈元素放进栈顶位置上。
int Push(SqStack &st,ElemType x) /*进栈运算，st为引用型参数*/
{
if(st.top==StackSize-1) /*栈满*/
return 0;
else /*栈不满*/
{
st.top++;
st.data[st.top]=x;
return 1;
}
}
（3）出栈运算算法。
其主要操作是：先将栈顶元素取出，然后将栈指针减1。
int Pop(SqStack &st,ElemType &x) /*出栈运算，st和x为引用型参数*/
{
if(st.top==-1) /*栈空*/
return 0;
else /*栈不空*/
{
x=st.data[st.top];
st.top--;
return 1;
}
}
（4）取栈顶元素运算算法。
其主要操作是：将栈指针处的元素取出赋给变量x。
int GetTop(SqStack st,ElemType &x) /*取栈顶元素,x为引用型参数*/
{
if(st.top==-1) /*栈空*/
return 0;
else
{
x=st.data[st.top];
return 1;
}
}
（5）判断栈空运算算法。
其主要操作是：若栈为空（top== -1）则返回1，否则返回0。
int StackEmpty(SqStack st) /*判断栈空运算*/
{
if(st.top==-1) /*栈空*/
return 1;
else /*栈不空*/
return 0;
}
当顺序栈的基本运算函数设计好后，给出以下程序调用这些基本操作函数，读者可以对照程序执行结果进行分析，进一步体会顺序栈各种操作的实现过程。
void main()
{
SqStack st; /*定义顺序栈st*/
ElemType e; /*定义栈元素e的类型*/
InitStack(st); /*创建空栈st*/
printf("栈%s\n",(StackEmpty(st)==1?"空":"不空"));
printf("a进栈\n");Push(st,'a');
printf("b进栈\n");Push(st,'b');
printf("c进栈\n");Push(st,'c');
printf("d进栈\n");Push(st,'d');
printf("栈%s\n",(StackEmpty(st)==1?"空":"不空"));
GetTop(st,e); /*取栈顶元素*/
printf("栈顶元素:%c\n",e);
printf("出栈次序:");
while(!StackEmpty(st)) /*栈不空时循环*/
{
Pop(st,e); /*栈不空时元素出栈*/
printf("%c ",e); /*显示出栈元素*/
}
printf("\n");
}
上述程序的执行结果如下：
栈空
a进栈
b进栈
c进栈
d进栈
栈不空
栈顶元素:d
出栈次序：d c b a
【例3-2】利用栈的基本运算编写一个算法，输入若干整数，以0标识输入结束。然后按与输入相反次序输出这些整数。
解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法如下。
void Invert()
{
int n; /*将ElemType类型改为int*/
SqStack st; /*定义顺序栈st*/
InitStack(st); /*创建空栈st*/
printf("输入一串整数(以0标识结束)");
while (1)
{
scanf("%d",&n);
if (n==0) break; /*输入值n为0时退出循环*/
Push(st,n); /*每输入一个n进栈*/
}
printf("输出序列:");
while(!StackEmpty(st)) /*栈不空时循环*/
{
Pop(st,n); /*出栈n*/
printf("%d ",n); /*输出n*/
}
}
2．栈的链式存储及其基本运算
栈的链式存储结构是以某种形式的链表作为栈的存储结构，栈的链式存储结构简称为链栈，其组织形式与单链表类似，如图3-3所示。其中，单链表的第一个节点就是链栈栈顶节点。ls称为栈顶指针。类似地，栈由栈顶指针ls唯一确定。栈中的其他节点通过它们的next域链接起来。栈底节点的next域为NULL。因链栈本身没有容量限制，所以在用户内存空间的范围内不会出现栈满情况。
图3-3 用不带头节点的单链表表示链栈
链栈的类型定义如下：
typedef struct stnode
{
ElemType data; /*存储节点数据*/
struct stnode *next; /*指针域*/
} LinkStack;
链栈ls的四要素如下：
· 栈空 ls==NULL
· 栈满 不存在
· 进栈操作 p->next=ls; ls=p
· 出栈操作 ls=ls->next
栈的基本运算算法如下。
（1）初始化栈运算算法。
创建一个栈头节点*ls，用ls=NULL标识栈为空栈。
void InitStack(LinkStack *&ls) /*ls为引用型参数*/
{
ls=NULL;
}
（2）进栈运算算法。
其主要操作是：先创建一个新节点，其data域值为x；然后将该节点插入到单链表表头作为栈顶节点。
void Push(LinkStack *&ls,ElemType x) /*进栈运算，ls为引用型参数*/
{
LinkStack *p;
p=(LinkStack *)malloc(sizeof(LinkStack));
p->data=x;
p->next=ls;
ls=p;
}
（3）出栈运算算法。
其主要操作是：将栈顶节点（即ls所指节点）的data域值赋给x，然后删除该栈顶节点。
int Pop(LinkStack *&ls,ElemType &x) /*出栈运算，ls为引用型参数*/
{
LinkStack *p;
if(ls==NULL) /*栈空，下溢出*/
return 0;
else
{
p=ls;
x=p->data;
ls=p->next;
free(p);
return 1;
}
}
（4）取栈顶元素运算算法。
其主要操作是：将栈顶节点（即ls所指节点）的data域值赋给x。
int GetTop(LinkStack *ls,ElemType &x) /*取栈顶元素运算*/
{
if(ls==NULL) /*栈空，下溢出*/
return 0;
else
{
x=ls->data;
return 1;
}
}
（5）判断栈空运算算法。
其主要操作是：若栈为空（即ls==NULL）则返回1，否则返回0。
int StackEmpty(LinkStack *ls) /*判断栈空运算*/
{
if(ls==NULL)
return 1;
else
return 0;
}
当链栈的基本运算函数设计好后，给出以下程序调用这些基本操作函数，读者可以对照程序执行结果进行分析，进一步体会链栈各种操作的实现过程。
void main()
{
LinkStack *ls; /*定义链栈ls*/
ElemType e; /*定义栈元素e的数据类型*/
InitStack(ls); /*创建链栈ls*/
printf("栈%s\n",(StackEmpty(ls)==1?"空":"不空"));
printf("a进栈\n");Push(ls,'a');
printf("b进栈\n");Push(ls,'b');
printf("c进栈\n");Push(ls,'c');
printf("d进栈\n");Push(ls,'d');
printf("栈%s\n",(StackEmpty(ls)==1?"空":"不空"));
GetTop(ls,e); /*取栈顶元素*/
printf("栈顶元素:%c\n",e);
printf("出栈次序:");
while (!StackEmpty(ls)) /*栈不空时循环*/
{
Pop(ls,e); /*出栈*/
printf("%c ",e);
}
printf("\n");
}
上述程序执行结果与顺序栈对应主程序的执行结果相同。
【例3-3】假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。
（1）下面所示的序列中哪些是合法的？
A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO
（2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法则返回1；否则返回0（假设被判定的操作序列已存入一维数组中）。
解：
（1）A、D均合法，而B、C不合法。因为在B中，先进栈一次，立即出栈两次，这会造成栈下溢。在C中共进栈5次，出栈3次，栈的终态不为空。
（2）本例用一个链栈来判断操作序列是否合法，其中A为存放操作序列的字符数组，n为该数组的元素个数（这里的ElemType类型设置为char）。
int Judge(char A[ ],int n)
{
int i;
ElemType x;
LinkStack *ls;
InitStack(ls); /*初始化*/
for (i=0;i<n;i++)
{
if(A[i]=='I') /*进栈*/
Push(ls,A[i]);
else if (A[i]=='O') /*出栈*/
Pop(ls,x);
else return 0; /*其他值无效退出*/
}
return(ls->next==NULL); /*栈为空时返回1；否则返回0*/
}