Alternative queue reversal

Question

Suppose I have a queue filled with some types of elements, and they are filled in such a way that if any two elements are evaluated the same using the assigned comparator, they will be adjacent to each other.

Now I want to change the queue as follows: if all the elements in the queue are unique, then cancel it as the usual definition of the opposite.

If there are some elements that are the same (and they will be adjacent to each other, given how they are filled), cancel the queue, but keep the relative position of the unique elements.

A chart may be easier to understand what the problem is.

If the queue looks like this:

[11 22 33 44 55] 

and my comparer compares two integers, looking at their first digit, then the back of the queue is higher:

 [55 44 33 22 11] 

However, if my input queue is:

 [11 22 23 44 55] 

the opposite should be:

 [55 44 22 23 11] 

subject to comparison.

I am trying to do this in a recursive way, using only one stack as additional auxiliary storage. However, it is difficult for me to understand the correct and effective way. Could you help me? Thank you very much!

PS: The reason I use the stack as additional storage is because queue reversal in the usual way is most easily done using the stack (dequeue and push all to the stack, and then pop and enqueue back to the queue).

Answer 1

Approach 1)

First, cancel the entire queue (excluding the equality of 21.22, etc.), then cancel each individual block (for example, 21.22, etc.) using the stack. This can be done iteratively.

This is similar to the inverse of the sentence problem (a well-known interview question).

(see the given example and pseudo-code below)

Approach 2)

If you want to absolutely perform recursion, I would suggest you use Queue as auxiliary storage, not a stack.

You insert the block into the auxiliary queue, recursively modify the rest of the list, and then insert the elements back into the main queue.

The code will be something like this (handwavy pseudo)

 StrangeReverse(Queue <T> q) { Queue<T> aux; // this removes first block from q, and places them in aux while (elem_of_first_block(q)) { aux.Enque(elem); } // Recursively reverse the rest of the q. StrangeReverse(q); // place the first block back in q, at the end. // in the order they appeared originally. while (aux.HasElements()) { q.Enque(aux.Deque()); } } 

A recursive version can be converted to iterative, having a queue stack! You create a queue from each block and add them. Then put the stack, use the queues.

Developed example approach 1

[11, 12, 21, 22, 43, 44]

Discard it (using stack or recursive method)

[44, 43, 22, 21, 12, 11]

Now undo each block:

push 44, the 43.

Stack = [44, 43]. Queue = [22, 21, 12, 11]

Now enque, jumping out of the stack

Stack = [], Queue = [22, 21, 12, 11, 43, 44]

push 22, 21

Stack = [22, 21], Queue = [12, 11, 43, 44]

Enque clicking a stack.

Stack = [], Queue = [12, 11, 43, 44, 21, 22]

Finally, we get

[43, 44, 21, 22, 11, 12]

Note. To determine the block, you may need the peek method in the queue.

Pseudocode Approach 1

 void StrangeReverse(Queue<T> q) { Stack<T> s; int count = q.Count(); if (count < 2) return; for (i = 0; i < count; i++) { T elem = q.Deque(); s.Push(elem); } while (s.HasElements()) { T elem = s.Pop(); q.Enque(elem); } // Now the queue has been reversed, // in the normal fashion. ReverseBlocks(q); } void ReverseBlocks(Queue<T> q) { int reversed = 0; int count = q.Count(); while (reversed < count) { reversed += ReverseSingleBlock(q); } } int ReverseSingleBlock(Queue <T> q) { Stack <T> s; T prevElem = q.Deque(); s.Push(prevElem); T curElem = q.Peek(); while(curElem == prevElem) { s.Push(curElem); q.Deque(); prevElem = curElem; curElem = q.Peek(); } int count = 0; while(s.HasElements()) { T elem = s.Pop(); q.Enque(elem); count++; } return count; } 

Answer 2

still assumed: enque → [11,21,22,23,30] → deque / peek
should be better now:

 first = queue.peek(); start = true; while (queue.peek() != first || start) { start = false; el = queue.deque(); if (el.compare(queue.peek())) { stack.push(el); while (el.compare(queue.peek())) { el1 = queue.dequeue(); if (first.compare(el1)) { first = el1; } stack.push(el1); } while (!stack.isEmpty()) { queue.enque(stack.pop()); } } else { queue.enque(el); } } while (!queue.isEmpty()) { stack.push(queue.deque()); } while (!stack.isEmpty()) { queue.enque(stack.pop()); } 

so first I turn the queue by changing the order of the "equivalent" elements and finally I do the usual reverse queue

Answer 3

  class ReverseQueue(object): def __init__(self, limit=5): self.rear = None self.front = None self.que = [] self.size = 0 self.limit = limit def enQueue(self, item): if self.size >= self.limit: print "Queue Overflow" return else: self.que.append(item) # two case # 1. if front is None then the queue is empty. # so if item is added both front # end point to the same position ie 0 # 2. if front is not None then item is added to the end of the # list(append does that). we then increase the size of rear # note: rear is 0 indexed but size is not # that why there a diff of 1 always b/w these rear and size if self.front is None: self.rear = self.front = 0 self.size = 1 else: self.rear = self.size self.size += 1 return def deQueue(self): if self.size <= 0: print "Queue Underflow" return else: temp = self.que.pop(0) # change the size self.size -= 1 # if list is empty set both front and rear = None # This is in sync with the queue method # where we check if front = none when adding item # change front and rear if self.size is 0: # if only one element self.rear = self.front = None else: # more then one element self.rear -= 1 return temp def isEmpty(self): return self.size <= 0 def reverse(self): if not self.isEmpty(): temp = self.deQueue() self.reverse() self.enQueue(temp) 

myQueue = ReverseQueue ()

myQueue.enQueue ("First")

myQueue.enQueue ("Second")

myQueue.enQueue ("Third")

myQueue.enQueue ("Fourth")

myQueue.enQueue ("Fifth")

print myQueue.que

myQueue.reverse ()

print myQueue.que

Answer 4

Here is a code snippet to cancel a C ++ STL queue using recursion.

 void reverseQueue(queue<int>& q){ while(q.size() != 0){ q.pop(); reverseQueue(q); q.push(value); break; } }