数据结构-基础之栈的顺序存储表示与实现

 　　一、栈的定义

　　栈是限定仅在表尾进行插入或删除操作的线性表。

　　栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。

　　栈的抽象数据类型定义：

　　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(

　　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