简单队列算法

这是不是请求排队算法，我知道有很多。简单队列算法

我正在阅读一本C＃书，它用一个代码示例解释了Circular Queue算法。在第13,14和15行，他解释了如何检查队列是否已满。但我不明白为什么第一个可选条件是必要的。有人能告诉我一个需要它的情况吗？

下面是类代码：

我的问题是关于这个部分：（putloc + 1 == getloc）

public bool Put(char ch) {  
    /* Queue is full if either putloc is one less than 
    getloc, or if putloc is at the end of the array 
    and getloc is at the beginning. */ 
    if (putloc + 1 == getloc || ((putloc == q.Length - 1) && (getloc == 0))) 
    { 
     return false; 
    }

来源

2009-10-19 Daniel S

第一次检查是执行以下部分评论中的声明。

putloc比getloc

需要这种检查，因为您的队列为圆形少一个。如果您始终可以认为队列的末尾是阵列中的最后一个元素，则不需要检查。在这种情况下，尽管...队列的末尾可能发生在阵列的中间，在这种情况下，队列将变满并且您遇到了这种情况。

来源

2009-10-19 19:18:55

谢谢！这是最终让我更加思考的答案，并让我了解了循环队列概念。忍受着我，我只有15岁，而且我在数学上也不例外:) – 2009-10-19 19:39:43

说getloc是5并且putloc是4，那么这意味着你没有更多空间来放置任何东西。因为如果你把东西放在5号，那么你就失去了5号，因为你还没有读出来。

来源

2009-10-19 19:20:27 BFree

该逻辑可以通过以下形式可以更好地理解：

int new_putloc = (putloc + 1) % q.Length; 
if (new_putloc == getloc) return false;

原始代码只是打破上述逻辑下到两种情况：

putloc不倒带，则new_putloc = putloc 1
putloc被倒带，则put_loc = q.Length-1

来源

2009-10-19 19:23:23 Codism

在一个循环队列中，无论什么时候你将东西推入它，putLoc都会向下移动数组，最后环绕。无论何时你从队列中弹出一些东西，getLoc会向下移动数组，最后也会打包。 putLoc位于getLoc之前时，该队列被视为已满。

有2种情况可能发生。如果getLoc从来没有移动过，或者恰好已经回到数组的开头，那么当putLoc位于数组的末尾（下一次推动会使它换行为0）时，它位于0并且队列已满。这是if语句的后半部分。

如果队列中有几个值已经弹出，那么getLoc可能位于数组的中间。在这种情况下，当putLoc位于数组的末尾时，队列是满的，但是当它被环绕并且位于getLoc之前时。 if语句的第一部分（你正在询问的部分）正在处理的情况就是这种情况。

来源

2009-10-19 19:24:00 Herms

这两个实际上是相同的条件。从模平等角度考虑它。

当添加的最新元素位于位置N（模长度）并且最早的元素位于位置N + 1（模长）时，用数组实现的循环队列已满。这意味着队列中有“长度”元素，并且没有更多空间可用于新队列，因此已满。

有许多方法可以对该测试进行编码，但代码示例使用的方法是使用直接算术版本而不使用模数。

你也可以这样的代码是：

if ((putloc + 1) % q.length == getloc) {}

，这将是逻辑上是相同的，只要getloc正确界定为0和q.length - 1之间。

来源

2009-10-19 19:24:37 jprete

表达式的左半部分是几乎适用于所有场景的主要部分，右半部分是唯一的边缘情况，其中putloc是队列的结尾，getloc是队列的开始。当putloc为4且getloc为5时，左侧为true，但当队列长度为10且putloc为9且getloc为0时，右侧为true。

来源

2009-10-19 19:26:07

队列已满，如果 (((in+1)%queue_length)==out) 队列为空，如果 (in==out) 注意，“在”是指向该数据推入队列，而“出”点的数据的流行形式队列。

来源

2010-11-02 20:17:32

简单队列算法

回答

相关问题