一、棧的定義

　　棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。

　　棧的表尾稱(chēng)為棧頂，表頭稱(chēng)為棧底，不含元素的空表稱(chēng)為空棧。

　　棧的抽象數(shù)據(jù)類(lèi)型定義：

　　ADT Stack{

　　數(shù)據(jù)對(duì)象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}

　　數(shù)據(jù)關(guān)系:R1={|ai-1,ai(- D,i=2,...,n}

　　基本操作:

　　InitStack(&S) 構(gòu)造一個(gè)空棧S

　　DestroyStack(&S) 棧S存在則棧S被銷(xiāo)毀

　　ClearStack(&S) 棧S存在則清為空棧

　　StackEmpty(S) 棧S存在則返回TRUE,否則FALSE

　　StackLength(S) 棧S存在則返回S的元素個(gè)數(shù),即棧的長(zhǎng)度

　　GetTop(S,&e) 棧S存在且非空則返回S的棧頂元素

　　Push(&S,e) 棧S存在則插入元素e為新的棧頂元素

　　Pop(&S,&e) 棧S存在且非空則刪除S的棧頂元素并用e返回其值

　　StackTraverse(S,visit())棧S存在且非空則從棧底到棧頂依次對(duì)S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()一旦visit()失敗,則操作失敗

　　}ADT Stack

　　二、棧的表示和實(shí)現(xiàn)

　　棧的存儲(chǔ)方式：

　　1、順序棧:利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置

　　2、鏈棧:利用鏈表實(shí)現(xiàn)

　　順序棧的類(lèi)C語(yǔ)言定義:

　　typedef struct{

　　SElemType *base;

　　SElemType *top; //設(shè)棧頂棧底兩指針的目的是便于判斷棧是否為空

　　int StackSize; //棧的當(dāng)前可使用的最大容量.

　　}SqStack;

　　順序棧的的模塊說(shuō)明:

　　struct STACK {

　　SElemType *base;

　　SElemType *top;

　　int stacksize;

　　};

　　typedef struct STACK Sqstack;

　　Status InitStack(SqStack &S);

　　Status DestroyStack(

　　Status ClearStack(SqStack &S);

　　Status StackEmpty(SqStack S);

　　int StackLength(SqStack S);

　　Status GetTop(SqStack S,SElemType &e);

　　Status Push(SqStack &S,SElemType e);

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

　　Status StackTraverse(SqStack S,Status (*visit)());

　　Status InitStack(SqStack &S) {

　　S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));

　　if(!S.base)exit(OVERFLOW);

　　S.top=S.base;

　　S.stacksize=STACK_INI_SIZE;

　　return OK;

　　}//IniStack

　　Status DestroyStack(SqStack &S); {

　　}//DestroyStack

　　Status ClearStack(SqStack &S); {

　　S.top=S.base;

　　} //ClearStack

　　Status StackEmpty(SqStack S); {

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

　　else return FALSE;

　　} //StackEmpty

　　int StackLength(SqStack S); {

　　int i; SElemType *p;

　　i=0;

　　p=S.top;

　　while(p!=S.base) {p++; i++; }

　　} //stackLength

　　Status GetTop(SqStack S,SElemType &e); {

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

　　e=*(S.top-1);

　　return OK;

　　} //GetTop