Question

Describe how to scan a stack S containing to see if it contains a particular value x using only a queue Q and a constant number of reference variables. The stack contains n values and Q is initially empty. When the process finishes, the elements of S must be in their original order. [Preferred Language in C++]

Answer 1

Answer:

#include <iostream>

#include <stack>

#include <queue>

using namespace std;

bool checkfor(stack<int> &stk, int x){

 

   queue<int> q;

   bool flag = false;

   while(!stk.empty()){

       int p = stk.top();

       stk.pop();

       if(p == x){

           flag = true;

       }

       q.push(p);

   }

 

   while(!q.empty()){

       stk.push(q.front());

       q.pop();

   }

   while(!stk.empty()){

       q.push(stk.top());

       stk.pop();

   }

 

   // from queue to stack

   while(!q.empty()){

       stk.push(q.front());

       q.pop();

   }

 

   return flag;

 

}

int main(){

 

   stack<int> stk;

   // pushing data to stack

   stk.push(1);

   stk.push(3);

   stk.push(43);

   stk.push(2);

   stk.push(5);

 

   cout<<(checkfor(stk, 5)?"Found": "Not Found")<<'\n';

   cout<<(checkfor(stk, 10)?"Found": "Not Found")<<'\n';

 

   return 0;

}

Explanation:

• Check the top of stack for relevant value and insert that into queue.
• Take value from front of queue and push it to stack after the stack is empty.
• Now empty queue and push values to stack.