合工大数据结构03-队列剖析

《合工大数据结构03-队列剖析》由会员分享，可在线阅读，更多相关《合工大数据结构03-队列剖析（26页珍藏版）》请在金锄头文库上搜索。

1、合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 1 数 据 结 构 （第三章 队 列 ） Data Structures 张晶 计算机与信息学院 * 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 2 第三章 队 列 第三章 队列（queue） 3.1 队列的定义和运算 3.2 顺序队列与循环队列 3.3 队列的应用 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 3 第三章 队 列 队列是软件设计中最基本的数据结构之一， 对队列结构的理解，同样需要参照前面所介绍的数据结构 的组成部分。 逻辑结构 分析 运算实现（算法） 运算定义 存储结构 数据结构的组成

2、合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 4 3.1 队列的定义和运算 3.1.1队列的定义 n队列是只能在一端插入，另一端删除元素的线性表。 术语：队头, 队尾， 入队, 出队 逻辑结构和运算 a1 a2 an 特性：先进先出 （FIFO：first in first out） a1a2 an an a2a1 a1a2 an 队头队尾 出队 入队 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 5 3.1 队列的定义和运算 3.1.2队列的运算 o 1.队列的基本运算定义 对队列的基本运算有如下几个： (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空

3、，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？ 运算定义 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 6 3.1.2 队列的运算 o 2.队列的运算的C+描述 如何用C+描述队列的内容和运算？ 参照栈结构的做法，即 n 将队列的有关数据和运算封装在一起， n 以C+的类的形式来封装描述。

4、n 封装的数据和运算要便于被有关程序来合理调用和 引用。 o 因此，队列的C+描述的框架如下所示： class queue ; 类的名称 类的框架 运算描述部分 数据描述部分 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 7 3.1.2 队列的运算 o队列的运算的C+描述的细节，与栈的运算的相对应： n初始化函数的描述 队列的C+类描述： class queue queue(); 队列的数据成员 ; 队列的运算 (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (

5、4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？ 采用C+的 构造函数 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 8 3.1.2 队列的运算 o 判断函数的对应 队列的C+类描述： class queue queue(); 队列的数据成员 ; 队列的运算 (1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE

6、，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？ 判断为空的函数 判断为满的函数const; const; Bool empty( ) Bool full( ) 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 9 3.1.2 队列的运算 o 其他几个函数的对应描述：与栈结构类似， n 几个运算的条件也可能有不成立的情况， 因此，需要给与明确的反映。 n 设立运算是否正常的类型e

7、rror_code， o 正常时返回success, o 否则返回错误类型，如overflow, underflow等。 n 将这几个函数的类型设置为error_code； n 如果需要返回其他的值，可以作为参数来返回。 o 由上述讨论可得到其他几个函数的功能描述： 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 10 3.1.2 队列的运算 （4)取队头元素的运算功能描述： 如果队列不空，则取出队头元素到参数x中，并返回success。 否则，返回underflow。 对应的运算函数为： error_code get_front(elementtype (5)入队的运算功能描述：

8、 如果队列不满，则将元素入队，并返回success。 否则，返回overflow。 对应的运算函数为： error_code append(const elementtype x); (6)出队的运算功能描述： 如果队列不空，删除当前队头的元素，并返回success。 否则，返回underflow。 对应的运算函数为： error_code serve(); 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 11 3.1.2 队列的运算 o由此得到队列的类queue的函数成员列表如下： class queue public: queue(); / 初始化 Bool empty( )

9、const; / 判断空 Bool full( ) const; / 判断满 error_code get_front(elementtype / 取队头元素 error_code append(const elementtype x); /入队 error_code serve(); / 出队 private： 队列的数据成员 ; 问题：上述类的描述是否还需要补充什么？ 对类的函数成员和数据成员的接口控制。 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 12 3.2 顺序队列与循环队列 3.2.1 存储结构： o与顺序栈的讨论类似： n假设有一个足够大的存储空间（数组）data

10、,用于存储队列的元 素。 n则将队列中的元素依次存储到数组中-顺序存储方式， n由此得到顺序队列。 n如下图所示： o其中，设置一个计数变量count ，以记录队列中的元素个数。 o将数组data和count作为类queue的数据成员。 队列的存储结构 a1a2 an 01 n-1maxlen-1 data ncount 顺序队列存储结构 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 13 3.2 顺序队列与循环队列 o 由此而得到类queue的完整描述。 o 封装类: class queue public: queue(); Bool empty()const; Bool fu

11、ll() const; error_code get_front(elementtype error_code append(const elementtype x); error_code serve(); private: int count; elementtype datamaxlen; ; 由函数成员 描述的运算 由数据成员描 述的存储结构 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 14 3.2 顺序队列与循环队列 3.2.2 关于存储结构的进一步讨论 因此，插入和删除操作的实现讨论如下： 插入：插入元素x就是要将x插入到表的末尾，因此，插入操作序列为： datac

12、ount = x; count +; 删除：删除就是删除表头元素，因而需将其后面所有元素往前移动一位。 问题：每次删除都需要移动所有元素， 若队列足够大，花费时间太大！ 如何解决这一问题？ n a1a2 an 01 n-1maxlen-1 data count 顺序队列结构 下面通过对运算实 现的讨论来探讨存储结 构的相关问题： 在这一结构下，约 定data0为队头元素， 另一端为队尾。 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 15 3.2 顺序队列与循环队列 改进的方法： 设置头尾指针front和rear作为queue的数据成员，分别指示队头和队尾。 并约定： front

13、指向队头的前一个元素，rear指向队尾元素。如图所示。 在这种情况下，插入操作和与前面类似，但写法有所不同： rear+; datarear = x; count +; 但删除操作要简单和省时间多了：front +; count-; 问题- “溢出”现象: 在连续插入元素后，会使rear指示到数组的末尾。 而此时的情况是，数组的前面可能还有空的元素空间。 01 n-1 a1a2 an maxlen-1 data n count 顺序队列结构 front rear - “假溢出” 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 16 3.2 顺序队列与循环队列 解决“假溢出”问题的方

14、法： 采用循环队列方式：将数组的头尾看作是相邻的元素， 即将元素data0看作是datamaxlen-1的下一个元素。如图所示。 因此，插入和删除以及状态检测需要作相应的调整： 插入操作中移动指示位置的计算： if ( rear+1 = maxlen ) rear = 0; else rear+; 或者：rear = ( rear + 1 ) % maxlen ; 或者：rear = ( rear + 1 = maxlen ) ? 0 : rear + ; 删除操作：front = ( front + 1 ) % maxlen ; 队列空条件： front = rear 队列满条件： fron

15、t = rear 冲突：判断队列满和空的条件相同！ 2 maxlen-1 1 0 an a1 a3 a2 ai front rear 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 17 3.2 顺序队列与循环队列 解决的方法：（假设不用count） （1）增加标志： 设置一个记录最后的操作是插入还是删除的标志。 当出现首尾指针值相同时， 如果标志是插入，则可断定当前队列是- 如果标志是删除，则可断定当前队列是- （2）约定保留一个元素空间： 即将数组约定为最多存放maxlen-1个元素， 因此，使得尾指针rear“赶不上”头指针front， 因而不会出现上述的在满的情况下，头尾指针相等的情况。 从而便于判断的实现。 下面采用第二种方法讨论各运算的实现。 2 maxlen-1 1 0 an a1 a3 a2 ai front rear 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 18 3.2 顺序队列与循环队列 o运算实现（循环队列）： queue:queue( ) count = 0; front = rear = 0; Bool queue:empty( )const if ( count = 0 ) return TRUE