《软件技术基础06--栈和队列》由会员分享，可在线阅读，更多相关《软件技术基础06--栈和队列（26页珍藏版）》请在金锄头文库上搜索。
1、线性结构：栈和队列,廖丹 宽带光纤传输与通信系统技术教育部重点实验室 Key Laboratory of Broadband Optical Fiber Transmissionand Communication Networks,制作：段景山 廖丹 主讲：廖丹,栈结构,堆栈 stack,栈是特殊的线性表，仅在表的一端 进行插入或删除操作,an,.,a2,a1,栈顶,入栈,出栈,栈底,是抽屉一类物理实体的逻辑抽象 类似仓库、抽屉的结构,特点：（1）对栈内数据的操作总在栈顶进行（2）数据进栈称为“压入”push（3）数据出栈称为“弹出”pop（4）遵循“后进先出”的原则LIFO,用数组实现栈,a
2、max,.,a12,a0,.,atop,栈顶,a0为栈底，top为栈顶,（1）定义,typedef struct stack_typeelemtype dataMAXNUM;int top; /栈顶元素所在位置 stack_type;,（2）压入 push,当新元素入栈时，栈顶上移，新元素放在栈顶。,.,stack.top = stack.top + 1;,stack.datastack.top = new_one;,new_one,栈顶元素 所在位置,a1,a2,元素个数为top1,.,（3）弹出 pop,从栈顶移出一个数据。,amax,.,a1,a0,a1,a2,栈顶,栈顶元素拷贝出栈，栈
3、顶下移,out,out = stack.datastack.top; stack.top = stack.top - 1;,elemptype pop(stack_type *stack)elemtype out;if(stack-top datastack-top;stack-top = stack-top -1;return out; ,atop,（4）栈空判断,stack.top = = 0,stack.top = MAXNUM - 1;,a1,stack.top,栈顶元素所在位置,若a0为栈底，top为栈顶之上新空间位置 压入弹出栈空判断置栈空,amax,.,a1,a0,.,atop,
4、栈顶,new_one,a1,a2,stack.top = stack.top + 1;,stack.datastack.top = new_one;,atop,stack.top = stack.top 1;,out = stack.datastack.top;,stack.top = 0;,stack.top = 0;,元素个数为top,栈的应用,程序的嵌套，中断的嵌套,程序A,程序B,程序C,程序A,程序B,程序C,程序C,利用用户栈实现了程序调用后回到调用处,程序的嵌套与局部变量 程序的局部变量存放在用户栈,proc B( ) int x,y;,程序A a、b,程序B x、y,程序C o
5、、p,proc C( ) int o,p;,用链表实现栈,head,栈顶在,表头,（1）定义,typedef struct lstack_typenode_type * top;int length; lstack_type;,入栈,出栈,top,（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 = st
6、ack-top-next;stack-length -;return out; ,a1,new,stack-top,out,（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; ,队列,队
7、列 类似于排队机制的结构 队列是特殊的线性表， 节点的插入仅限于在表尾进行， 节点的删除仅限于在表头进行,入队,出队,队头,队尾,队列,特点： （1）对队列的操作在表的两端进行 （2）仅在队尾加入节点入队enqueue （3）仅在队首移出节点出队dequeue （4）遵循“先进先出”的原则FIFO,入队,出队,队头,队尾,用数组实现队列,（1）定义,a0,队首,队尾,a1,.,.,an,MAX,front,rear,typedef struct queue_typeelemtype dataMAXNUM;int front;int rear; queue_type;,（2）入队与出队,移元素？
8、,移队首、尾指针,入队,出队,入队,出队,入队,数组空间溢出而使操作出错，但此时 数组前面是有空间的,用循环数组实现队列,入队,rear = rear + 1,% 整除取余,设MAXNUM 5，rear4 则新元素加入队列后： rear （41） 50，新元素放在a0内,用循环数组实现队列,循环队列元素位置？,用循环数组实现队列,队空条件队满条件,rear,front = = rear,(rear + 1) % MAXNUM = = front,如果rear表示队尾节点的位置则有一个节点的队列的指针情况和队空时相同,front,rear,用循环数组实现队列,队空条件队满条件,rear,fron
9、t = = rear,(rear + 1) % MAXNUM = = front,定义：rear为指向队尾下一个可存放节点的位置,队列满时还有一个空位置,void enqueue(queue, new_one)queue-dataqueue-rear = new_one;queue-rear = (queue-rear +1) % MAXNUM;,入队算法,队列已满？,队列尾部放入新节点,队尾指示向后移动一格,if( (queue-rear + 1) % MAXNUM = = queue-front )error(1);else,出队算法,elemtype dequeue(queue)elem
10、type out；if( queue-rear = = queue-front )error(2);elseout queue-dataqueue-front;queue-front = (queue-front +1) % MAXNUM;return out； ,用循环数组实现队列,思考：在循环队列的第K个元素后插入一个新元素插队 如何确定aK的位置？ 如何搬移节点，以腾出空位放入新元素？,rear,用链表实现队列,front,rear,（一）定义,typedef struct lqueue_typenode_type * front;node_type * rear;int length; ,用链表实现队列,（二） 入队 新链点插入到队尾 注意：队列为空时，rear和front都要指向新元素（三） 出队 删除队首链点 注意：当队列被删空时，rear指针要置空,new_node-next = NULL; list-rear -next = new_node;,list-front = list-front-next;,temp = list-front;,front,rear,思考题,堆栈中取最大值操作 队列中取最大值操作,之前思考题讨论,单链表反向 链表成环检测,
