2

我需要帮助理解循环队列的概念。我在 stackoverflow 上阅读了几篇文章，但没有一个答案能回答我遇到的心理障碍。

例如，假设我在循环队列中有 8 个单元格。

        Head                              Tail
 empty|U    |   I  |   S  |   K  |   M  |   empty  |   empty

假设我插入两个字符 F 和 P，这将使队列更改为。

  Tail  Head                                
 empty|U    |   I  |   S  |   K  |   M  |   F  |   P

现在让事情变得有趣，如果我删除 3 个条目会怎样。

  Tail                                  Head                
 empty|  empty  |  empty   |  empty   |   K  |   M  |   F  |   P

显然，我的头部和尾部现在已经改变，并且我有 3 个新的可用位置。但为了更好的措施，我想再添加两个条目。

            Tail                Head                
 A|  B  |  empty   |  empty   |   K  |   M  |   F  |   P

这是我的问题

我执行对了吗？大声笑当你完全填满队列时会发生什么，因为尾巴和头在同一个位置，即“K”？如果有人可以更详细和清晰地解释这个概念，我将不胜感激。

谢谢！

4

2 回答 2

1

在我看来，你说得对。您可以通过显示头部和尾部的整数值使您的图表更清晰

关于循环队列有很多解释和例子。我没有找到比我在前段时间在这里提供的答案中发布的解释更好的解释。它解释了队列为空、有空间或已满时如何显示头部和尾部。

在图表的最后一行，队列还有 2 个项目的空间。添加第三个会使tail = head，并会覆盖您不想这样做的K。

当tail = head时，队列为空。测试一个完整的队列稍微复杂一些。有关完整说明，请参阅链接。

于 2015-04-09T01:40:19.263 回答
1

我执行对了吗？

是的，你确实做到了。

当你完全填满队列时会发生什么，因为尾巴和头在同一位置，即“K”？

K 将被覆盖。这个溢出条件可以通过条件 TAIL == HEAD 来检查。

如果有人可以更详细和清晰地解释这个概念，我将不胜感激。

您必须了解，在传统的线性 FIFO 队列中，只要达到最大大小，就需要连续移动元素。例如，如果队列的大小为 5，则在 5（数字 1-5）连续插入和删除（数字 1 被删除）之后，队列变为 [null, 2, 3, 4, 5]。您可以在此处看到，虽然还有 1 个元素的位置，但您无法插入，除非您将所有元素上移 1 个。这就是使用循环队列的原因。它不需要元素转换。

但是，如果您的队列不断被溢出，队列的全部目的就失去了。我建议使用链表（线性或循环），因为它动态添加和删除元素。

请记住，当内存受到限制时，实际上会使用队列。例如，输入/输出流是一个队列。当内存充足且不喜欢数据覆盖时，使用链表。

于 2015-05-22T04:54:12.530 回答