# Check If A Queue Can Be Sorted Into Another Queue Using A Stack ### 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, ….. , N-1 , 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

1. 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 .

2. 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.

3. 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.

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

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

6. 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
7. 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.