合工大数据结构03-队列

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

2、队列是只能队列是只能在一端插入在一端插入，另一端删除另一端删除元素的线性表。元素的线性表。 术语术语：队头队头, 队尾，队尾， 入队入队, 出队出队 逻辑结构和运算逻辑结构和运算a1 a2 an 特性：先进先出特性：先进先出（FIFO：first in first out）a1a2anana2a1a1a2an队头队头队尾队尾出队出队入队入队53.1 队列的定义和运算3.1.23.1.2队列的运算队列的运算o 1.1.队列的基本运算定义队列的基本运算定义对队列的基本运算有如下几个：对队列的基本运算有如下几个：(1)(1)初始化初始化 ：设置队列为空。：设置队列为空。 (2)(2)判断队列为空：判

3、断队列为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断队列为满：判断队列为满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取队头元素：取出队头元素。取队头元素：取出队头元素。 条件：队列不空。条件：队列不空。 否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入队：将元素入队，即放到队列的尾部。入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？如果队列满，怎样处理？ (6)(6)出栈：删除当前队头的元素。出栈：删除

4、当前队头的元素。 如因为队列空而不能进行，如因为队列空而不能进行，应怎样处理？应怎样处理？ 运算定义运算定义63.1.2 队列的运算o 2.队列的运算的队列的运算的C+描述描述如何用如何用C+描述队列的内容和运算？描述队列的内容和运算？参照栈结构的做法，即参照栈结构的做法，即n 将队列的有关将队列的有关数据数据和和运算运算封装在一起，封装在一起，n 以以C+的的类类的形式来封装描述。的形式来封装描述。n 封装的封装的数据数据和和运算运算要便于被有关程序来要便于被有关程序来合理调用合理调用和和引用引用。o 因此，队列的因此，队列的C+描述的框架如下所示：描述的框架如下所示：class queue

5、 ;类的名称类的名称类的框架类的框架运算描述部分运算描述部分数据描述部分数据描述部分73.1.2 队列的运算o队列的运算的队列的运算的C+描述的细节，与栈的运算的相对应：描述的细节，与栈的运算的相对应：n初始化函数的描述初始化函数的描述队列的队列的C+类描述：类描述： class queue queue(); 队列的数据成员队列的数据成员 ;队列的运算队列的运算(1)(1)初始化初始化 ：设置队列为空。：设置队列为空。 (2)(2)判断队列为空：判断队列为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断队列为满：判断队列为满：

6、若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取队头元素：取出队头元素。取队头元素：取出队头元素。 条件：队列不空。条件：队列不空。 否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入队：将元素入队，即放到队列的尾部。入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？如果队列满，怎样处理？ (6)(6)出栈：删除当前队头的元素。出栈：删除当前队头的元素。 如因为队列空而不能进行，如因为队列空而不能进行，应怎样处理？应怎样处理？采用采用C+的的构造函数构造函数83.1.2 队列的运算o

7、 判断函数的对应判断函数的对应队列的队列的C+类描述：类描述： class queue queue(); 队列的数据成员队列的数据成员 ; 队列的运算队列的运算(1)(1)初始化初始化 ：设置队列为空。：设置队列为空。 (2)(2)判断队列为空：判断队列为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断队列为满：判断队列为满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取队头元素：取出队头元素。取队头元素：取出队头元素。 条件：队列不空。条件：队列不空。 否则，应能明

8、确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入队：将元素入队，即放到队列的尾部。入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？如果队列满，怎样处理？ (6)(6)出栈：删除当前队头的元素。出栈：删除当前队头的元素。 如因为队列空而不能进行，应怎样处理？如因为队列空而不能进行，应怎样处理？判断为空的函数判断为空的函数判断为满的函数判断为满的函数const;const;Bool empty( )Bool full( )93.1.2 队列的运算o 其他几个函数的对应描述：与栈结构类似，其他几个函数的对应描述：与栈结构类似，n 几个运算的条件也可能有不

9、成立的情况，几个运算的条件也可能有不成立的情况， 因此，需要给与明确的反映。因此，需要给与明确的反映。n 设立运算是否正常的类型设立运算是否正常的类型error_code，o 正常时返回正常时返回success,o 否则返回错误类型，如否则返回错误类型，如overflow, underflow等。等。n 将这几个函数的类型设置为将这几个函数的类型设置为error_code；n 如果需要返回其他的值，可以作为参数来返回。如果需要返回其他的值，可以作为参数来返回。o 由上述讨论可得到其他几个函数的功能描述：由上述讨论可得到其他几个函数的功能描述：103.1.2 队列的运算（4)4)取队头元素取队头

10、元素的运算功能描述：的运算功能描述： 如果队列不空，则取出队头元素到参数如果队列不空，则取出队头元素到参数x x中，并返回中，并返回successsuccess。 否则，返回否则，返回underflowunderflow。 对应的运算函数为：对应的运算函数为： error_code get_front(elementtype &x) const;(5)(5)入队入队的运算功能描述：的运算功能描述： 如果队列不满，则将元素入队，并返回如果队列不满，则将元素入队，并返回successsuccess。 否则，返回否则，返回overflowoverflow。 对应的运算函数为：对应的运算函数为

11、： error_code append(const elementtype x);(6)(6)出队出队的运算功能描述：的运算功能描述： 如果队列不空，删除当前队头的元素，并返回如果队列不空，删除当前队头的元素，并返回successsuccess。 否则，返回否则，返回underflowunderflow。 对应的运算函数为：对应的运算函数为： error_code serve();113.1.2 队列的运算o由此得到队列的类由此得到队列的类queue的函数成员列表如下：的函数成员列表如下：class queue public: queue(); / 初始化初始化 Bool empty( ) c

12、onst; / 判断空判断空 Bool full( ) const; / 判断满判断满 error_code get_front(elementtype &x) const; / 取队头元素取队头元素 error_code append(const elementtype x); /入队入队 error_code serve(); / 出队出队 private： 队列的数据成员队列的数据成员;问题：上述类的描述是否还需要补充什么？问题：上述类的描述是否还需要补充什么？ 对类的函数成员和数据成员的接口控制。对类的函数成员和数据成员的接口控制。123.2 顺序队列与循环队列3.2.1 存储

13、结构：存储结构：o与顺序栈的讨论类似：与顺序栈的讨论类似：n假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）data,用于存储队列的元用于存储队列的元素。素。n则将队列中的元素依次存储到数组中则将队列中的元素依次存储到数组中-顺序存储方式，顺序存储方式，n由此得到顺序队列由此得到顺序队列。n如下图所示：如下图所示：o其中，设置一个计数变量其中，设置一个计数变量count ，以记录队列中的元素个数。，以记录队列中的元素个数。o将数组将数组data和和count作为类作为类queue的数据成员。的数据成员。队列的存储结构队列的存储结构a1a2an01n-1maxlen-1dat

14、ancount顺序队列存储结构133.2 顺序队列与循环队列o 由此而得到类由此而得到类queue的完整描述。的完整描述。o 封装类封装类: class queue public: queue(); Bool empty()const; Bool full() const; error_code get_front(elementtype &x)const; error_code append(const elementtype x); error_code serve(); private: int count; elementtype datamaxlen;由函数成员由函数成员描述

15、的运算描述的运算由数据成员描由数据成员描述的存储结构述的存储结构143.2 顺序队列与循环队列3.2.2 关于存储结构的进一步讨论关于存储结构的进一步讨论 因此，插入和删除操作的实现讨论如下：因此，插入和删除操作的实现讨论如下：插入插入：插入元素：插入元素x就是要将就是要将x插入到表的末尾，因此，插入操作序列为：插入到表的末尾，因此，插入操作序列为： datacount = x; count +; 删除删除：删除就是删除表头元素，因而需将其后面所有元素往前移动一位。：删除就是删除表头元素，因而需将其后面所有元素往前移动一位。问题问题：每次删除都需要移动所有元素每次删除都需要移动所有元素， 若队

16、列足够大，花费时间太大！若队列足够大，花费时间太大！如何解决这一问题？如何解决这一问题？na1a2an01n-1maxlen-1datacount顺序队列结构顺序队列结构 下面通过对运算实下面通过对运算实现的讨论来探讨存储结现的讨论来探讨存储结构的相关问题：构的相关问题： 在这一结构下，约在这一结构下，约定定data0data0为队头元素，为队头元素，另一端为队尾。另一端为队尾。153.2 顺序队列与循环队列改进的方法改进的方法： 设置头尾指针设置头尾指针front和和rear作为作为queue的数据成员，分别指示队头和队尾。的数据成员，分别指示队头和队尾。 并并约定约定： front指向队头

17、的前一个元素，指向队头的前一个元素，rear指向队尾元素。如图所示。指向队尾元素。如图所示。 在这种情况下，插入操作和与前面类似，但写法有所不同：在这种情况下，插入操作和与前面类似，但写法有所不同： rear+; datarear = x; count +; 但删除操作要简单和省时间多了：但删除操作要简单和省时间多了：front +; count-;问题问题- “溢出溢出”现象现象: 在连续插入元素后，会使在连续插入元素后，会使rear指示到数组的末尾。指示到数组的末尾。 而此时的情况是，数组的前面可能还有空的元素空间。而此时的情况是，数组的前面可能还有空的元素空间。01n-1a1a2anma

18、xlen-1datancount顺序队列结构顺序队列结构frontrear - “假溢出假溢出”163.2 顺序队列与循环队列解决解决“假溢出假溢出”问题的方法问题的方法： 采用采用循环队列循环队列方式：将数组的头尾看作是相邻的元素，方式：将数组的头尾看作是相邻的元素，即将元素即将元素data0看作是看作是datamaxlen-1的下一个元素。如图所示。的下一个元素。如图所示。 因此，插入和删除以及状态检测需要作相应的调整：因此，插入和删除以及状态检测需要作相应的调整： 插入操作中移动指示位置的计算插入操作中移动指示位置的计算： if ( rear+1 = maxlen ) rear = 0;

19、 else rear+;或者：或者：rear = ( rear + 1 ) % maxlen ;或者：或者：rear = ( rear + 1 = maxlen ) ? 0 : rear + ;删除操作删除操作：front = ( front + 1 ) % maxlen ; 队列空队列空条件：条件： front = rear 队列满队列满条件：条件： front = rear 冲突冲突：判断队列满和空的条件相同判断队列满和空的条件相同！2maxlen-110ana1a3a2aifrontrear173.2 顺序队列与循环队列解决的方法：解决的方法：（假设不用假设不用count） （1）增加标

20、志：）增加标志： 设置一个记录最后的操作是插入还是删除的标志。设置一个记录最后的操作是插入还是删除的标志。 当出现首尾指针值相同时，当出现首尾指针值相同时， 如果标志是插入，则可断定当前队列是如果标志是插入，则可断定当前队列是- 如果标志是删除，则可断定当前队列是如果标志是删除，则可断定当前队列是- （2）约定保留一个元素空间：）约定保留一个元素空间： 即将数组约定为最多存放即将数组约定为最多存放maxlen-1个元素，个元素， 因此，使得尾指针因此，使得尾指针rear“赶不上赶不上”头指针头指针front， 因而不会出现上述的在满的情况下，头尾指针相等的情况。因而不会出现上述的在满的情况下，

21、头尾指针相等的情况。 从而便于判断的实现。从而便于判断的实现。下面采用第二种方法讨论各运算的实现。下面采用第二种方法讨论各运算的实现。2maxlen-110ana1a3a2aifrontrear183.2 顺序队列与循环队列o运算实现（循环队列）：运算实现（循环队列）：queue:queue( ) count = 0; front = rear = 0; Bool queue:empty( )const if ( count = 0 ) return TRUE; return FALSE; /等价于：return front = rear;Bool queue:full( )const if

22、( count = maxlen - 1 ) return TRUE; return FALSE; /等价于：return ( rear + 1 ) % maxlen = front ;2maxlen-110ana1a3a2aifrontrear193.2 顺序队列与循环队列error_code queue:get_front(elementtype &x)const if ( empty() ) return underflow; x = data (front + 1 ) % maxlen ; return success;error_code queue:append(const

23、 elementtype x) if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; datarear = x; count +; return success;2maxlen-110ana1a3a2aifrontrear203.2 顺序队列与循环队列error_code queue:serve() if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count -; return success;分析：分析： 算法的时间复杂度均为算法的时间复杂度

24、均为O(1).思考题：思考题：如果不设置如果不设置count分量，依据分量，依据front和和rear的值，能否计算出当的值，能否计算出当前队列的元素个数？前队列的元素个数？依据依据front和和rear是如何判断队列是如何判断队列“满满”的？的？2maxlen-110ana1a3a2aifrontrear213.3队列的应用队列的应用o 队列在软件设计中有广泛的应用o 例如：n 在操作系统中，多作业、多任务的排队n 网络中：服务器对各终端的服务请求的排队。n 在程序设计中，用队列结构存储数据构成某种次序，实现特定问题的求解。o 后面将要介绍的图的广度优先搜索遍历算法。223.3队列的应用队列

25、的应用o 例例 设计算法，用队列计算并打印杨辉三角的前设计算法，用队列计算并打印杨辉三角的前8行行的内容，即输出结果如下：的内容，即输出结果如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1p分析：杨辉三角的规律是：分析：杨辉三角的规律是：u每行的第一和最后一个数是每行的第一和最后一个数是1 1，u从第从第3 3行开始的其余的数是上一行对应行开始的其余的数是上一行对应位置的左右两个数的和。位置的左右两个数的和。u例如，第例如，第7 7行的第行的第3 3个数个数1515是第是第6

26、 6行中的行中的第第2 2和第和第3 3两个数两个数5 5和和1010的和。的和。u由这一规律可知，我们可用上一行的数由这一规律可知，我们可用上一行的数来求出对应位置的下一行的内容。来求出对应位置的下一行的内容。u为此，要用队列来保存上一行的内容。为此，要用队列来保存上一行的内容。u每当由上一行的两个数求出下一行的一每当由上一行的两个数求出下一行的一个数时，其中的前一个便需要删除，而新个数时，其中的前一个便需要删除，而新求出的数就要入队。求出的数就要入队。233.3队列的应用队列的应用n为了由存放在队列中的某行的内容求得下一行的内容，为了由存放在队列中的某行的内容求得下一行的内容，需要在两者之间建立一个对应关系。需要在两者之间建立一个对应关系。n为便于求解，在每行的第一个位置添加一个为便于求解，在每行的第一个位置添加一个0作为辅助。作为辅助。n例如，由第例如，由第6行求解第行求解第7行的对应关系示意图如下所示。行的对应关系示意图如下所示。 s1 s2 0 1 5 10 10 5 1 1 6 15 20 15 6 1n 新一行的最后一个不能由上一行求得，好在其值是新一行的最后一个不能由上一行求得，好在其值是确定的数确定的数1，只要直接