Sorting a queue with another queue

I dont think the naive implementation would work. It's a queue, so you cant remove the smallest element if it is not at the end of the queue.

The only way I can think of is: Keep the 2nd queue sorted always. 1. Delete element from q1. 2. If this element >= last element of q2, then insert it into q2. (That way q2 is still sorted). 3. Else, insert it back to q1. Keep repeating the above steps till q1 is empty.

my algo :

 let the Q size = n, 
 1 save = getRearValue(1stQ)
 2 pop the element from 1st Q and insert it into 2nd Q.
 3 if getFrontValue(1stQ) > getRearValue(2ndQ)  
 4        then goto step 2.
 5 else 
 6        pop the element from 1st Q and insert back into the same Q (1st Q). 
 7        if (save != getRearValue(1stQ)) goto step 3.
 8 if (1st Q not sorted OR getFrontValue(1stQ) > getFrontValue(2ndQ))
 9          then 
 10          pop all elements of 2nd Q and insert into 1st Q (One by one).
 11          goto step 1.
 12 else
 13     pop all elements of 2nd Q and insert into 1st Q (One by one).
 14     return 1stQ

Here's a method I think might work :-

The algorithm uses Recursion to sort the queue.

Assume we have a function copy_from that can copy from one queue over to another queue as follows :-

void copy_from (ArrayQueue&Q_from,ArrayQueue& Q_to){

     while(!Q_from.empty()){

        int t= Q_from.front();
        Q_to.enqueue(t);
        Q_from.dequeue();
     }

}   

The main sort function is as shown :-

    void sort(ArrayQueue &Q, int element, ArrayQueue&Q2){

if(Q.size()==1){

    if(Q.front()>element){

         int front = Q.front();
         Q.dequeue();
         Q.enqueue(element);
         Q.enqueue(front);      
    }
    else{
        Q.enqueue(element);
    }

}
else{

 int front = Q.front();
 Q.dequeue();
 sort(Q,front); // sort the remaining queue.

 int sorted_front = Q.front(); //get front element of sorted queue
 if(element<sorted_front){

    Q2.enqueue(element);
    copy_from(Q,Q2);
    copy_from(Q2,Q);     

 }
 else{
    // dequeue all elements from the queue which are lesser than element and put it into new queue.
    // Then enqueue the new element
    // Then enqueue whatevers bigger than element into the queue.

      Q2.enqueue(sorted_front);
      Q.dequeue();

      while(!Q.empty()&&Q.front()<element){
         Q2.enqueue(Q.front());
         Q.dequeue();
      }

      Q2.enqueue(element);
      copy_from(Q,Q2);
      copy_from(Q2,Q);

 }

}
}

When we initially call the sort function, we can call it as follows :-

Queue Q, Q2;

 int front = Q.front();
 Q.dequeue();
 sort(Q,front,Q2);

If we had input as 6->4->9>2->1, the result would be 9->6->4->2->1.

Here is a simple logic that I came up with from the top of my head. The worst-case run time will be O(N^2) while ideally the best case can be O(N). I think the complexity can be further reduced with an improvised logic.

The syntax is Javascript but is well commented to be self-explanatory.

I hope this helps.

// SORT A QUEUE USING ANOTHER QUEUE
function sortQueueUsingQueue(uq) {
    // instantiate required variables
    var sq = new Queue();
    var t = null, last = null;
    // copy the items to a temp queue
    // so as not to destroy the original queue
    var tq = new Queue(uq);
    // loop until input is not empty
    while(!tq.isEmpty()) {
        t = tq.dequeue();
        if (last && last <= t) {
            // new element will be at the end of the queue, and we don't have to
            // process any further - short-circuit scenario
            // this is the best case scenario, constant time operation per new item
            sq.enqueue(t);
            // also keep track of the last item in the queue,
            // which in this case is the new item
            last = t;
        } else {
            // other scenario: linear time operation per new item
            // new element will be somewhere in the middle (or beginning) so,
            // take elements from the beginning which are less or equal to new item,
            // and put them at the back
            while(!sq.isEmpty() && sq.peek() <= t) {
                sq.enqueue(sq.dequeue());
            }
            // when that is done, now put the new element into the queue,
            // i.e the insertion into the proper place
            sq.enqueue(t);
            // following which, shift the rest elements to the back of the queue,
            // to reconstruct the sorted order,
            // thus always keeping the second queue sorted per insertion
            while(sq.peek() > t) {
                // meanwhile, also keep a track of the last (highest) item in the queue
                // so that we may perform a short-circuit if permitted
                last = sq.dequeue();
                sq.enqueue(last);
            }
        }

    }
    return sq;
}

You can view the entire working code as a github gist here: https://gist.github.com/abhishekcghosh/049b50b22e92fefc5124

static void sort(Queue<Integer> input) {
        Queue<Integer> tempQueue = new LinkedList<>();

        while (!input.isEmpty()) {
            int temp = input.remove();
            if (!tempQueue.isEmpty()) {
                if (temp < tempQueue.peek()) {
                    int n = tempQueue.size();
                    tempQueue.add(temp);
                    for (int i = 0; i < n; i++) {
                        tempQueue.add(tempQueue.remove());
                    }
                } else {
                    int n = tempQueue.size();
                    int i = 0;
                    while (i < n) {
                        if (temp > tempQueue.peek()) {
                            tempQueue.add(tempQueue.remove());
                        } else {
                            tempQueue.add(temp);
                            for (int j = i; j < n; j++) {
                                tempQueue.add(tempQueue.remove());
                            }
                            break;
                        }
                        i++;
                    }
                    if (i == n) {
                        tempQueue.add(temp);
                    }
                }
            } else {
                tempQueue.add(temp);
            }

        }
        System.out.println(tempQueue);
    }

We can do this using the below steps:

1. We got an extra queue here that we can make use of it for our algorithm. Let’s use the extra queue to hold only sorted values.
2. So, if an element which is polled/dequeued from the queue (front element) is less than the element which we just enqueued in the extra queue, then above statement step 1 is broken, so we just poll/dequeue the front element from the queue and add it back to the same queue.
3. Once all the elements in the queue are processed by using the above two steps, then we dequeue all sorted elements from the extra queue and add them back to the original queue.
4. The queue is not sorted until the given queue and the extra queue is not equal in size. So we do start from step 1 and repeat the algorithm.

Refer to the code here https://zingscoop.com/coding-challenge-sorting-a-queue-with-another-queue/