一、棧的定義
棧是限定僅在表尾進行插入或刪除操作的線性表。
棧的表尾稱為棧頂，表頭稱為棧底，不含元素的空表稱為空棧。
棧的抽象數據類型定義：
ADT Stack{
數據對象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
數據關系:R1={|ai-1,ai(- D,i=2,...,n}
基本操作:
InitStack(&S) 構造一個空棧S
DestroyStack(&S) 棧S存在則棧S被銷毀
ClearStack(&S) 棧S存在則清為空棧
StackEmpty(S) 棧S存在則返回TRUE,否則FALSE
StackLength(S) 棧S存在則返回S的元素個數,即棧的長度
GetTop(S,&e) 棧S存在且非空則返回S的棧頂元素
Push(&S,e) 棧S存在則插入元素e為新的棧頂元素
Pop(&S,&e) 棧S存在且非空則刪除S的棧頂元素並用e返回其值
StackTraverse(S,visit())棧S存在且非空則從棧底到棧頂依次對S的每個數據元素調用函數visit()一旦visit()失敗,則操作失敗
}ADT Stack
二、棧的表示和實現
棧的存儲方式：
1、順序棧:利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素,同時附設指針top指示棧頂元素在順序棧中的位置
2、鏈棧:利用鏈表實現
順序棧的類C語言定義:
typedef struct{
SElemType *base;
SElemType *top; //設棧頂棧底兩指針的目的是便於判斷棧是否為空
int StackSize; //棧的當前可使用的最大容量.
}SqStack;
順序棧的的模塊說明:
struct STACK {
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct STACK Sqstack;
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
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
Status Push(SqStack &S,SElemType e); {
if(S.top - s.base>=S.stacksize) {
S.base=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
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 ERROR;
e=*--S.top;
return OK;
}//Pop
Status StackTraverse(SqStack S,Status (*visit)()); {
}//StackTraverse
以上偽代碼的C語言源碼
三、總結
棧的定義
棧的順序存儲實現
