3

Basically I've been given an implementation of a CircularQueue, I need to implement a method called 'public boolean contains (E other)' which is supposed to return true if the parameter 'other' exists in my queue.

I was ok with it because it was an array, but then I saw this other condition to it which is bugging me.

Remember that you cannot freely navigate across all elements in a queue. Only the front element is accessible at any time through the peek method. Your implementation of the contains and intersectWith methods MUST NOT make use of any extra queue to temporarily hold some of the elements of this queue.

Would an Iterator be applicable to solve this problem?

Any help is highly appreciated.

Mjall

Solution:

Answer I came up with, method rotate description: The method rotate( int n ) removes n elements from the front of the queue and adds them to the rear of the queue. The elements are added at the rear of the queue in the same order as they are removed from the front of the queue. For example, given a queue q containing the elements \A, B, C, D, E", where the element A is at the front of the queue, following the method call q.rotate( 2 ), the content of the queue will be \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;

 }
3
  • can an element be twice in the queue? [I mean the actual object, identity not equality] - if not, why can't you hold a temporary reference of the head, and iterate until you see it again?
    – amit
    Apr 7, 2012 at 22:42
  • @amit: It sounds like the constraint is that you can't just iterate. "Only the front element is accessible at any time". Apr 7, 2012 at 22:43
  • @OliCharlesworth: In this circular queue, if you popped all elements, will the queue be empty or will it return to the old head? [I assumed the second and refered to it as iterating]
    – amit
    Apr 7, 2012 at 22:44

1 Answer 1

1

An iterator would not be practical for this situation.

Since it's a circular queue, you can remember the first thing you've seen (not necessarily removing it from the circular queue entirely), and dequeue/enqueue elements until you find what you're looking for, or arrive at the first dequeued node.

10
  • That's what I thought, but in order to dequeue from one queue, then enqueue into a different temporary queue, while doing this checking whether the value is there, then dequeuing from the temporary queue and enqueuing into the original queue (to maintain the original data). Is not allowed..
    – Mjall2
    Apr 7, 2012 at 22:44
  • And what if the head was pushed twice? You will stop before you scanned all elements. [I am assuming no access to the node object, only to the element object via the queue]
    – amit
    Apr 7, 2012 at 22:45
  • @Mjall2: Who said anything about a temporary queue? Apr 7, 2012 at 22:45
  • @Makoto: If im using the dequeue method, it returns the element taken out of the queue, i need a variable to hold it. Then the variable matched with another element, if not matching, then enqueued into temp queue..so on until original queue is empty or i've found the value, then replace all the values from the temp queue to the original
    – Mjall2
    Apr 7, 2012 at 22:48
  • @amit: If the head (front) was pushed twice? Does that mean enqueued twice?
    – Mjall2
    Apr 7, 2012 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.