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

F G H D E 0 1 2 3 4 5 f r ← G,H进队 方案二的空，满队列条件： A B C D E 0 1 2 3 4 5 r f 当 r+1==f 或 (f==0)(r==maxleng-1) 即：(r+1)% maxleng==f 为满队列 0 1 2 3 4 5 r f (2)空队列条件： A,B,C,D,E 依次出队后： 当(f==r)为空队列 (1)满队列条件： 若A,B,C,D,E 依次进队后： 4.顺序队列算法举例 定义队列的C类型 #define MAXLENG 100 Typedef struct { ElemType elem[MAXLENG]; int front,rear; } SeQueue; //定义结构变量Q表示队列 SeQueue Q; elem[0] elem[1] … … elem … … … … … … elem[MAXLENG-1] front rear 队列Q的存储结构示意图 (1)进队算法: 假设用Q表示顺序队列,头指针front指向队头元素，rear指向尾元素的后一个空位，e为进队元素。 int En_Queue( SeQueue Q,Elemtype e) { if ((Q.rear+1)% MAXLENG==Q.front) //若Q已满，退出 return ERROR； Q.elem[Q.rear]=e； //装入新元素e Q.rear++； //尾指针后移一个位置 Q.rear = Q.rear % MAXLENG； //为循环队列 return OK; } 0 1 2 MAXLENG-1 /// 0 1 2 MAXLENG-1 rear front rear front Q[0..MAXLENG-1]已满 Q[0.. MAXLENG-1]已满 (2)出队算法 int De_Queue(SeQueue Q,Elemtype e) { if (Q.front==Q.rear) //Q为空队列，退出 return ERROR； e=Q.elem[Q.front]； //取走队头元素,送e Q.front=(Q.front+1)% MAXLENG； //循环后移到一个位置 return OK; } x ... y 0 ... MAXLENG-1 rear front y ... z x 0 ... MAXLENG-1 front rear 思 考 题 1。 如何根据front,rear,maxlength求队列的长度。 (Q.rear-Q.front+maxlength)%maxlength struct node *pop(struct node *top,Elemtype *e) { struct node *p； if (top==NULL) return NULL; //空栈,返回NULL p=top； //p指向原栈的顶结点 (*e)=p-data； //取出原栈的顶元素送（*e） top=top-next； //删除原栈的顶结点 free(p)； //释放原栈顶结点的空间 return top； //返回新的栈顶指针top } 退栈算法 3.2 栈的应用举例 栈的基本用途----保存暂时不用的数或存储地址。 3.2.1 数制转换 例. 给定十进制数 N=1348,转换为八进制数 R=2504 1.依次求余数,并送入栈中，直到商为0。 (1) r1=1348%8=4 //求余数 n1=1348/8=168 //求商 (2) r2=168%8=0 //求余数 n2=168/8=21 //求商 (3) r3=21%8=5