CHAPTER 4 Stacks and Queues 81 The Stack ADT L ADT A stack is a Last-In-First-Out(LIFO) list, that is an ordered list in which insertions and deletions are made at the top only Objects: A finite ordered list with zero or more elements Operations cInt StackEmpty Stack S) cInt Stack Full( Stack S); cG Stack Init Stack (; G MakeEmpty( Stack S ) Note: A Pop(or Get Top)on CG Push( Element Type X, Stack S) an empty stack is an error in the stack adt Element Type Get Top( Stack S) Push on a full stack is C Pop( Stack S) an implementation error but not an adt error
§1 The Stack ADT 1. ADT 1 2 3 4 5 6 65 6 5 A stack is a Last-In-First-Out (LIFO) list, that is, an ordered list in which insertions and deletions are made at the top only. Objects: A finite ordered list with zero or more elements. Operations: Int StackEmpty( Stack S ); Int StackFull( Stack S ); Stack InitStack( ); MakeEmpty( Stack S ); Push( ElementType X, Stack S ); ElementType GetTop( Stack S ); Pop( Stack S ); Note:A Pop (or GetTop) on an empty stack is an error in the stack ADT. Push on a full stack is an implementation error but not an ADT error. CHAPTER 4 Stacks and Queues
2. Implementations Linked List Implementation typedef int StackData; typedef struct node i StackData data; 结点 struct node xlink;/链指钅 i StackNode; typedef struct t StackNode“top; /栈顶指针 3 Linkstack
2. Implementations ➢ Linked List Implementation typedef int StackData; typedef struct node { StackData data; //结点 struct node *link; //链指针 } StackNode; typedef struct { StackNode *top; //栈顶指针 } LinkStack;
Basic operation of Linked List Implementation a Create void InitStack( LinkStack S)& S->top= NULL ■Push int Push( LinkStack *S, StackData x)t StackNode *p=( StackNode *) malloc sizeof( stackNode )) p->data=X; p->link=S->top S->top= p; return 1
Basic operation of Linked List Implementation ▪ Create void InitStack ( LinkStack *S ) { S->top = NULL; } ▪ Push int Push ( LinkStack *S, StackData x ) { StackNode *p = ( StackNode * ) malloc ( sizeof ( StackNode ) ); p->data = x; p->link = S->top; S->top = p; return 1; }
StackEmpty int Stack Empty (Link Stack *S)( return s->tol p NULL Pop int Pop( linkstack *S, Stack Data &x)t if( Stack Empty(S)) return 0; StackNode *p=S->top S->top=p->link >data free(p) return 1
▪ StackEmpty int StackEmpty (LinkStack *S) { return S->top == NULL; } ▪ Pop int Pop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; StackNode * p = S->top; S->top = p->link; x = p->data; free (p); return 1; }
GetTop int GetTop( linkStack * S, StackData &x)t if( StackEmpty(S)) return 0; x=S->top->data return 1 Makeempty int MakeEmpty( LinkStack *S)t While(s->top !=NULL StackNode x S->top; S->top=S->top ->links free(p)
▪ GetTop int GetTop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; x = S->top->data; return 1; } ▪ MakeEmpty int MakeEmpty ( LinkStack *S) { While(S->top!=NULL){ StackNode * p = S->top; S->top = S->top ->link; free(p); } }
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;}