清华大学：《数据结构》课程电子教案（PPT课件讲稿）Chapter4 Stacks Queues

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