数据结构课件栈和队列

1、第三章栈和队列 Stack and Queue(2)作者声明：课件仅限本班教学参考用，不对外发布主讲：顾为兵第3章 栈和队列目录3.1 栈(Stack)3.2 栈的应用举例3.3 栈与递归的实现3.4 队列(Queue)3.4 队列(Queue) 3.4.1 队列的定义 3.4.2 队列的链式表示和实现-链队列 3.4.3 队列的顺序表示和实现-循环队列 3.4 队列3.3.1 队列的定义 队列是一种特殊的线性表; 插入位置只有1个，限制在表尾进行； 删除位置也只有1个，限制在表头进行。队列 队列的定义队头 front队尾rear插入入队删除出队a1a2a3a4 特点：先进先出FIFO(Fir

2、st In First Out) 入队序列队头端队尾端出队序列队列模型队列 队列的定义队列的基本运算:初始化空队列：InitQueue(&Q)清空队列：ClearQueue(&Q)判队空:QueueEmpty(Q)求队长：QueueLength(Q)读队头：GetHead(Q,&e) 入队操作：EnQueue(&Q,e)出队操作：DeQueue(&Q,&e)队列 队列的定义3.4 队列(Queue) 3.4.1 队列的定义 3.4.2 队列的链式表示和实现-链队列 3.4.3 队列的顺序表示和实现-循环队列 3.4 队列链队列: 带头结点、头指针和尾指针的单链表：typedef struct

3、QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front, rear; /队头指针和队尾指针 LinkQueue;datanext队元素frontrear队列队列 队列的链式表示和实现-链队列q1q2qn .Q.frontQ.rear队头元素队尾元素 Q.frontQ.rear队空条件：Q.front=Q.rearQ队列 队列的链式表示和实现-链队列q1 .队头元素队尾元素Q.frontQ.rearq2qn插入端删除端qness-next = NULLQ.rear-next

4、= sQ.rear = sQ.front-next=Q.front-next-next链队列操作的示意队列 队列的链式表示和实现-链队列q1q2qn .队头元素队尾元素rear 带尾指针的循环链队列也是一种不错的选择 队列 队列的链式表示和实现-链队列3.4 队列(Queue) 3.4.1 队列的定义 3.4.2 队列的链式表示和实现-链队列 3.4.3 队列的顺序表示和实现-循环队列 3.4 队列01234567a1a2a3a4rearfrontmaxsizea5#define maxsize 100 /队列数组的大小typedef struct QElemType *base; /队列数组

5、的基地址 int front; /队头指示器 int rear; /队尾指示器 SqQueue；队列 队列的顺序表示和实现-循环队列指在队尾元素的下一个位置指在队头元素位置01234567a5a7a6a8rearfrontmaxsize队空条件：front=rear 队列长度：rearfront入队操作：rear 出队操作：front队满条件：真上溢 rear=maxsize & rearfront=maxsize 假上溢 rear=maxsize & rear front maxsizea9还有空间，我要入队！顺序队列：01234567reara5a7a6a8fronta9假上溢问题的解决方

6、案一： 当rear达到上界时，队列整体左移, 将空闲空间移至右侧，继续接纳元素入队。缺点：需要移动元素。进来吧01234567reara5a7a6a8fronta9假上溢问题的解决方案二： 允许rearfront，即当rear达到上界而有入队请求时，rear回到下界位置。这就是循环队列的思想。a10队列 队列的顺序表示和实现-循环队列循环队列(Circular Queue)06543217frontrear入队、出队方向初态循环队列(Circular Queue)06543217front入队、出队方向a1a6a5a4a3a2reara1,a2,a3,a4,a5,a6入队循环队列(Circul

7、ar Queue)06543217入队、出队方向a6a5rearfronta1,a2,a3,a4出队循环队列(Circular Queue)06543217入队、出队方向a9a6a5rearfronta7a8a7,a8,a9入队入队： if(rearmaxsize-1) rear +; else rear=0; 这个if语句可等价地写成: rear=(rear+1) mod maxsize出队： if(frontmaxsize-1) front+; else front=0; 这个if语句可等价地写成: front=(front+1) mod maxsize队列 队列的顺序表示和实现-循环队列

8、判队空的条件：front = rear06543217a6a5front06543217初态：front=rear=0rearfronta5、a6出队后front=rear=6rear队列 队列的顺序表示和实现-循环队列06543217a8a7a6a5rearfronta9a10问题来了队满的条件也是 front = reara11和a12相继入队后，rear追上了front队列 队列的顺序表示和实现-循环队列解决队满与队空条件一样的方案： 06543217a8a7a6a5fronta9a10a11rear 牺牲一个结点的空间约定, maxsize的空间中最多只放maxsize1个结点队列已经

9、装满了rear所指的单元里不放任何元素06543217a8a7a6a5fronta9a10a11rear 在这种约定下，当rear在顺时针方向距front相差一个单元时，队列就满了。队满条件：front = (rear+1) mod maxsize队列长度： (rear front + maxsize) mod maxsize06543217rearfronta1a2a3front=2, rear=5length = (5 2 + 8) mod 8 = 306543217frontreara5a1a2a3a4front=5, rear=2length = (2 5 + 8) mod 8 = 5

10、队列 队列的顺序表示和实现-循环队列总结：队列Q0.maxsize-1初态：rear = front = 0入队：rear = (rear+1) mod maxsize出队：front = (front +1) mod maxsize队空条件：front = rear队满条件：front = (rear+1) mod maxsize队列长度：(rearfront+maxsize) mod maxsize队列 队列的顺序表示和实现-循环队列想一想： 对于Q1.maxsize的数组，入队、出队和求队列长度的公式该如何变化呢？队列 队列的顺序表示和实现-循环队列当队列数组的下界为1时，计算公式为：队

11、列Q1.maxsize初态：rear = front = 1入队：rear = rear mod maxsize + 1 出队：front = front mod maxsize + 1队空条件：front = rear队满条件：front = rear mod maxsize + 1队列长度：(rearfornt+maxsize) mod maxsize队列 队列的顺序表示和实现-循环队列循环队列的类型定义：#define MAXQSIZE 100;/队列数组的大小typedef struct QElemType*base;/队列数组首地址intfront;/队头指针，指向队头元素intre

12、ar;/队尾指针，指向/队尾元素的下一个位置 SqQueue；队列 队列的顺序表示和实现-循环队列基本运算在循环队列上的实现：初始化队列Status InitQueue(SqQueue &Q) /初始化一个空队列 Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType); if(!Qbase) return(OVERFLOW); Q.front=Q.rear=0; return OK/InitQueue队列 队列的顺序表示和实现-循环队列求队列长度：int QueueLength(SqQueue Q) len=(Q.rear-Q.front+MA

13、XQSIZE) % MAXQSIZE; return len;/QueueLength队列 队列的顺序表示和实现-循环队列入队操作：Status EnQueue(SqQueue &Q, int e)/入队操作,元素e成为新的队尾元素 if(Q.front=(Q.rear+1)%MAXQSIZE) return ERROR; /队列已满 Q.elemQ.rear=e; Q.rear=(Q.rear+1) % MAXQSIZE; /修改队尾指针/EnQueue队列 队列的顺序表示和实现-循环队列出入队操作：Status DeQueue(SqQueue &Q, int &e)/用e返回队头元素的值，队头元素出队， if(Q.front=Q.rear) re