为什么Q.head = Q.tail +1表示CLRS中的队列已满 [英] Why Q.head = Q.tail + 1 represents the queue is full in CLRS

问题描述

我正在从CLRS中读取基本数据结构，并且在读取队列ADT时遇到了这个问题：

I was reading Elementary Data Structures from CLRS and while reading Queue ADT I came across this:

当Q.head = Q时。 tail + 1，队列已满，如果我们尝试加入
元素，则队列溢出。

When Q.head = Q.tail + 1 , the queue is full, and if we attempt to enqueue an element, then the queue overflows.

总是这样吗？因为如果Q.tail等于Q.length，则根据文本将Q.tail设置为1。因此，如果我们完全填充队列，则Q.tail和Q.head将指向相同的位置（索引1），并且上述条件将不成立。我在这里想念什么？请指出我在哪里误解文本。

Is it always true? because if Q.tail equals Q.length then we set Q.tail = 1 according to the text. Therefore if we completely fill the Queue then Q.tail and Q.head will be pointing to the same position (index 1) and the above condition shall not hold. What am I missing here? Please point out where am I misinterpreting the text. Thanks in advance.

此处属性Q.head索引或指向队列的头部。属性Q.tail索引将新到达的元素插入队列的下一个位置。

Here Attribute Q.head indexes, or points to, queue's head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue.

推荐答案

包装队列功能：

您需要了解以下事实：数组中的位置1以循环顺序紧随位置n之后。
例如

You need to understand the fact that location 1 in the array immediately follows location n in circular order. For example

在索引1处元素g的前任是在索引11处的f。尾指针始终在排队操作中指向将要插入新元素的下一个空位置，在插入元素之前，我们检查是否存在溢出条件（如果Q）。 tail +1 = Q.head，表示尾部到达头部位置，表示没有可用空间，表示队列已满。

Predecessor of element g at index 1 is f at index 11. Tail pointer always points to the next empty location where new element will be inserted, in enqueue operation, before inserting element we check for overflow condition, if Q.tail +1 = Q.head, it means tail is reached at head location, means no free space, means queue is full.

注意：（n- 1）可以使用长度为n的数组创建长度队列。

这篇关于为什么Q.head = Q.tail +1表示CLRS中的队列已满的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！