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

#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")<<'\\';

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

return 0;

}

Step-by-step 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.