-2

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
  • Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question.
    – gnat
    Jul 31, 2014 at 11:08
  • you may want to ask about a specific part of a solution you don't understand
    – jk.
    Jul 31, 2014 at 11:14

1 Answer 1

0

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

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