汇编网

帐号密码


多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页首页上一页下一页尾页

算法讲堂
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。现本栏目的内容处于不断添加中，请随时关注。

算法讲堂－》队列【算法讲解】

    队列
一、概述：
    线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
    在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。本文将对队列形式的线性表的进行详细的设计描述。
在计算机科学中，队列（queue）是一种特殊的线性表，它具有线性表的所有特性，此外它只允许在表的一端插入节点元素，而能在表的另一端删除节点元素，实现了线性表修改的先进先出（First In First Out）（或者说后进后出Last In Last Out）处理原则。进行插入操作的端称为队尾（rear），进行删除操作的端称为队头（head）。队列中没有节点元素时，称为空队列。队列长度达到规定的最大值时称队列满。已经进入队列的节点元素次序不能再做改变。在任何时刻，我们关心的只是队列的队头和队尾，如在二者之间作一个比较，那么队头的关注度更多一些。可以这样说，队列里的任何一个节点元素，要想受到关注都要努力向队头移动。
    根据以上描述，队列可以整理出以下基本操作：
         1、创建初始化：按约定置队列为空状态。
         2、入队列：在队尾加入一个新节点元素。
         3、出队列：从队首取出一个节点元素，并使余下诸项向队首移动。
         4、队列空：判断队列是否为空。
         5、队列满：判断队列是否已满。
         6、清空队列：所有节点元素出队。
    从概念上说，队列不存在“满”状态，其长度可以任意增加，但实现（不论静态或动态）中总有空间限制的。
二、队列的存储结构及基本算法描述：
    我们如何把一个又一个长度为node_Len的节点元素node放入队列或从队列中取出呢？先要了解一下队列的存储结构。队列的存储结构既可以采用顺序结构，也可以采用链式结构。我们这里不考虑队列的特殊应用和特殊形式，只就一般的队列进行描述。
1、队列的顺序存储结构：
    队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，用一个连续的内存空间来存储，队列所容许的最大节点数受到这段连续内存空间大小的限制。在队列的运算中需设置两个指针：
        head：队头指针，指向实际队头元素的前一个位置；
        rear：队尾指针，指向实际队尾元素所在的位置。
    一般情况下，两个指针的初始值皆设置为0，此时队列为空，其中没有元素。
2、顺序队列基本算法描述：
     a)入队：在队列不满的条件下，如果想让一个新元素入队，则需尾指针向后移动一个节点位置，即rear=rear+1*node_Len。并将新节点存放在rear所指向的位置上。本算法时间复杂度为O(1)。
     b)出队：在队列不为空的条件下，如果想让一个队列元素出队，则需头指针向后移动一个节点位置，即head=head+1*node_Len。并将head所指向位置上的节点传送出去。本算法时间复杂度为O(1)。
    c)返回队首元素值：首先判断循环队列是否为“空”，若空则返回出错信息。否则返回队首元素值。本算法时间复杂度为O(1)。

    由上面的描述不难得出这样的结论：随着入队和出队操作的交替进行队列在分配给它的内存空间中是不断向内存空间的后部移动的，要解决空间的问题，可以在每次出队操作结束后将队列整体向低内存地址移动，但是这样会使操作的时间复杂度和空间复杂度增加。
3、顺序队列中的溢出现象：
　　a) "下溢"现象
    　当队列为空时，做出队操作产生的空间溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
　　b) "真上溢"现象
    　当队列满时，做进栈操作产生的空间溢出现象。“真上溢”是一种出错状态，应设法避免。
　　c) "假上溢"现象
　　由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。但实际上队列中可能因为以前的出队操作而产生了空位置，也就是说队列实际并没有占满所有分配给它的内存空间，当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
　【例】假设下述操作序列作用在初始为空的顺序队列上：
          EnQueue，DeQueue，EnQueue，DeQueue，…
    这里，尽管在任何时刻，队列元素的个数均不超过1，但是只要该序列足够长，如此操作下去，事先定义的向量空间无论多大均会产生指针越界错误。
    解决假溢出的方法有两种。一种是每当有出队操作完成就将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种是将队列存储区看成一个首尾相接的环形区域。当队列节点存放到分配的内存空间末尾地址后，下一个节点位置就"翻转"为队列内存空间的首地址。在结构上采用这种技巧来存储的队列称为循环队列（Circular Queue）。
4、循环队列：
    a)循环队列是有长度设置的，这里称循环队列的最大长度为queue_Max_Len。在对循环队列的操作当中，若head(或rear)值为queue_Max_Len-1*node_Len,则移动后head(或rear)的值就变成0了，只要当前队列长度小于queue_Max_Len，就可以继续执行入队列操作。
    b)对于循环队列必须注意怎样判断队列的空与满的状态。除起始状态外。任何时刻rear所指为最后一个进入队列的元素，而head所指的是刚刚出队列的那个元素原先所占的位置。因此(head+1) mod queue_size才是真正当前队列中首元素位置。
    c)循环队列边界条件处理
    循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件head==rear来判别队列是"空"还是"满"。
    解决这个问题的方法至少有三种：
　　1)另设一布尔变量以区别队列的空和满；
　　2)少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
　　3)使用一个计数器记录队列中元素的总数（即队列长度）。
5、循环队列基本算法描述：
    a)入队：首先由条件等式判断循环队列是否为“满”，若满则返回出错信息。否则插入新节点元素，并使尾指针沿环指向下一位置。本算法时间复杂度为O(1)。
    b)出队：首先由条件等式判断循环队列是否为“空”，若空则返回出错信息。否则返回队首节点元素值，并使头指针沿环指向下一位置。本算法时间复杂度为O(1)。
    c)首先由条件等式判断循环队列是否为“空”，若空则返回出错信息。否则返回队首元素值。本算法时间复杂度为O(1)。
6、队列的链式存储结构：
    队列元素节点也可以用不连续的存储空间存放，即采用单向链表的形式。其特点如下：
    a)无须考虑判队满的运算及上溢。
    b)在出队算法中，一般只需修改队头指针。但当原队中只有一个节点时，该节点既是队头也是队尾，故删去此节点时亦需修改尾指针，且删去此节点后队列变空。
    c)以上讨论的是无头节点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头节点前也可附加一个头节点，增加头节点的链队列的基本运算。
7、链式队列基本算法描述：
    a)入队：当新的节点元素入队时，首先创造链队列元素节点，并使原来的队尾节点元素的指针指向该节点元素，同时使尾指针也指向该节点元素，使该元素成为新的队尾元素。本算法的时间复杂度为
O(1)。
    b)出队：当删除链队列的队首元素时，首先检查队列是否为空，如果为空，则返回错误。若队列不为空，取出队首元素，使头节点的指针指向原队首节点元素的指针域所指向的节点，然后释放该节点空间。本算法的时间复杂度为O(1)。
    c)首先检查链队列是否为空，如果为空，则返回错误。若队列不为空，则直接返回队首元素的数据即可。本算法的时间复杂度为O(1)。
    d)遍历：从队首元素开始，通过队列元素的指针域向队尾循环。该算法的主要操作和影响算法效率的步骤为循环遍历队列的元素，频数和队列的元素个数相同，所以本算法的时间复杂度为O(n)。
三、队列有着非常广泛的应用。
    对于队列在算机科学领域所起的作用主要是解决计算机的两个方面的问题。第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。
    关于第一个方面，仅以主机和打印机之间速度不匹配的问题为例作一下简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然会造成打印的混乱，是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入到这个缓冲区中，写满后就暂停向缓冲区的输出，转去处理其它的任务。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完成后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又提高了主机的效率。不难看出，这里对打印数据缓冲区中所存储的数据的存取方式就是队列。
    关于第二个方面，用户对CPU这个资源的竞争就是一个典型的例子。在一个拥有多终端的计算机系统上，在某一个时间间隔内往往会有多个用户需要CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出占用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给处于队首的请求用户使用。当相应的程序运行结束或用完规定的时间间隔后，则令其出队，再把CPU分配给新的队首请求的用户使用。这样既满足了每个用户的请求，又使CPU能够正常运行。
四、学习建议及练习任务
    队列的实现原理是基于连续地址的顺序存储结构和链式存储结构的，学习者在理解队列的顺序存储结构和链式存储结构后，可以尝试实现下面的“停车场问题”，体会队列应用的算法。
停车场问题：
    假设停车场有一个出口和一个入口，出口只允许汽车离开停车场，入口只允许汽车进入停车场。停车场为每辆车编排一个编号，在停车场中停放的位置任意，但离开停车场必须按照编号顺序，请模拟停车场每天的调度情况。
    在屏幕显示当前停车场的状态。每辆车用车牌号代表其本身，每辆车进入或离开时它的车牌号和编号也在屏幕上显示出来。

[07/09/21]

Email: asmedu@163.com