数据结构课件_第六讲(队列)

数据结构 大话《数据结构》 大话《数据结构》

崔基哲 2012年算法和数据结构 1

第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章

绪论 算法 线性表 栈和队列 串 树 图 查找 排序

2 算法和数据结构

第四章：栈和队列

栈栈是限定于只在表尾进行插入和删除操 作的线性表 后进先出(Last in first out,LIFO) Last out,LIFO 相关概念– 栈顶(表尾) – 栈底(表头)举例：IE浏览器中的“前，后”3 算法和数据结构

队列： 队列：常常是件很令人恼火的事情……尤其是在我们这样的人口大国电话亭-1978年在北京15%的电话要在1小时后才能 接通。在电报大楼打电话的人还要带着午饭去排队

银行窗口，ATM 医院、理发、火车售票… 游乐场的游乐项目

在游乐园中的频频排队 会极为扫兴……

5 算法和数据结构

6 算法和数据结构

7 算法和数据结构

怎样缩短排队的等待时间？银行的排队叫号机 只是有序的组织了顾客，并没有减 少等待时间 如果能实现知道轮到自己需要等待 多少时间，再选择合适的时间来， 岂不很好？ 排队(队列 到底有什么学问？ 排队 队列)到底有什么学问？ 队列 到底有什么学问8 算法和数据结构

第三章：栈和队列

队列队列的特点– 先进先出，First in first out(FIFO)

相关概念– 队头：删除 – 队尾：插入出队 A1 A2 A3 A4 A5… … An 队头(front)算法和数据结构

入队 队尾(rear)9

第三章：栈和队列

队列的操作初始化：InitQueue 判断是否为空：IsEmpty 入队列：EnQueue 出队列：DlQueue 取队列头：GetHead 清空队列：Clear 得到队列长度：GetSize10 算法和数据结构

队列顺序存储的不足– 排队打饭，头名打完后面所有元素都要往 前移动，O(n)…

不必要的浪费？ – 引入两个指针：

假溢出11 算法和数据结构

10 9 8 7 6 5 4 3 2 1 0

tail Q(8) (7) (6) (5) (4) (3)

head

10 9 8 7 6 5 4 3 2 1 0

tail Q(8) (7) (6) (5) (4)

head

12 算法和数据结构

循环队列假溢出

当队头与队尾元素重合时候，队满溢出算法和数据结构

14 算法和数据结构

循环队列演示

Q.fron Q.rea t r

J1 J2 J3