Answer to Question #239670 in C for kanha

Question

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

a. Push and Pop elements in the stack. b. Delete from the given Queue. 

c. Insert into another Queue.

Examples :

 Input : Queue[] = { 5, 1, 2, 3, 4 }; Output : Yes 

Delete the first element of the given Queue i.e 5. 

Push 5 into the stack. 

Now, Delete all the elements of the given Queue and Insert them into the second Queue. 

Now, pop element 5 from the stack and Insert it into the second Queue. 

  Input : Queue[] = { 5, 1, 2, 6, 3, 4 }; Output : No

Answer 1

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


bool checkIfQueue(int queue_size, queue<int>& queue1)
{
    stack<int> s;
    int ex = 1;
    int put_front;
 
    
    while (!queue1.empty()) {
        put_front = queue1.front();
        queue1.pop();
 
        
        if (put_front == ex)
            ex++;
 
        else {
            
            if (s.empty()) {
                s.push(put_front);
            }
 
            
            else if (!s.empty() && s.top() < put_front) {
                return false;
            }
 
           
            else
                s.push(put_front);
        }
 
        
        while (!s.empty() && s.top() == ex) {
            s.pop();
            ex++;
        }
    }
 
    
    if (ex - 1 == queue_size && s.empty())
        return true;
 
    return false;
}
 
// Testing code
int main()
{
	cout<<"The first queue\n";
   //First queue
    queue<int> first_que;
    first_que.push(5);
    first_que.push(1);
    first_que.push(2);
    first_que.push(3);
    first_que.push(4);
 
    int len = first_que.size();
 
    (checkIfQueue(len, first_que) ? (cout << "Yes\n") : (cout << "No\n "));
 
 
 cout<<"The second queue\n";
 
 queue<int> second_que;
 second_que.push(5);
 second_que.push(1);
 second_que.push(2);
 second_que.push(6);
 second_que.push(3);
 second_que.push(4);
 int len1 = second_que.size();
 
    (checkIfQueue(len1, second_que) ? (cout << "Yes\n") : (cout << "No\n "));
    return 0;
}