reverse a queue using an empty queue-CodePudding

I have a queue [3,2,1] and I want to reverse it using only enqueue and dequeue functions. My final queue should be [1,2,3].

I cannot declare any local variables. I only have 2 queues one is empty and the other has data in it. I want to reverse the queue which has data using the empty queue only. I don't have access to the pointers of the queue.

I only have 1 global variable, but I can't declare local variables otherwise it can be done easily by recursion. And I don't have peek back and pop back function either. Only have enqueue, dequeue, length, empty and front.

Is this possible?

queue1 = [3,2,1]
queue2 = []

final result
queue1 = [1,2,3]
queue2 = []

CodePudding user response：

It seems crucial you have one global variable to use. So let that be a number which can be used for looping.

The idea is to rotate queue1 (dequeue enqueue) until it has its (originally) last element first. Then this one can be transferred to queue2. Now queue1 looks like it was originally, but without its last element. Repeat this procedure until it is empty.

This gives the desired result in queue2. As it was asked to get the result in queue1, we can first move all elements from queue1 into queue2, except the last one. And then we can apply the above described procedure on queue2 and make the transfer of the wanted element to queue1.

global i

reverse(queue1):
    queue2 = new Queue()
 
    repeat queue1.length-1 times:
        queue2.equeue(queue1.dequeue())
    repeat until queue2.empty():
        for i = queue2.length-1 downto 1:
            queue2.equeue(queue2.dequeue())
        queue1.enqueue(queue2.dequeue())

Here is an implementation in runnable JavaScript snippet (push = enqueue, shift = dequeue):

let i; // One global variable
let queue1 = [];
let queue2 = [];
// Populate the first queue
for (i = 1; i <= 5; i  ) {
    queue1.push(i);
}
console.log(...queue1);
// Start of the reversal algorithm
// Move all but the last element to the other queue
while (queue1.length > 1) {
    queue2.push(queue1.shift());
}
while (queue2.length > 0) {
    // Rotate queue2 to bring last element at the front
    for (i = queue2.length-1; i > 0; i--) {
        queue2.push(queue2.shift());
    }
    // Move that front element to the first queue
    queue1.push(queue2.shift());
}
// End of the algorithm. Print the result
console.log(...queue1);

CodePudding user response：

It's impossible.

Try to visualize this way:

All your enqueue and dequeue operations in both queues will look like moving numbers from left to right and right to left and hoping they will eventually change their order, but they won't.

Always you dequeue a number from the second queue, it will return to its original position in the first queue.

CodePudding user response：

I should have asked if you need to do this for production or homework. If you're doing it for production, then don't. Queues are FIFO and ~~better~~ specific datatypes exist for that, like deque. If this is a homework problem for you to flex your algorithm chops, then you can do something like this.

object RemoveLast(Queue q) {
    object first = q.Peek();
    object current = null;
    while (true) {
        current = q.Dequeue();
        if (q.Count == 0 || q.Peek() == first) {
            break;
        }
        q.Enqueue(current);
    }
    return current;
}