第3章堆栈与队列

1、第三章堆栈与队列n队列的应用队列的应用3.1 堆栈堆栈一、堆栈的基本概念一、堆栈的基本概念n定义定义栈：用于局部变量、函数的形参等的空间栈：用于局部变量、函数的形参等的空间分配。分配。堆：由程序员申请，并对之进行释放。堆：由程序员申请，并对之进行释放。例如：例如：mallocmalloc（）；（）；freefree（）；（）；3.1 堆栈堆栈一、堆栈的基本概念一、堆栈的基本概念n定义定义 栈是限定只能在表的一端进行插入和删栈是限定只能在表的一端进行插入和删除的线性表。在表中允许插入和删除的除的线性表。在表中允许插入和删除的一端叫做一端叫做栈顶栈顶(top)(top)；表的另一端则叫做；表的另一

2、端则叫做栈底栈底(bottom)(bottom)。 栈又称后进先出栈又称后进先出(Last In First Out,(Last In First Out,简写简写为为LIFO)LIFO)表表出栈或出栈或退栈退栈入栈或入栈或进栈进栈a0a1an-2an-1bottomtop相关术语相关术语栈满：栈满：栈内元素个数为栈内元素个数为MaxSize时。时。 top=MaxSize-1栈空：栈空：栈内无元素。栈内无元素。 top=-1上溢：上溢：当栈满时，还要进栈。当栈满时，还要进栈。下溢：下溢：当栈空时，还要出栈。当栈空时，还要出栈。例：例： 对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，

3、如果输入项序列，如果输入项序列由由ABC组成，试给出所有可能的输出序列。组成，试给出所有可能的输出序列。1. A进进 A出出 B进进 B出出 C进进 C出出 ABC2. A进进 A出出 B进进 C进进 C出出 B出出 ACB3. A进进 B进进 B出出 A出出 C进进 C出出 BAC4. A进进 B进进 B出出 C进进 C出出 A出出 BCA5. A进进 B进进 C进进 C出出 B出出 A出出 CBA不可能产生输出序列不可能产生输出序列 CAB1、初始化、初始化2、进栈、进栈3、退栈、退栈4、取栈顶元素、取栈顶元素5、判栈是否非空、判栈是否非空二、堆栈的操作二、堆栈的操作三、栈的顺序表示和实现

4、三、栈的顺序表示和实现顺序堆栈顺序堆栈1. 顺序栈的存储结构顺序栈的存储结构出栈或出栈或退栈退栈入栈或入栈或进栈进栈bottomtopa0a1a3a4a5maxlen-1543210顺序栈的定义顺序栈的定义typedef int DataType;#define maxlen 64typedef struct DataType stackmaxlen; int top;seqstack;topstackmaxlenss-tops-stack0s-stack1s-stack2s-stackmaxlen-12. 顺序堆栈的操作实现顺序堆栈的操作实现toptopa1a2a3a4toptoptopma

5、xlen个a1进栈a2进栈a3进栈a4进栈a4出栈topn初始化voidinistack(seqstack*s)s-top=-1;n判栈空操作int empty(seqstack s) if(s.top=-1) return 1; else return 0;n入栈入栈int push(seqstack int push(seqstack * *s,DataType x)s,DataType x) if (s-top=maxlen-1)if (s-top=maxlen-1) printf(“nStack is full”);printf(“nStack is full”);return 0;r

6、eturn 0; s-top+;s-top+;s-stacks-top=x;s-stacks-top=x;return 1;return 1; 判栈满？判栈满？栈顶下栈顶下标加标加1 1入栈入栈n出栈出栈int pop(seqstack int pop(seqstack * *s,DataType s,DataType * *d)d) if(s-top=-1) if(s-top=-1) printf(n Stack is empty!); printf(n Stack is empty!); return 0; return 0; else else * *d= s-stacks-top; d

7、= s-stacks-top; (s-top)- -; (s-top)- -; return 0; return 0; 判栈空？判栈空？元素出元素出栈栈栈顶下标减栈顶下标减1n取栈顶元素取栈顶元素int gettop(seqstack *s,DataType *d) if(s-top=-1) printf(“nStack is empty!”); return 0; else *d=s-stacks-top; return 1; 堆栈算法练习堆栈算法练习顺序栈的顺序栈的C C语言描述：语言描述：typedef int elemtype;#define maxsize 10elemtype st

8、ackmaxsize; int top;写出堆栈的入栈和出栈算法写出堆栈的入栈和出栈算法两个堆栈共享空间目的：两个堆栈共享空间目的：节省空间节省空间堆栈共用问题堆栈共用问题两个堆栈共享空间的运算：初始化两个堆栈共享空间的运算：初始化 进栈进栈 出栈出栈a0aiajam0maxsize-1LeftTopRightTop 数据结构定义：数据结构定义：typedef struct DataType stackmaxlen; int LeftTop; int RightTop; dqstack;初始化算法初始化算法void InitiDqstack(dqstack*s); s-LeftTop=-1;

9、s-RightTop=maxlen; int PushDqstack(dqstack*s,char WhichStack,DataType x) if (s-LeftTop= s-RightTop-1) printf(“栈满栈满”); return 0; if (WhichStack!=L& WhichStack !=R) printf(“出错出错”); return 0; if (WhichStack=L) s-stack+s-LeftTop=x; else s-stack-s-RightTop=x; return 1; 进栈算法进栈算法判断是否栈判断是否栈满满判断输判断输入是否入是

10、否错错X X入左栈入左栈X X入右栈入右栈共用堆栈的出共用堆栈的出栈算法栈算法:自编。自编。共用堆栈的算法练习共用堆栈的算法练习:已知：已知：一个双向堆栈一个双向堆栈stackMstackM(M(M自己定义自己定义) )，编写一个从键盘输入数据，若输入的是奇数，编写一个从键盘输入数据，若输入的是奇数，则存入左栈；若输入的是偶数，则存入右栈，则存入左栈；若输入的是偶数，则存入右栈，直到栈满为止的算法。直到栈满为止的算法。 12EFhead130A12EFa31475130Aa210CB1475a110CB三、栈的链式存储结构三、栈的链式存储结构栈顶栈顶链栈的结点定义链栈的结点定义typedef

11、int DataType;typedef struct snode DataType data; struct snode *next; LSNode; int PushStack(LSNode *head, DataType x) LSNode *p; if (p (LSNode*) malloc(sizeof(LSNode)=NULL) printf(“n失败失败”)； return 0； p-datax; p-nexthead-next; head-next=p; return 1; 链栈的进栈算法链栈的进栈算法产生一个产生一个新结点新结点进栈进栈headpxint PopStack(L

12、SNode *head,DataType *d) LSNode *p; p=head-next; if (p=NULL) printf(“under flown”); return 0; *dp-data; head-next p-next; free(p); return 1; 链栈的出栈算法链栈的出栈算法判栈空判栈空出栈headp*d总结：总结：概念：概念：堆栈，栈顶，栈底，栈满，栈空，上溢，堆栈，栈顶，栈底，栈满，栈空，上溢， 下溢，下溢， 顺序栈，链栈。顺序栈，链栈。算法：算法：初始化，入栈，出栈，取栈顶元素。初始化，入栈，出栈，取栈顶元素。 （顺序栈，链栈）（顺序栈，链栈） 3.3

13、3.3 队列队列一、队列的定义及其操作一、队列的定义及其操作n定义定义 队列是一种特殊的线性表。在队列中，仅队列是一种特殊的线性表。在队列中，仅允许一端进行插入，在另一端进行删除。允许一端进行插入，在另一端进行删除。 允许插入的一端叫做队尾允许插入的一端叫做队尾(rear)(rear)；允许删除；允许删除的另一端叫做队头的另一端叫做队头(front)(front)。 队列又称先进先出队列又称先进先出(First in First Out,(First in First Out,简写简写为为FIFO)FIFO)表。表。队列的基本操作队列的基本操作1、置空队列、置空队列2、判定队列是否为空、判定队

14、列是否为空3、取队列头元素、取队列头元素4、将新元素插入队尾、将新元素插入队尾5、队列头元素出队、队列头元素出队 二、队列的顺序存储结构二、队列的顺序存储结构frontfrontqueuemaxlenqueuemaxlenrearrearsqsqsq-rearsq-rearsq-frontsq-frontsq-queue0sq-queue0sq-queue1sq-queue1sq-queue2sq-queue2sq-queuemaxlen-1sq-queuemaxlen-1借助借助C语言的算法描述使用的数据类型示意图语言的算法描述使用的数据类型示意图顺序队列的定义顺序队列的定义#define

15、maxlen 100typedef int DataType;typedef struct DataType queuemaxlen; int front,rear; sequeue;指示队头元素的前一个位置指示队头元素的前一个位置指示队尾元素的实际位置指示队尾元素的实际位置frontrear空队空队a a入队入队b b入队入队 顺序队列入队过程顺序队列入队过程cdcd入队入队4 3 2 1 04 3 2 1 0a4 3 2 1 0ba4 3 2 1 0rearfrontfrontrearfrontrearabdc注意：入队时，注意：入队时，frontfront不变，不变，rearrear变变

16、gfedcbafrontrear队满队满gfedcbfrontreara a出队出队gfedfrontrearbcbc出队出队frontreardefgdefg出队出队 队列出队过程队列出队过程注意：出队时，注意：出队时，frontfront变，变，rearrear不变不变队空队空n 进队时队尾指针先进一进队时队尾指针先进一 rear = rear + 1， 再将新元素按再将新元素按 rear 指示位置加入。指示位置加入。n 出队时队头指针先进一出队时队头指针先进一 front = front + 1， 再将下标为再将下标为 front 的元素取出。的元素取出。n 队满时队满时( (rear

17、=maxsize-1 ) )再进队将溢出出错；再进队将溢出出错；n 队空时队空时( (rear = front ) )再出队将溢出出错。再出队将溢出出错。n front总是指向队列中第一个元素的前一个位置。总是指向队列中第一个元素的前一个位置。n rear总是指向队列中最后元素总是指向队列中最后元素的位置。的位置。顺序队列的假溢出顺序队列的假溢出rearrearrearreara0a1a2a3rearrearrearrearrearrearmaxlenmaxlen个个frontfrontfrontfrontrearreara4rearreara5frontfronta6rearrear假溢出假

18、溢出1. 基本原理：基本原理： a.当当rear和和front达到达到maxlen-1后，在前后，在前进一个位置就自动到进一个位置就自动到0。 b.如何实现：如何实现： 用求模运算，用求模运算，rear=(rear+1)%maxlen循环队列循环队列frontJ6J7J8J1J2J3J4J5rearrearfront队列满队列满队列空队列空2. 队空和队满的判断：队空和队满的判断：循环队列循环队列n循环队列的初始化循环队列的初始化void iniqueue(sequeue void iniqueue(sequeue * *sq)sq) sq-front=0; sq-front=0; sq-re

19、ar=0; sq-rear=0; n入队入队int addqueue(sequeue int addqueue(sequeue * *sq,DataType x)sq,DataType x) if (sq-front=(sq-rear+1)%maxlen)if (sq-front=(sq-rear+1)%maxlen) printf(“nQueue is full”);printf(“nQueue is full”);return 0;return 0; sq-rear=(sq-rear+1)%maxlen;sq-rear=(sq-rear+1)%maxlen;sq-queuesq-rear=

20、x;sq-queuesq-rear=x;return 1;return 1; n出队出队int delqueue(sequeue int delqueue(sequeue * *sq, DataType sq, DataType * *d)d) if(sq-front=sq-rear)if(sq-front=sq-rear) printf(n Queue is empty!);printf(n Queue is empty!);return 0;return 0; sq-front=(sq-front+1)%maxlen;sq-front=(sq-front+1)%maxlen;* *d=sq

21、-queuesq-front;d=sq-queuesq-front;return 1;return 1; 三、队列的链式存储结构三、队列的链式存储结构 队列的链式存储结构队列的链式存储结构12EFfront130A12EFa11475130Aa210CB1475a310CB10CBrear链队列的结构体定义链队列的结构体定义typedef struct slnode DataType data; struct slnode *next; LQNode; typedef struct LQNode *front; LQNode *rear; LQueue;初始化初始化int InitiateSLQueue(LQueue *q) if(q-front=(LQNode*)malloc(sizeof(LQNode)=NULL) printf(“n申请空间失败！申请空间失败！”); return 0; q-rear=q-front; q-front-next=NULL; ret