顺序栈 与 链栈

和线性表类似，栈也有两种存储表示

 

一、顺序栈

顺序栈，即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序

栈中的位置。一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先给栈分配一个基本容量，然后在应用过程中，

当栈的空间不够使用时再逐段扩大，为此，设定两个常量：STACK_INIT_SIZE（存储空间初始分配量）和STACKINCREMENT（存储空间

分配增量）。

顺序栈的类型描述如下：

typedef struct {

　　SElemType *base;　　　　// 存储空间基址

　　SElemType *top; 　　　　// 栈顶指针

　　int stacksize;　　　　　// 允许的最大存储空间，以元素为单位

} SqStack;

其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在

顺序栈中，它始终指向栈底的位置，若base=null，则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标

记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此非空栈的栈顶指针始终在栈顶元素的下一个位置上。下图

展示了顺序栈中数据元素和栈顶指针之间的对应关系。

　　　　

栈顶指针top与栈中数据元素的关系

以下是顺序栈的模块说明。

ADT Stack的表示与实现：

//----------------------栈的顺序存储表示-------------------

typedef struct　{ 
　　　　SElemType *base;　　　　// 存储空间基址

　　SElemType *top;　　　 　 // 栈顶指针

　　int stacksize;　　　　　 // 允许的最大存储空间，以元素个数为单位

}　SqStack;

// --------------------基本操作接口( 函数声明 )-------------------

void InitStack (SqStack &S，int maxsize);

//　构造一个最大存储容量为maxsize的空栈S。

void DestroyStack (SqStack &S);

//　销毁栈S，S不再存在。

void ClearStack (SqStack &S);

//　将S置为空栈。

bool StackEmpty (SqStack S);

//　若栈S为空栈，则返回TRUE，否则返回FALSE。

int StackLength (SqStack S);

//　返回S的元素个数，即栈的长度。

bool GetTop Sq (Stack S, SElemType &e);

//　若栈不空，则用e返回S的栈顶元素，并返回TRUE；否则返回FALSE。

bool Push (SqStack &S, SElemType e);

//　若栈的存储空间不满，则插入元素e为新的栈顶元素，并返回TRUE；否则返回FALSE。

bool Pop (SqStack &S, SElemType &e);

//　若栈不空，则删除S的栈顶元素，用e返回其值，并返回TRUE；否则返回FALSE。

void StackTraverse(SqStack S, void (*visit(SElemType ))

//　依次对S的每个元素调用函数visit( )，一旦visit( )失败，则操作失败。

//------------------基本操作的算法描述（部分）--------------------

Status InitStack (SqStack &S)

{　// 构造一个空栈S

　　S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(sElemType));

　　Status GetTop

　　if (!S.base) exit(OVERFLOW);　　　//存储分配失败

　　S.top=S.base;

　　S.stacksize=STACK_INIT_SIZE;

　　return OK;

}　// InitStack

Status GetTop (SqStack S, SElemType &e)

{　// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR

　　if (S.top==S.base ) return ERROR;

　　e=*(S.top-1); 　　// 返回非空栈中栈顶元素

　　return OK;

}　// GetTop

status Push (SqStack &s, selemtype e)

{　if (s.top-s.base>=s.stacksize)

　{　//栈满追加存储空间

　　　s.base=(SElemtype *)

　　　realloc(s.base,(s.stacksize+STACKINCREMENT)* sizeof(SElemtype));

　　if(!s.base) exit(overflow);

　　s.top=s.base+s.stacksize;

　　s.stacksize+=STACKINCREMENT;

　}

　*s.top++=e;

　return OK;

}　// Push

status Pop(SqStack &s, selemtype &e)

{　if (S.top==S.base) return EEROR;　　　//栈空不能出栈

　　　e=*--S.top;　　　　　　　　　　　　 //栈顶元素存入e，返回

　　return ok;

}　// Pop

补充1：

入栈口诀：

堆栈指针top先压后加（s[top++]=e）；

出栈口诀：

堆栈指针top先减后弹（e=s[--top]）

补充2：

栈不存在的条件：base=NULL;

栈为空的条件：base=top;

栈满的条件：top-base=stacksize;（top 指向的是栈顶元素的下一个位置，故不要再加1）

 

二、链栈

链栈即为栈的链式存储结构。

链栈的定义更简单，结点结构和单链表中的结点结构相同，无须重复定义。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，

但要注意链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。

结构定义：

　　　typedef struct {

　　　　　SLink top; 　 　// 栈顶指针

　　　　　int length; 　　// 栈中元素个数

　　　} Stack;

链栈示意图

 

说明：

◆ 因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，没有必要象单链表那样为了运算方便附加一个头结点。

◆ 采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。

通常将链栈表示成上图的形式。基本操作和单链表类似，在此不作详细讨论。