ch3--队列.pptVIP

第3章 队列 3.1 队列的定义和运算 3.2 顺序队列和循环队列 队列也是线性表，是操作受限的特殊的线性表。线性表的插入、删除操作是不受限制的；队列的插入操作在表的一端进行，删除操作在表的另一端进行。 但从数据类型角度看，队列是和线性表不相同的两种重要的数据结构。在计算机科学和程序设计中有广范的应用。 3.1 队列 队列（Queue）也是一种基本的、重要的、应用广泛的数据结构。 队列是按“先进先出”操作方式组织的数据结构。 日常生活中队列操作方式实例： 人类在争用某些稀缺资源时，为体现公平，往往采取排队的解决办法，按“先来先服务”的原则使用这些资源。 春节排队购买火车票；食堂排队买饭等。 计算机中栈的应用实例： 早期Host+Terminal系统，终端争用CPU； 许多类型CPU的内部就构建了取指令队列，加快指令执行速度； 计算机中队列的应用实例： 计算机主机向外设传输数据，比如打印机打印文档，当外设速度较慢，来不及处理主机传来的数据时要使用队列对数据进行缓冲； 操作系统中的进程、线程调度等用到队列，Windows操作系统更是大量使用信息队列，利用消息驱动来调度和管理计算机系统，系统运行时构建众多的消息队列，将不同的消息放入不同的消息队列进行管理； 网络应用系统中队列也得到广泛的使用，比如C/S模式系统中，服务器为了处理众多客户端的并发访问，会用队列对客户端的服务请求进行管理； 此外，解决实际问题的应用系统中也会经常使用队列。 学习队列结构时，需要掌握哪些方面的内容？ 请看下图： 3.1.1 队列基本概念 队列（Queue） 是限定只能在一端插入元素，另一端删除元素的线性表，也称作先进先出表。 空队列 没有元素的队列。 队头（front） 删除元素的一端。 队尾（rear） 插入元素的一端。 入队 插入操作，即队尾插入。 出队 删除操作，即删除队头。 队列的特性 先进先出（FIFO—First In, First Out） 队列也是操作受限的线性表。 3.1.2 队列的基本运算 1. 队列的基本运算定义 (1) 初始化 ：设置队列为空。 (2) 判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3) 判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4) 取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5) 入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6) 出队：删除当前队头的元素。 如队列空而不能进行，应怎样处理？ 2. 杜列的运算的C++描述 任何数据结构的描述和实现都包括2个部分：数据（数据元素及其关系）和运算； C++如何描述队列结构呢？一种方案：将队列的数据和运算封装成C++的类。 成员变量—描述数据 成员函数—描述运算 队列的C++类描述框架： 【思考问题】 不用类其数据结构如何描述呢？ C++描述队列的运算需要考虑的问题与栈类似，下面逐个讨论栈的每个运算的情况 (1) 初始化 构造函数实现，Queue() 可能涉及到重载 (2)判断队空 bool empty() 若队列为空，返回True，否则，返回False。 (3)判断队满 bool full() 队列为满时，返回True，否则，返回False。 (4)取队头元素值 bool getFront(elementType x) 若队列不空，队头元素的值由变量x返回； 取队头成功返回True；若为空队列，取队头顶失败，返回False。 （注意书上返回值类型为errorCode，这里为了简单起见） elementType 为自定义的数据类型，可由typedef指定； 注意函数参数中使用了C++的‘引用’ (5)入队 bool enQueue( elementType x ) 将值为x的元素入队，即元素插入到队尾。 插入成功返回True；若插入前的队列已经满了，元素入队失败，返回False。 (6)出队 bool outQueue() 删除队头元素。 删除成功返回True；若删除前为空队列，删除失败，返回False。 队列类Queue的框架 3.2 顺序队列 3.2.1 顺序队列存储结构 用连续的存储空间（数组）data, 存储队列的元素。 将队列中的元素依次存储到数组中----顺序存储方式--顺序队列。 如下图所示： front 指向队头元素的前一个位置。此在初始化、循环队列中有用。rear 指向队尾元素。 或者， front指队头元素，让rear指向队尾元素的下一个单元。 顺序队列的C++描述--Queue类的完整描