5--栈队列串数组.pptx

软件技术基础线性结构——栈、队列栈结构2、堆栈 stack栈是特殊的线性表，仅在表的一端进行插入或删除操作是抽屉一类物理实体的逻辑抽象类似仓库、抽屉的结构出栈入栈an栈顶...a2栈底a1特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则LIFO用数组实现栈——顺序栈（一）2.1用数组实现栈（1）定义若定义a[0]为栈底，top为栈顶（2`）压入 push——将新元素放在栈顶当新元素入栈时，栈顶上移，新元素放在栈顶。a[MAX-1]new_one......typedef struct stack_type{ elemtype data[MAXNUM]; int top; //栈顶元素所在位置}stack_type;360栈顶...a2253栈顶元素所在位置a1150元素个数为top＋1stack.top = stack.top + 1;stack.data[stack.top] = new_one;顺序栈（一）（3`）弹出 pop——从栈顶移出一个数据栈顶元素拷贝出来栈顶下移拷贝出来的栈顶作为函数返回值a[MAX-1]out栈顶36046...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;}a2253a1150顺序栈（一）（4`）栈空判断（5`）置栈空（6`）栈满判断if( stack.top = = 0 ? )stack.topa1if( stack.top 0 )栈顶元素所在位置stack.top = -1;top的数理含义非常别扭if( stack.top = MAXNUM – 1 )顺序栈（常用定义）若定义top为栈顶之上新空间位置（2）压入（3）弹出（4）栈空判断条件（5）置栈空 （6）栈满判断条件a[max-1]元素个数为top...a[top]stack.data[stack.top] = new_one;a[top]new_onestack.top = stack.top + 1;栈顶...a2a[1]stack.top = stack.top － 1;a1a[0]out = stack.data[stack.top];有更好的逻辑解读stack.top == 0stack.top == MAX_NUMstack.top = 0;proc B( ){ ...... call C( ) ......}proc C( ){ ...... ...... ......}proc A( ){ ...... call B( ); ...... call C( );}顺序栈（6）栈的应用程序的调用，中断的嵌套A和B都会调用C，单从函数C的角度，当C执行完后，应该返回A还是B呢？proc B( ){ ...... call C( ) ......}proc C( ){ ...... ...... ......}proc A( ){ ...... call B( ); ...... call C( );}顺序栈（6）栈的应用程序的嵌套，中断的嵌套程序C程序C程序B程序A程序B程序C程序A利用用户栈实现了程序调用后回到调用处proc A( ){ int a,b; ...... call B( ); …… call C( );}用数组实现栈程序的嵌套与局部变量程序的指令位置和局部变量都存放在用户栈当C()被调用时c函数的局部变量会覆盖B的局部变量proc B( ){ int x,y; ...... ......}proc C( ){ int o,p; ...... ......}程序C o、p程序B x、y程序A a、bana1a2……用链表实现栈2.2用链表实现栈（1）定义入栈出栈headtop栈顶在表头typedef struct lstack_type{ node_type * top; int length;}lstack_type;链栈（2）压入push（3）弹出popvoid push(stack, new_node){ new_node-next = stack-top; stack-top = new_node; stack-length ++;}……a1stack-topnode_type * pop(stack){ node_type* out; out = stack-top; stack-top = stack-top-nex