1.栈 stack的定义 栈是特殊的线性表,仅在表的一端进行插入或删除操作 特点:(1)对栈内数据的操作总在栈顶进行 (2)数据进栈称为“压入”push (3)数据出栈称为“弹出”pop (4)遵循“后进先出”的原则LIFO 例题:输入顺序ABC,输出顺序有几种? ABC,ACB,BAC,BCA,CBA,不可能产生CAB 2.栈的顺序存储结构及运算 用数组实现栈, 为栈底,top为栈顶 (1)定义 typedef struct stack type elemtype data MAXNUM; Astack type (2)进栈push 当新元素进栈时,栈顶上移,新元素放在栈顶。 stack top=stack top+l: stack.datalstack top]= new one (3)出栈pop:从栈顶移出一个数据 栈顶元素拷贝出栈,栈顶下移 elemptype pop(stack type *stack) i elemtype out; f(stack->top <0)error(3); el out=stack->data[stack->top; stack->top= stack->top-1 return out (4)栈空判断 stack top==0(stack top<0) 栈满判断: stack top>= MAXNUM-17 1. 栈 stack 的定义 栈是特殊的线性表，仅在表的一端进行插入或删除操作 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则 LIFO 例题：输入顺序 A,B,C，输出顺序有几种？ ABC,ACB,BAC,BCA,CBA, 不可能产生 CAB 2.栈的顺序存储结构及运算 用数组实现栈, 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; （3）出栈 pop: 从栈顶移出一个数据。 栈顶元素拷贝出栈，栈顶下移 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; } （4）栈空判断 stack.top = = 0 (stack.top < 0) 栈满判断：stack.top >= MAXNUM - 1;