Question

Suppose you have a stack S containing n elements and a queue Q that is initially empty. Write a program in which you can use Q to scan S to see if it contains a certain element x, with the additional constraint that your algorithm must return the elements back to S in their original order. You may only use S, Q, and a constant number of other primitive variables

Answer 1

JAVA PROGRAM

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackQueue {
  
   public static void main(String[] args){
      
       //instantiate a stack of Integers S
       Stack<Integer> S = new Stack<Integer>();
       final int n = 10; //define n as 10
      
       //push 10 random integers into S
       //random integers can be anything between 0 to 25(exclusive)
       for(int i = 1; i <= n; i++){
           S.push((int)(Math.random()*25));
       }
       System.out.println("Initial contents of stack (bottom to top):");
       System.out.println(S);
       System.out.println("stack top is="+S.peek());
      
       int x = (int)(Math.random()*25); //x is the element to find in stack
       System.out.println("x (the element to scan) is "+x);
      
       //Instantiate Queue Q
       Queue<Integer> Q = new LinkedList<Integer>();
      
       //run while loop as long as stack is not empty
       while(!S.isEmpty()){
           if(S.peek() == x){//if x is found in Stack
               System.out.println(x+" is Found");//print that it is found
               break;//break out of loop
           }else{
               //otherwise add the stack popped item into queue
               Q.add(S.pop());
           }
       }
      
       if(S.isEmpty()){
           System.out.println(x+" is NOT Found");//print that it is found
       }
      
      
       //reverse the queue elements
       Q = reverseTheQ(Q);
      
       //push the elements from Q into S
       //in original order of S
       while(!Q.isEmpty()){
           S.push(Q.remove());
       }
      
       System.out.println("After scanning the stack now contains: "+S);
       System.out.println("Stack top is =>"+S.peek());  
      
   }
  
   //reverse the contenet s of queue using recusrsion
   private static Queue<Integer> reverseTheQ(Queue<Integer> theQ){
       if(theQ.isEmpty()){//if queue is empty
           return theQ; //the base criteria of the recursion function
       }
      
       int value = theQ.remove();//get and remove the front element of queue
      
       theQ= reverseTheQ(theQ); //now call the reverseTheQ on remaining queue elements
      
       //add the value at rear end of reversed Q
       theQ.add(value);
       //return
       return theQ;
   }

}

=================================

OUTPUT

=================================

RUN1

Initial contents of stack (bottom to top):
[15, 21, 20, 22, 13, 6, 7, 22, 12, 24]
stack top is=24
x (the element to scan) is 1
1 is NOT Found
After scanning the stack now contains: [15, 21, 20, 22, 13, 6, 7, 22, 12, 24]
Stack top is =>24

RUN2

Initial contents of stack (bottom to top):
[8, 8, 15, 1, 2, 11, 11, 18, 14, 20]
stack top is=20
x (the element to scan) is 13
13 is NOT Found
After scanning the stack now contains: [8, 8, 15, 1, 2, 11, 11, 18, 14, 20]
Stack top is =>20

RUN3

Initial contents of stack (bottom to top):
[10, 11, 15, 14, 22, 24, 20, 0, 17, 24]
stack top is=24
x (the element to scan) is 14
14 is Found
After scanning the stack now contains: [10, 11, 15, 14, 22, 24, 20, 0, 17, 24]
Stack top is =>24

please likemy answer THANK YOU!