《数据结构与算法 C语言版》—— 3.1栈

3.1栈

3.1.1栈的抽象数据类型定义

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的栈称为空栈。由于后进栈的元素先出栈，所以栈又称为后进先出(Last In First Out，LIFO)的线性表。
在日常生活中，有很多后进先出的例子。例如，铁路调度站火车的进出是后进先出，人们脱衣服是后穿先脱等。在程序设计中，也常用栈这样的数据结构，实现与保存数据相反的顺序来使用这些数据。
栈的操作有栈的初始化、判空、进栈、出栈及取栈顶元素等。下面给出栈的抽象数据类型的定义：
ADT Stack {
数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=2,…,n}。约定an端为栈顶,a1端为栈底。
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
StackEmpty(S)
初始条件:栈S已存在。
操作结果:若栈S为空栈,则返回TRUE,否则返回FALSE。
Push(&S,e)
初始条件:栈S已存在。
操作结果:插入元素e为新的栈顶元素。
Pop(&S,&e)
初始条件:栈S已存在且非空。
操作结果:删除S的栈顶元素,用e返回其值。
GetTop(S)
初始条件:栈S已存在且非空。
操作结果:返回栈顶元素。
DestroyStack(&S)
初始条件:栈S已存在。
操作结果:栈S被销毁。
}ADT Stack

为了讨论方便，若没有特别说明，则假定ElemType为int类型，使用如下自定义类型语句定义：typedef int ElemType;。

3.1.2栈的表示与实现

由于栈是操作受到限制的线性表，所以栈也有顺序存储和链式存储两种方式。
1.顺序栈
利用顺序存储方式实现的栈称为顺序栈。与顺序表的定义一样，在C语言中栈也用动态分配的一维数组来描述其顺序存储结构。这样做的好处是：在应用过程中，当栈的空间不够使用时可以将其扩大。
顺序栈的类型描述如下:

#defineSTACK_INIT_SIZE 100//存储空间的初始分配量
#defineSTACKINCREMENT 10//存储空间分配增量
typedef int ElemType;
typedef struct{
ElemType *data;
int top;//栈顶指针
int stacksize;
}SqStack;

通常将数组的0下标作为栈底，这样空栈时栈顶指针top=-1；进栈时，栈顶指针加1，即top++；出栈时，栈顶指针减1，即top--。栈操作的示意图如图31所示。

图31a是空栈，图31b只有1个元素，图31c是元素a,b,c,d,e依次入栈后的情况；图31d是元素e,d依次出栈后的情况，出栈的元素还在原先的单元中，但指针top已指向新的栈顶元素。通过这个示意图可以帮助大家深刻理解栈顶指针的作用。
下面给出顺序存储结构中栈的基本操作的实现算法。
(1)栈的初始化
int InitStack(SqStack &s){//构造一个空顺序栈S，其存储空间大小为STACK_INIT_SIZE
s.data=new ElemType［STACK_INIT_SIZE］;
if(!s.data)exit(OVERFLOW);//存储分配失败
s.top =-1;//栈空
s.stacksize=STACK_INIT_SIZE;
return OK;
}
(2)进栈操作
int Push(SqStack &s,ElemType e){//将e插入栈顶
ElemType *p;
if(s.top>=s.stacksize-1){//栈满
p=(ElemType )realloc(s.data,(s.stacksize+STACKINCREMENT)sizeof(ElemType));
if(!p)exit(OVERFLOW);//存储分配失败
s.data=p;
s.stacksize=s.stacksize+STACKINCREMENT;
}
s.data［++s.top］=e;
return OK;
}
(3)出栈操作
int Pop(SqStack &s,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返

//回ERROR
if(s.top==-1)retur ERROR;
e=s.data［s.top--］;
return OK;
}
(4)取栈顶元素
ElemType GetTop(SqStack s){//栈已存在且不为空，返回栈顶元素
if(s.top==-1)return ERROR;
return s.data［s.top］;
}
(5)判断栈是否为空栈
int StackEmpty(SqStack s){
if(s.top==-1)return OK;
return ERROR;
}
需要注意的是，对于顺序栈，入栈时应首先判断栈是否满了，栈满的条件是S.top>=S.stacksize-1。栈满时不能入栈，否则将出现空间溢出，引起错误，这种现象称为上溢。解决的办法是追加存储空间。出栈和读取栈顶元素时，应先判断栈是否为空，为空时不能操作，否则将产生错误。通常栈空作为控制转移的条件。
2链栈
用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结点结构相同。在此用LinkStack表示链栈，即有：
typedef struct node{
ElemType data;
struct node *next;
}StackNode,*LinkStack;
LinkStack top;//top为栈顶指针
因为栈中的主要运算是在栈顶插入、删除，显然将链表的头部作为栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。通常将链栈表示成如图32所示的形式。

下面给出链栈基本操作的实现算法。
(1)置空栈
void InitStack(LinkStack &top){//构建一个空栈，栈顶指针为top
top=NULL;
}
(2)判栈空
int StackEmpty(LinkStack top){//判断栈是否为空栈
if(top==NULL) return OK;
else return ERROR;
}
(3)入栈
int Push(LinkStack &top,ElemType x){
StackNode *s;
s=new StackNode;
if(!s)exit(OVERFLOW);
s->data=x;
s->next=top;
top=s;
return OK;
}
(4)出栈
int Pop(LinkStack &top,ElemType &x){
StackNode *p;
if(top==NULL)return ERROR;
else{
x=top->data;
p=top;
top=top->next;
delete p;
returnOK;
}
}
链栈的入栈操作不需要判断栈是否已满，但出栈操作仍需要判断是否为空栈。