In the stack example program add a method called searchchar

In the stack example program, add a method called search(char item) that performs searching algorithm on a stack. To search for an item in a stack, the searched item can only be compared with the item on the top of the stack. If the item on the top of the stack is NOT the searched item, it must be popped off the stack so that the item underneath it can be used to compare with the searched item. After the searching is done, the removed item(s) must be pushed back to the stack to remain original stack again. Sample method\'s calls in main and its output: int main() {push(\'H\'); push(\'A\'); push(\'T\'); displayStack(); search(\'H\'); displayStack(); cout

Solution

Hi Friend, YOu have not posted whole progtam of stack implementation, so I do not have clear unserstanding of all methods implementation.

But I have implemented:

// search method implementation

void search(char c){
  
   // if stack is empty
   if(empty()){
       cout<<c<<\" not avaialble in stack\"<<endl;
       return;
   }

   // getting top element
   char t = pop(); // getting top element
   if(t == c){
       cout<<c<<\" is now found at top\"<<endl;
       push(t); // push again popped element in stack
       return;
   }
      
   search(c); // calling search recursively
  
   // now popped element back to stack
   push(t);

}

Time Complexity: Worst case scenario occurs when \'c\' is available at bottom of stack or \'c\' is not in stack

In this case we need to pop all elements and again we need to push in stack

So, if N is the total number of elements in stack then It takes : O(2*N) = O(N)