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

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第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_SIZEs.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；否则返

//回ERRORif(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){//构建一个空栈，栈顶指针为toptop=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;}}链栈的入栈操作不需要判断栈是否已满，但出栈操作仍需要判断是否为空栈。