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 <=0)error(3) else out= stack->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 <= 0) error(3); else{ out = stack->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 < 0 （5）置栈空 stack.top = -1; 栈满判断：stack.top >= MAXNUM - 1; stack.top a[0] 栈顶元素所在位置