Last Updated on December 14, 2022 by Prepbytes
Problem statement
Given a queue having N numbers . Numbers in the queue is a permutation of first N natural numbers (1 to N) . You have to find out whether this queue can be sorted in increasing order in another queue using a single stack following the below constraints :
 Only pop is allowed on the first queue
 Only push is allowed on the second queue
 Push and pop both is allowed on the stack
 Only one stack can be used , and recursion is not allowed
Examples :
Sample input : Queue => {5 , 4 , 1 , 2 , 3}
Sample output: YES
Explanation : push 5 and 4 into the stack from the first queue .
push 1 , 2 , 3 into the second queue .
pop stack elements and push 4 and 5 into the second queue .
Sample input : Queue => {1, 5, 3,4,2}
Sample output: NO
Sample input : Queue => {5 , 1, 3 , 2 , 4}
Sample output: YES
Approach
Given queue is a permutation of first N natural numbers i.e it contains all numbers from 1 to N exactly once . So if it is possible to sort these numbers into another queue then we already know that our second queue will look like {1 , 2 , 3, ….. , N1 , N} . So we need to push first 1 , then next 2 , next 3 and so on . If we are not able to push numbers in this order , then it is not possible to sort the queue .
If the front of the queue is not the required next number that we want to push into the second queue , then we will push it into the stack temporarily . At the end ,our stack should also be in monotonic decreasing order .
Algorithm for sorting a queue into another queue using a stack

Let us first create a req_next variable and initialize it to 1. This req_next variable denotes what is the next number that we require to push into the stack .

If the front of the given queue is the same as req_next , pop it from the queue and push it into the second queue and increment the req_next.

If the top of the stack is the same as req_next , pop it from the stack and push it into the second queue and increment the req_next.

If none of the above conditions is true , then we need to pop the front of the given queue and push into the stack .

Keep repeating 2 – 4 until the given queue is empty .

Now we will pop each element from the stack
 If the top of the stack is the same as req_next , pop it from the stack and push it into the second queue and increment the req_next.
 Else print “No” , because it is not possible to sort the queue into another queue

If we have successfully pushed all N elements into the second queue , then print “YES” because we sorted the given queue into another queue using a single stack .
Dry run for the above algorithm
#include <bits/stdc++.h> using namespace std; // Check If A Queue Can Be Sorted Into Another Queue Using a Single stack bool checkIfAQueueCanBeSorted(queue<int> &q){ stack<int> st; int req_next=1; // queue<int> q2; while(!q.empty()){ if(q.front() == req_next){ // q2.push(q.front()); q.pop(); req_next++; } else if(!st.empty() && st.top() == req_next){ // q2.push(st.top(); st.pop(); req_next++; } else{ st.push(q.front()); q.pop(); } } while(!st.empty()){ if(st.top() == req_next){ // q2.push(st.top()); st.pop(); req_next++; } else{ return false; } } return true; } int main() { queue<int> q1; q1.push(5); q1.push(1); q1.push(3); q1.push(2); q1.push(4); if(checkIfAQueueCanBeSorted(q1)){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; queue<int> q2; q2.push(1); q2.push(5); q2.push(3); q2.push(4); q2.push(2); if(checkIfAQueueCanBeSorted(q2)){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; return 0; }
Time complexity : O(N)
Space complexity : O(N)
This article tried to discuss How to Check if a queue can be sorted into another queue using a stack. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE  Competitive Programming at Prepbytes.