You are given 2 queues, Q1 and Q2. Q1 is already filled with n elements. Q2 is empty
You have to reverse all the elements in Q1.
You cannot use any other space apart from Q2.
only operations permitted would be Q.enqueue() and Q.dequeue()
Time complexity – O(nlogn)
i found this question on a less popular website. http://www.questiondiscussion.com/questions/64/questiondiscussionchallenge-reverse-a-queue-using-an-extra-queue
few answers are also there. i am not able to understand the solutions, can anyone help me with is question ?
2
q1 has n elements
do
for n-1 elements in q1
take the first element out of q1 (dequeue) and add it to the end (enqueue) q1.Enqueue(q1.Dequeue)
when n-1 elements have been processed (the last element in q1 is next out)
q2.Enqueue(q1.Dequeue) – move it to q2
loop until q1 is empty
In vb it looks like this
Dim q1 As New Queue(Of Integer)
Dim q2 As New Queue(Of Integer)
'add some elements
For x As Integer = 1 To 5
q1.Enqueue(x)
Next
Do While q1.Count > 0 'while q1 has elements
For x As Integer = 1 To q1.Count - 1 'move last to first
q1.Enqueue(q1.Dequeue)
Next
q2.Enqueue(q1.Dequeue) 'move it to q2
Loop