乌鲁木齐白癜风专科医院 http://baidianfeng.39.net/bdfby/yqyy/上一篇说到，队列是一种特殊的线性表。既然如此，它便也有顺序和链式两种存储方式。顺序存储中，也是用数组来实现队列的存储。我们最先的考虑是，0处为队头，队列最后一位是队尾。但是与栈不同，队列是尾进头出的，单是入队还不要紧，只需要给队尾加上一位即可；但出队就麻烦了，既需要删除队头，又需要把所有元素都向前移动一位，让队头的位置得到填充，这样操作的复杂度为O[n]，不太好。于是我们为了弥补这个缺陷，可以让队头的位置不是固定在0处，而是可以随着出队的操作而向后移动，这样就不需要了把每个元素都向前挪动了，大大提高了效率。这么做的话，需要定义两个指针：front指向队头，rear指向队尾的下一个位置。这么定义的好处显而易见，当只有一个元素时，两个指针不会重合，而空队列的两个指针才会重合在一起。这么做还是有问题。当不断地出队、入队后，队尾位置可能会超出数组长度，但队头之前的位置却还是空的，这种现象叫做“假溢出”，顾名思义，数据并没有大到溢出数组，但队尾的位置却超出了数组的范围。如何解决这种问题呢？我们可以使用循环队列，其特点是“头尾相接”，当队尾超出数组一个位置时，让它回到0位置继续存储和进行后续操作，这样就能充分地利用数组的空间了。这时还有一个小问题，循环队列在空队列和满队列情况下，rear和front都是重合的，怎样分辨这两种情况呢？书中给出了两种方法：可以设置一个布尔变量flag，rear==front时，若flag==1则队列满，flag==0时队列空；或者当队列满时，我们设定必须留空一位，rear指向这个空位，而不允许队头与队尾重合。
图一第二种解决方案示意图
书中重点讨论了第二种方法，推导出了该情况下的队列长度计算公式：(rear-front+QueueSize)%QueueSize.稍微解释一下这个式子，QueueSize是数组长度，把整个式子拆开来看就是(rear-front)%QueueSize+QueueSize%QueueSize，后项意义不大，最初在括号里设置QueueSize项只是为了取正值方便计算，但没有它也可以顺利计算。核心是前项，其含义为尾头指针之差除以数组长度的余数，当尾头指针差值为零时，就是队列空的情况，队列长度自然为零；当差值为正时，对应队头在前队尾在后的情况，差值自然为此时的队列长度；为负时，代表尾前头后，差值对QueueSize取模，结果就是负值加了一个QueueSize的大小，转化成了正值，这就是此时队列的长度。队列的链式存储结构称为链队列，它的front指向头结点，而rear指向队尾。
图二链队列示意图
链队列的入队操作，就是在队尾插入新结点。具体操作是，把队尾的后继指针指向新结点，然后把rear也指向新结点。其出队操作，就是把第一个结点移除，然后把头结点的后继指针指向原来第二个结点。若原先队列里除头结点外只有一个结点，则移除该结点后，需要把rear指向头结点，而头结点的后继指针设为空。
图三链队列的出队操作
对于循环队列和链队列的比较，也是从两方面考虑的。时间上，两者基操均O[1]，差异比较小；空间上，循环队列必须有固定的数组空间，容易产生空间浪费和数据溢出的问题，而链队列需要有额外的指针域，空间成本更大，但能充分利用空间，更加灵活。预览时标签不可点收录于话题#个上一篇下一篇