3.3栈 1.栈 stack的定y 栈是特殊的线性表,仅在表的一端进行插入或删除操作 入栈 出栈 栈顶 an a2 栈底a1 特点:(1)对栈内数据的操作总在栈顶进行 (2)数据进栈称为“压入"push (3)数据出栈称为“弹出”pop (4)遵循“后进先出”的原则LFO
3.3 栈 1. 栈 stack的定义 栈是特殊的线性表，仅在表的一端进行插入或删除操作 an ... a2 a1 栈顶 入栈 出栈 栈底 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则LIFO
3.3栈 输入顺序ABc,输出顺序有几种? 入栈 出栈 栈顶 an B=A B—A a2 栈底a1 ABC BAC BCA CBA
3.3 栈 输入顺序A,B,C，输出顺序有几种？ an ... a2 a1 栈顶 入栈 出栈 栈底 ABC,BAC,BCA,CBA B C A B A ...
栈的顺序存储结构及运犷 用数组实现栈 ao为栈底,top为栈顶一栈顶元素amax] (1)定义 所在位置 new one typedef struct stack typet a[op]栈顶 elemtype data[MAXNUM] int top; 3stack_ type a[1]a2 a[0] a (2)进栈push 当新元素进栈时,栈顶上移,新元素放在栈顶。 stacktop= stacktop 1; stack data [stack top= new one
栈的顺序存储结构及运算 用数组实现栈 a[max] ... a[1] a[0] ... a[top] 栈顶 a[0]为栈底，top为栈顶 （1）定义 typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; （2）进栈 push 当新元素进栈时，栈顶上移，新元素放在栈顶。 ... stack.top = stack.top + 1; stack.data[stack.top] = new_one; new_one 栈顶元素 所在位置 a1 a2
的顺序存储结构及运算 (3)出栈pop 从栈顶移出一个数据。 a[max] 栈顶元素拷贝出栈,栈顶下移 out aop栈顶 out= stack data[stack topI stack top= stacktop.1; elemptype pop( stack type*stack) a a2 elemtype out a[0]a if(stack->top data [stack->top stack->top= stack->top-19 return out, 1
栈的顺序存储结构及运算 ... （3）出栈 pop 从栈顶移出一个数据。 a[max] ... a[1] a[0] a1 a2 栈顶元素拷贝出栈，栈顶下移 out 栈顶 out = stack.data[stack.top]; stack.top = stack.top - 1; elemptype pop(stack_type *stack){ elemtype out; if(stack->top data[stack->top]; stack->top = stack->top -1; } return out; } a[top]
栈的顺序存储结构及运犷 (4)栈空判断 stacktop==0 X stack, top s0 stack top a 0I 栈顶元素所在位置 栈满判断: stack top≥ MAXNUM-1; (5)置栈空 stack top =1;
栈的顺序存储结构及运算 （4）栈空判断 stack.top = = 0 stack.top = MAXNUM - 1; stack.top a[0] 栈顶元素所在位置
用数组奥现栈 (6)栈的应用 例程序的嵌套,中断的嵌套 proc Ao proc Bo proc call BOiK call COK 口■■■口口口■口■口口■ 程序C 程序B 程序A
用数组实现栈 （6）栈的应用 例 程序的嵌套，中断的嵌套 proc A( ) ...... call B( ); ...... proc B( ) ...... ...... call C( ) ...... proc C( ) ...... ...... ...... 程序A 程序B 程序C
用数组奥现 (6)栈的应用 程序的嵌套,中断的嵌套 ■"■ proc A( proc b( proc call BO; call(()月 程序C 程序B 程序A
用数组实现栈 （6）栈的应用 程序的嵌套，中断的嵌套 proc A( ) ...... call B( ); ...... proc B( ) ...... ...... call C( ) ...... proc C( ) ...... ...... ...... 程序A 程序B 程序C 程序A 程序B 程序C
栈的链弌存储结构及运箕 用链表实现栈 入栈 出栈a1 a2 圆■■■■ an Httpd 栈顶在表头 (1)定义 typedef struct Stack_ type( node type* top; int length stack type;
栈的链式存储结构及运算 ◼ 用链表实现栈 a1 a2 …… an head 栈顶在 表头 （1）定义 typedef struct lstack_type{ node_type * top; int length; }lstack_type; 入栈 出栈 top
栈的链式存储结构及运犷 (2)压入push void push(stack, new_ node) new node->next= stack->top; stack→>top= new node; stack→| nath++ stack->top a ■■■ (3)弹出pop node type* pop(stack node type*out, new out= stack→>top; stack→top= stack→top>next; stack->length - return out
栈的链式存储结构及运算 （2）压入push void push(stack, new_node){ new_node->next = stack->top; stack->top = new_node; stack->length ++; } （3）弹出pop node_type * pop(stack){ node_type* out; out = stack->top; stack->top = stack->top->next; stack->length --; return out; } a1 new stack->top ……
4)的链式存储结抱及运基 stack top =s N, int empty(stack) if(stack top = NULL) return YES. else return No (5)置栈空 能否简单的使用 stacktop=NULL? 如果栈中还有链点,必须逐个将链点占用的空间释放 void clean(stack node type* temp; whil(! empty(stack)1、逐个将链点弹出 temp=pop( stack)2、释放链点空间 free(temp);]
栈的链式存储结构及运算 （4）栈空判断 stack.top == NULL; （5）置栈空 能否简单的使用 stack.top = NULL ? 如果栈中还有链点，必须逐个将链点占用的空间释放 void clean(stack){ node_type * temp; while( ! empty(stack)){ temp = pop(stack); free(temp); } } int empty(stack){ if(stack.top == NULL) return YES; else return NO; } 1、逐个将链点弹出 2、释放链点空间