Array Implementation #define STacK INiT size 100 #define STacKIncrement 10 typedef char StackData; typedef struct{顺序栈定义 StackData*base;/栈底指针 StackData*top;栈顶指针 int stacksize;/当前已分配的存储空间 3 SeqStack Note: O The stack model must be well encapsulated. That is, no part of your code, except for the stack routines, can attempt to access the Array or Top ofStack variable 2 Error check must be done before Push or Pop(Top)
➢ Array Implementation #define STACK_INIT_SIZE 100； #define STACKINCREMENT 10； typedef char StackData; typedef struct { //顺序栈定义 StackData *base; //栈底指针 StackData *top; //栈顶指针 int stacksize；//当前已分配的存储空间 } SeqStack； Note: The stack model must be well encapsulated. That is, no part of your code, except for the stack routines, can attempt to access the Array or TopOfStack variable. Error check must be done before Push or Pop (Top)
Basic operation of Array Implementation Create stack void initstack( Seqstack*S){/置空栈 S->base = StackData *)mallOc(STACK INIT SIZE sizeof( stackData)); if (S->base) exit(OVERFLOW) S->top S->base S->stacksize= STACK INIT SIZE Return ok
Basic operation of Array Implementation ▪ Create stack void InitStack ( SeqStack *S) { //置空栈 S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW); S->top = S->base ; S->stacksize= STACK_INIT_SIZE ; Return ok; }
a StackEmpty int StackEmpty(SeqStack *S)i if(S->top=S->base) return1判栈空空则返回1 else return0;/否则返回0 Makeempty void MakeEmpty(stack S) iS->top==S->base i
▪ StackEmpty int StackEmpty (SeqStack *S) { if( S->top == S->base ) return 1 //判栈空,空则返回1 else return 0; //否则返回0 } ▪ MakeEmpty void MakeEmpty(Stack s) {S->top == S->base ;}
■Push int Push(SeqStack*S, StackData x)i /插入元素x为新的栈顶元素 if( StackFull(S))i S->base = StackData *)malloc(S->base (S->stacksize+ STACKINCREMENT)X sizeof( stackData)); if( S->baseexit(overflow); S->top=S->base+S->stacksize; S-> stacksize+= STACKINCREMENT;/)加存储空间 (S->top)=x; (S->top)++; Return ok
▪ Push int Push (SeqStack *S, StackData x) { //插入元素x为新的栈顶元素 if ( StackFull (S) ){ S->base =( StackData *)malloc(S->base , (S->stacksize+ STACKINCREMENT) * sizeof(StackData)); if(! S->base)exit(overflow); S->top= S->base + S->stacksize; S->stacksize+= STACKINCREMENT; //追加存储空间 } *(S->top)=x; （S->top）++; Return ok }
OD int pop seqstack *S, StackData &x)t /若栈空返回0,否则栈顶元素退出到x并返回1 if( StackEmpty()) return 0; (S->top X=“(S->top) return 1 Gettop int Gettop(SeqStack *S, StackData &x)i /若栈空返回0,否则栈顶元素读到x并返回1 if( StackEmpty()) return 0; (S->top)-; X=“(S->top) return 1:
▪ Pop int pop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; --(S->top); x = *(S->top); return 1; } ▪ Gettop int Gettop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; (S->top)--; x = *(S->top); return 1;}