Answer to Question #239585 in C for Neelam

Question

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operations allowed are:

1. Push and Pop elements in the stack
2. Delete from the given Queue.
3. Insert into another Queue.

Answer 1

#include <iostream>
#include<stack>
#include<queue>
using namespace std;


bool checkIfCanSorted(int size_n, queue<int>& que)
{
    stack<int> stack1;
    int x = 1;
    int temp;
 
    
    while (!que.empty()) {
        temp = que.front();
        que.pop();
 
        
        if (temp == x)
            x++;
 
        else {
            
            if (stack1.empty()) {
                stack1.push(temp);
            }
 
            
            else if (!stack1.empty() && stack1.top() < temp) {
                return false;
            }
 
           
            else
                stack1.push(temp);
        }
 
        
        while (!stack1.empty() && stack1.top() == x) {
            stack1.pop();
            x++;
        }
    }
 
    
    if (x - 1 == size_n && stack1.empty())
        return true;
 
    return false;
}
 
// Testing code
int main()
{
    queue<int> que;
    que.push(5);
    que.push(1);
    que.push(2);
    que.push(3);
    que.push(4);
 
    int que_size = que.size();
 
    (checkIfCanSorted(que_size, que) ? (cout << "Yes, it is possible to arrange elements of the queue") : (cout << "No, Queue elements cannot be arranged "));
 
    return 0;
}