为什么Q.head = Q.tail + 1表示CLRS中的队列已满
Ris*_*abh 6 algorithm queue data-structures
我正在阅读CLRS中的基本数据结构,在阅读Queue ADT时,我遇到了这个问题:
当Q.head = Q.tail + 1时,队列已满,如果我们尝试将一个元素入队,则队列溢出.
它总是如此吗？因为如果Q.tail等于Q.length,那么我们根据文本设置Q.tail = 1.因此,如果我们完全填充队列,那么Q.tail和Q.head将指向相同的位置(索引1),并且上述条件不成立.我在这里错过了什么？请指出我在哪里误解了文本.提前致谢.
这里属性Q.head索引或指向队列的头部.属性Q.tail索引新到达的元素将被插入队列的下一个位置.
正如在 CLRS 的同一段中提到的，
使用数组 Q[1...n] 实现最多包含 n-1 个元素的队列。
这意味着还剩下一个位置。用于检查队列是否已满。如果我们使用所有的数组位置，空队列条件和满队列条件将相同，即 Q.head=Q.tail。@siddstuff 已经解释了环绕功能，Q.head = Q.tail+1 表示只剩下一个空位，所以队列已满。
包裹队列的功能:
您需要了解数组中的位置1按循环顺序紧跟位置n的事实.例如
索引1处的元素g的前导是索引11处的f.尾部指针始终指向将插入新元素的下一个空位置,在插入操作中,在插入元素之前我们检查溢出条件,如果Q.tail +1 = Q .head,表示在头部位置到达尾部,表示没有空闲空间,表示队列已满.
注意:可以使用长度为n的数组创建(n-1)长度队列.
- 我在阅读那条线时有同样的问题。我仍然不明白为什么算法会以这种方式检查溢出条件？Q.tail +1 = Q.head表示Q.tail位置为空且可用。 (2认同)
- 这意味着我们只能将 'i' 和 'j' 加入队列；'j' 入队后，tail 将指向 5。当我们继续入队 'k' 时，我们进行溢出检查并发现 tail+1 == 6。然后我们抛出错误。所以 5 将是空的。这就是为什么 CLRS 说使用 n 的数组大小只能存储 n-1 个元素。 (2认同)
- @mkc 起初它也让我感到困惑，但后来我记得因为我们只想拥有 n 个元素的数组的 [n - 1] 个元素，所以 head 旁边的插入顺序中的位置预计是空的。同样的理解有助于解释为什么当 Q.head = 1 且 Q.tail = Q.length 时，队列也被认为已满 (2认同)
| 归档时间： |
|
| 查看次数： |
3200 次 |
| 最近记录： |