合工大数据结构 03-队列.ppt

合肥工业大学 计算机与信息学院 * 数 据 结 构 （第三章 队 列 ） Data Structures 张晶 计算机与信息学院 * * 第三章 队 列 第三章 队列（queue） 3.1 队列的定义和运算 3.2 顺序队列与循环队列 3.3 队列的应用 * 第三章 队 列 队列是软件设计中最基本的数据结构之一， 对队列结构的理解，同样需要参照前面所介绍的数据结构的组成部分。 逻辑结构 分析 运算实现（算法） 运算定义 存储结构 数据结构的组成 * 3.1 队列的定义和运算 3.1.1队列的定义 队列是只能在一端插入，另一端删除元素的线性表。 术语：队头, 队尾， 入队, 出队 逻辑结构和运算 a1 a2 … an 特性：先进先出 （FIFO：first in first out） … a1 a2 an an … a2 a1 … a1 a2 an 队头 队尾 出队 入队 * 3.1 队列的定义和运算 3.1.2队列的运算 1.队列的基本运算定义 对队列的基本运算有如下几个： (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？ 运算定义 * 3.1.2 队列的运算 2.队列的运算的C++描述 如何用C++描述队列的内容和运算？ 参照栈结构的做法，即 将队列的有关数据和运算封装在一起， 以C++的类的形式来封装描述。 封装的数据和运算要便于被有关程序来合理调用和引用。 因此，队列的C++描述的框架如下所示： class queue{ }; 类的名称 类的框架 运算描述部分 数据描述部分 * 3.1.2 队列的运算 队列的运算的C++描述的细节，与栈的运算的相对应： 初始化函数的描述 队列的C++类描述： class queue{ queue(); … 队列的数据成员 } ; 队列的运算 (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？ 采用C++的 构造函数 * 3.1.2 队列的运算 判断函数的对应 队列的C++类描述： class queue{ queue(); … 队列的数据成员 } ; 队列的运算 (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空