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); } }