数据结构第三章栈和队列.ppt

栈 ( Stack ) 队列 ( Queue ) 栈和队列的应用 顺 序 栈 §3.3 队列 ( Queue ) 队列的顺序存储表示 — 顺序队列 循环队列操作的实现 队列的链接表示 — 链式队列 链式队列主要操作的实现 front rear 入队列： X P ? ? a1 a2 an 生成新结点p 插入队尾 ? 出队列： P 删除结点p 释放结点p ？ front 用于出队列 rear 用于入队列 ? front rear P ? rear指向？ ? a1 a2 an front rear P front front ? ? P P front front ? 删除头结点，原第一个结点作为头结点 链式队列的定义 typedef struct node { elemtype data; //队列结点数据 struct node *next; //结点链指针 } QNode; typedef struct { QNode *rear, *front; } LiQueue; ? a1 a2 an front rear q linkqueue *q; * 操作原则 后进先出 (LIFO) §3.1 栈 ( Stack ) top bottom a1 an an-1 ? 进栈a 1 ? ? ? a n 出栈a n ? ? ? a 1 只允许在一端插入和删除的线性表 S= （a 1 a 2 a 3 ? ? ? ? ? ? a n-1 a n ） 允许插入和删除的一端称为栈顶 (top)， 另一端称为栈底(bottom) top bottom a1 an an-1 ? x ADT List { 数据对象: D={ai|1?i ? n, n ? 0, ai属Elemtype类型 数据关系: R1={ ai ,ai+1 | ai ,ai+1 ?D, i=1,2, …,n-1} 基本运算: InitStack( s); ClearStack(s); StackEmpty(s); StackLength(s): Push(s,e); Pop(s,e) GetTop(s,e); }ADT Stack 抽象数据类型栈的定义 typedef struct //顺序栈定义 { SElemEype elem[maxsize]; //栈数组 int top; //栈顶指针 } SqStack; top (栈空) 0 1 2 3 4 5 6 7 8 9 maxsize-1 elem c a b top 空栈 top a 进栈 a top a b c d e f 进栈溢出 top b 进栈 a b top a b c d e e 进栈 top a b d e e 退栈 c top 空栈 top a b d d 退栈 c c 退栈 top a b c b 退栈 a b top a a 退栈 top bool InitStack_sq (SqStack S) //置空栈 { S.top = -1; return(S); } bool stackempty_sq (SqStack S) { //判断栈是否空？空则返回T，否则返回F. if(S.top==-1) return false; return true; } bool Push_sq (SqStack S, SElemType e) //若栈满返回F, 否则新元素 e 进栈并返回T { if ( S.top==maxsize-1) return false; S.top++; S.elem[S.top] = e; //加入新元素 return true; } bool Pop_sq (SqStack S, SElemType e) //若栈空返回F, 否则栈顶元素读到e并返回T { if ( S.top==-1 ) return false; e = S.elem[S.top]; S.top--; return true; } 栈 1