Algorithm for reversing two adjacent entries in a queue

Question

Suppose you were given two queues and you were only allowed to move one entry at a time from the head of a queue to the tail of either. Design an algorithm for reversing two adjacent entries in one of the queues.

Answer 1

q1 = [1,2,3,4,5]
q2 = []

reverse 3,4

q1 = [2,3,4,5,1]
q2 = []

q1 = [3,4,5,1,2]
q2 = []

q1 = [4,5,1,2]
q2 = [3]

q1 = [5,1,2,4]
q2 = [3]

q1 = [5,1,2,4,3]
q2 = []

q1 = [1,2,4,3,5]
q2 = []

That's basically the algorithm. Rotate the queue where you want to reverse elements. When the first element of the two can be dequeued, take it and enqueue it on the other queue. Enqueue and dequeue the next element and put back the first element. If q2 was populated, you would need to rotate it once until you can deque the elemnt from q1. This wouldn't change thee state of q2 though.

Time complexity: O(n + m) where n and m are the number of elements in q1 and q2.

Space complexity: O(1)