软件技术基础06--栈和队列.ppt

思考题 堆栈中取最大值操作 队列中取最大值操作 之前思考题讨论 单链表反向 链表成环检测 * * * * * * * * * * * * * * * 线性结构：栈和队列 廖丹 liaodan@uestc.edu.cn 宽带光纤传输与通信系统技术教育部重点实验室 Key Laboratory of Broadband Optical Fiber Transmission and Communication Networks 制作：段景山 廖丹 主讲：廖丹 栈结构 堆栈 stack 栈是特殊的线性表，仅在表的一端 进行插入或删除操作 an ... a2 a1 栈顶 入栈 出栈 栈底 是抽屉一类物理实体的逻辑抽象 类似仓库、抽屉的结构 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则LIFO 用数组实现栈 a[max] ... a[12] 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 元素个数为top＋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）栈空判断 stack.top = = 0 stack.top 0 （5）置栈空 stack.top = -1; 栈满判断：stack.top = MAXNUM - 1; a[1] stack.top 栈顶元素所在位置 若a[0]为栈底，top为栈顶之上新空间位置 压入 弹出 栈空判断 置栈空 a[max] ... a[1] a[0] ... a[top] 栈顶 new_one a1 a2 stack.top = stack.top + 1; stack.data[stack.top] = new_one; a[top] stack.top = stack.top － 1; out = stack.data[stack.top]; stack.top == 0; stack.top = 0; 元素个数为top 栈的应用 程序的嵌套，中断的嵌套 proc A( ) { ...... call B( ); call C( ); } proc B( ) { ...... call C( ) ...... } proc C( ) { ...... ...... ...... } 程序A 程序B 程序C 程序A 程序B 程序C 程序C 利用用户栈实现了程序调用后回到调用处 程序的嵌套与局部变量 程序的局部变量存放在用户栈 proc A( ) { int a,b; ...... call B( ); call C( ); } proc B( ) { int x,y; ...... ...... } 程序A a、b 程序B x、y 程序C o、p proc C( ) { int o,p; ...... ...... } 用链表实现栈 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