不使用临时队列遍历循环队列

Question

基本上，我得到了一个CircularQueue的实现，需要实现一个名为'public boolean contains (E other)'的方法，如果参数'other'存在于我的队列中，则应返回true。

因为它是一个数组，所以我还好，但是我看到还有这个附加条件让我很困惑。

请记住，您不能自由地在队列中导航所有元素。仅可以通过peek方法随时访问队列的前面元素。 您对contains和intersectWith方法的实现不得使用任何额外的队列来临时保存此队列的某些元素。

一个迭代器是否适用于解决这个问题？

非常感谢您的任何帮助。

Mjall

解决方案：

我想出了一个答案，方法rotate的描述如下： 方法rotate(int n)从队列的前面移除n个元素并将它们添加到队列的后面。元素按照从队列前面移除的顺序添加到队列的后面。例如，给定包含元素“A，B，C，D，E”的队列q，其中元素A位于队列的前面，在调用方法q.rotate(2)后，队列的内容将是“C，D，E，A，B”；

   public boolean contains(E elem) { 

    while( this.isEmpty() != true){

      if(this.peek() == elem){return true;}
      else{rotate(1);}



   } 
   return false;

 }

- Mjall2

---

一个元素可以在队列中出现两次吗？[我的意思是实际对象，而不是相等的身份] - 如果不行，为什么不能持有头部的临时引用，并迭代直到再次看到它？ - amit

@amit：听起来约束条件是你不能只进行迭代。“任何时候只有前一个元素是可访问的”。 - Oliver Charlesworth

@OliCharlesworth：在这个循环队列中，如果你弹出了所有元素，队列会变为空吗？还是会回到旧的头部？[我假设是后者，并将其称为迭代] - amit

Answer 1

在这种情况下，使用迭代器并不实用。

由于它是一个循环队列，您可以记住您已经看到的第一件事（不一定要完全从循环队列中删除它），并出队/入队元素，直到找到您要查找的内容，或者到达第一个出队节点。

- Makoto

---

@amit：如果头部（前面）被推了两次？这是否意味着入队了两次？ - Mjall2

@Mjall2：是的，假设我有一个循环队列，并且我将同一对象推入两次，它应该被添加两次到队列中，但是建议的算法会在找到第二个出现时停止，可能无法扫描队列中的所有元素。 - amit

@amit：contains方法仅用于检查作为参数传递的元素是否至少在队列中存在一次。 - Mjall2

@Makoto：从circularQueue中出队，然后将其入队到同一个circularQueue中...但是我如何保持顺序的完整性？ - Mjall2

@Mjall2，我在想除了这种方法，你可能还要依靠计算队列中元素的总数来保证队列的完整性（例如，头被推两次）。 - Makoto