Sorting sequences
A group of students wishes to separate a set of numbers into two sorted lists using stacks and queues. The steps of the developed algorithm are as follows:
Let there be an empty queue, say Q, and an empty stack, say S.
If Q is empty and S is empty, then enqueue the first element x into Q.
For the insertion of each element x (other than first element), the following sequential process is designed.
If element x is greater than or equals to the rear element in Q, then enqueue it in Q.
Else if S is empty or element x is less than or equals to the top element in S, then push it in S.
Else
Pop all the elements from S and enqueue in Q using the steps as given below:
If top element of S is less than front element of Q, then pop from S and enqueue in Q.
Else if top element of S is greater than all the elements in Q and Q has elements in non-decreasing order, then pop from S and enqueue in Q.
Else if top element of S is equal to the rear element in Q, then pop from S and enqueue in Q.
Else dequeue from Q and enqueue in Q.
Dequeue from Q and enqueue in Q till the front element of Q is less than the element x.
Dequeue from Q and push in S.
Push the element x in S.
Dequeue from Q and enqueue in Q till the front element of Q is greater than equals to the rear element in Q.
Finally the contents of Q and S give the required sorted lists.
Input:
Line 1 contains an integer N.
Line 2 contains space separated N integers to be sorted.
Output:
Show the contents of Q and S (in separate lines) after each insertion. Nothing will be displayed if Q or S is empty.
Constraint:
All integers range in between 1 and 1000.
Sample Input I:
5
3 1 7 1 2
Sample Output I:
3
3
1
3 7
1
3 7
1 1
1 1 7
2 3
EXPLANATION I:
Insert 3. Q and S both are empty.
Queue: (front) 3 (rear)
Insert 1. 1 is less than the rear element in Q, i.e. 3. But S is empty, so push 1 in S.
Queue: (front) 3 (rear)
Stack: (top) 1
Insert 7. 7 is greater than the rear element in Q, i.e. 3, so enqueue 7 in Q.
Queue: (front) 3 7 (rear)
Stack: (top) 1
Insert 1. 1 is less than the rear element in Q, i.e. 7. But 1 equals to the top element in S, i.e. 1, so push 1 in S.
Queue: (front) 3 7 (rear)
Stack: (top) 1 1
Insert 2. 2 is less than the rear element in Q, i.e. 7. Also 2 is greater than the top element in S, i.e. 1.
So all the elements are popped from S and enqueued in Q.
1 is less than 3. So Queue will be ‘(front) 3 7 1 (rear)’ and Stack will be ‘1’.
1 is less than 3. So Queue will be ‘(front) 3 7 1 1 (rear)’ and Stack will be empty.
If front of Q is less than the element x, then dequeue from Q and enqueue in Q.
3 is greater than 2. So Queue will be ‘(front) 3 7 1 1 (rear)’ and Stack will be empty. No change.
Dequeue from Q and push in S. So Queue will be ‘(front) 7 1 1 (rear)’ and Stack will be ‘3’.
Push the element x in S.
So Queue will be ‘(front) 7 1 1 (rear)’ and Stack will be ‘(top) 2 3’.
If front of Q is greater than the rear element in Q, then dequeue from Q and enqueue in Q.
7 is greater than 1. So Queue will be ‘(front) 1 1 7 (rear)’ and Stack will be ‘(top) 2 3’.
Therefore the output will be
Queue: (front) 1 1 7 (rear)
Stack: (top) 2 3
Sample Input II:
8
1 4 3 5 8 7 2 6
Sample Output II:
1
1 4
1 4
3
1 4 5
3
1 4 5 8
3
1 3 4 5
7 8
1 3 4 5
2 7 8
1 3 4 5 6
2 7 8
EXPLANATION II:
Insert 1. Q and S both are empty.
Queue: (front) 1 (rear)
Insert 4. 4 is greater than the rear element in Q, i.e. 1, so enqueue 4 in Q.
Queue: (front) 1 4 (rear)
Insert 3. 3 is less than the rear element in Q, i.e. 4. But S is empty, so push 3 in S.
Queue: (front) 1 4 (rear)
Stack: (top) 3
Insert 5. 5 is greater than the rear element in Q, i.e. 4, so enqueue 5 in Q.
Queue: (front) 1 4 5 (rear)
Stack: (top) 3
Insert 8. 8 is greater than the rear element in Q, i.e. 5, so enqueue 8 in Q.
Queue: (front) 1 4 5 8 (rear)
Stack: (top) 3
Insert 7. 7 is less than the rear element in Q, i.e. 8. Also 7 is greater than the top element in S, i.e. 3.
So all the elements are popped from S and enqueued in Q.
3 is greater than 1. So Queue will be ‘(front) 4 5 8 1 (rear)’ and Stack will be ‘(top) 3’.
3 is less than 4. So Queue will be ‘(front) 4 5 8 1 3 (rear)’ and Stack will be empty.
If front of Q is less than the element x, then dequeue from Q and enqueue in Q.
4 is less than 7. So Queue will be ‘(front) 5 8 1 3 4 (rear)’ and Stack will be empty.
5 is less than 7. So Queue will be ‘(front) 8 1 3 4 5 (rear)’ and Stack will be empty.
Dequeue from Q and push in S. So Queue will be ‘(front) 1 3 4 5 (rear)’ and Stack will be ‘8’.
Push the element x in S.
So Queue will be ‘(front) 1 3 4 5 (rear)’ and Stack will be ‘(top) 7 8’.
If front of Q is greater than the rear element in Q, then dequeue from Q and enqueue in Q.
1 is less than 5. So Queue will be ‘(front) 1 3 4 5 (rear)’ and Stack will be ‘(top) 7 8’. No change.
Therefore the output will be
Queue: (front) 1 3 4 5 (rear)
Stack: (top) 7 8
Insert 2. 2 is less than the rear element in Q, i.e. 5. But 2 is less than the top element in S, i.e. 7, so push 2 in S.
Queue: (front) 1 3 4 5 (rear)
Stack: (top) 2 7 8
Insert 6. 6 is greater than the rear element in Q, i.e. 5, so enqueue 6 in Q.
Queue: (front) 1 3 4 5 6 (rear)
Stack: (top) 2 7 8
