第3章-堆栈和队列

1、1本章主要内容本章主要内容: :n堆栈n堆栈的应用n队列n队列的应用23.1 栈 ( Stack ) 只允许在一端插入和删除的线性表只允许在一端插入和删除的线性表 允许插入和删除允许插入和删除的一端称为的一端称为栈顶栈顶 (top)，另一端称，另一端称 为为栈底栈底(bottom 特点特点后进先出后进先出LIFO退栈退栈进栈进栈3 栈的存储结构栈的存储结构 顺序栈顺序栈实现：一维数组实现：一维数组sMtop=0123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组长度为设数组长

2、度为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空4栈的基本操作1、初始化、初始化 Initiate(s)2、进栈、进栈 push(s,x)3、退栈、退栈 pop (s)4、取栈顶元素、取栈顶元素 gettop(s)5、判栈是否非空、判栈是否非空 Notempty(s)6、置空栈置空栈 SETNULL(s)5栈的顺序存储结构顺序栈的定义顺序栈的定义typedef int elemtype;

3、#define maxsize 64typedef struct elemtype datamaxsize; int top;seqstack; 6栈的基本运算栈的基本运算初始化初始化initiate(seqstack *s) s-top0; 判栈空判栈空int notEMPTY(seqstack *s) if (s-top0) return 1; else return 0;7进栈进栈seqstack *PUSH(seqstack *s,datatype x) if (s-top=maxsize) printf(“overflown”);return NULL; else s-datas-t

4、opx; s-top+; return s;8退栈退栈datatype POP(seqstack *s) if (s-toptop-; return(s-datas-top); 9取栈顶取栈顶datatype TOP(seqstack *s) if (s-topdatas-top-1);10栈的链接表示 链式栈 链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行 链式栈的栈顶在链头链式栈的栈顶在链头 适合于多栈操作适合于多栈操作11栈的链接存储结构链栈的结点定义链栈的结点定义typedef int elemtype;struct slno

5、detype elemtype data; struct slnodetype * next; ; 12链栈的进栈算法链栈的进栈算法slnodetype *PUSHLSTACK(slnodetype *top, elemtype x) slnodetype *p; pmalloc(sizeof(slnodetype); p-datax; p-nexttop; return p; .栈底hhxp13链栈的出栈算法链栈的出栈算法slnodetype *POPLSTACK(slnodetype *top, datatype *datap) slnodetype *p; if (top-next=NU

6、LL) printf(“under flown”); return NULL; else ptop; *datapp-data; top=top-next; free(p); return top; top .栈底top14例例 递归的执行情况分析递归的执行情况分析 递归过程及其实现递归过程及其实现递归：函数直接或间接的调用自身递归：函数直接或间接的调用自身实现：建立递归工作栈实现：建立递归工作栈void print(int w) int i; if ( w!=0) print(w-1); for(i=1;ifrontmaxsize-1; sq-rearmaxsize-1;22顺序队列判队空顺

7、序队列判队空int EMPTY(sequeue *sq) if (sq-rear=sq-front) return(TRUE); else return(FALSE); 23顺序队列取队头元素顺序队列取队头元素datatype FRONT(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”);return NULL; else return (sq-front+1)%maxsize;24顺序队列入队顺序队列入队int ENQUEUE(sequeue *sq,datatype x) if (sq-front=(sq-rear+1)%maxsiz

8、e) printf(“sequeue is fulln”;return NULL); else sq-rear(sq-rear+1)%maxsize; sq-datasq-rearx; return(TRUE); 25顺序队列出队顺序队列出队datetype DEQUEUE(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”);return NULL; else sq-front(sq-front+1)%maxsize; return(sq-datasq-front); 26 顺序队列存在问题顺序队列存在问题设数组维数为设数组维数为M，则：，

9、则：当当front=-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出真真溢出溢出当当front -1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出假假溢出溢出 解决方案解决方案1.队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪费时间浪费时间2.循环队列循环队列基本思想：把队列设想成环形，让基本思想：把队列设想成环形，让sq0接在接在sqM-1之后，若之后，若rear+1=M,则令则令rear=0;0M-11frontrear.实现：利用实现：利用“模模”运算运算入队：入队： rear=(rear+1)%M; sqrear=x;出

10、队：出队： front=(front+1)%M; x=sqfront;队满、队空判定条件队满、队空判定条件27 存储队列的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。 队头、队尾指针队头、队尾指针加加1时从时从maxSize - -1直接进到直接进到0，可用语言的取模，可用语言的取模(余数余数)运算实现。运算实现。 队头指针进队头指针进1: front = (front + 1) % maxSize; 队尾指针进队尾指针进1: rear = (rear + 1) % maxSize; 队列初始化：队列初始化：front = rear = 0;循环队列 (Circular

11、Queue)28012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态初始状态J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front29循环队列的进队和出队30队列的链接表示 链式队列 队头在链头，队尾在链尾。队头在链头，队尾在链尾。 链式队列在进队时无队满问

12、题，链式队列在进队时无队满问题，但有队空问题。但有队空问题。31链队列结点类型定义链队列结点类型定义typedef struct linklist *front,*rear; linkqueue;32链队列置队空链队列置队空SETNULL(linkqueue *q) q-frontmalloc(sizeof(linklist); q-front-nextNULL; q-rearq-front; 33链队列判队空链队列判队空int EMPTY(linkqueue *q) if q-front=q-rear) return(TRUE); else return(FALSE); 34链队列取队头结点

13、链队列取队头结点datatype FRONT(linkqueue *q) if (EMPTY(q) printf(“queue is emptyn”);return NULL; else return(q-front-next-data); 35链队列入队链队列入队ENQUEUE(linkqueue *q,datatype x) q-rear-nextmalloc(sizeof(linklist); q-rearq-rear-next; q-rear-datax; q-rear-nextNULL; 36链队列出队链队列出队datatype DEQUEUE(linkqueue *q) linkl

14、ist *s; if (EMPTY(q) printf(“queue is emptyn”);return NULL; else sq-front; q-frontq-front-next; free(s); return(q-front-data); 370111011110101010010011110111001110011000011001101 2 3 4 5 6 7 8123456队列的应用举例求迷宫的最短路径队列的应用举例求迷宫的最短路径38xy00+11+1+12+103+1-140-15-1-16-107-1+1需要解决的问题1：如何从某一坐标点出发搜索其四周的邻点39需要解

15、决的问题2：如何存储搜索路径需要解决的问题3：如何防止重复到达某坐标点步xypre111022213332431340需要解决的问题4：如何输出搜索路径1121314151617181920 x1525656656y1663175488pre0891010111214161641#define r 64#define m2 10#define n2 10int mm2-2,nn2-2; typedef struct int x,y; int pre; sqtype;sqtype sqr;struct moved int x,y; move8; int mazem2n2;42int SHORTP

16、ATH(int maze) int i,j,v,front,rear,x,y; sq1.x1; sq1.y1; sq1.pre0; front1; rear1; maze11-1; while(front=rear) xsqfront.x; ysqfront.y; for (v=0;v8;v+) ix+movev.x; jy+movev.y; if (mazeij=0) rear+; ; sqrear.xi; sqrear.yj; sqrear.prefront; mazeij-1; if (i=m)&(j=n) PRINTPATH(sq,rear); RESTORE(maze); return(1); front+; return(0); 43PRINTPATH(sqtype sq,int re