Question

For exam review:

Given a stack S1 with n numbers and an empty stack S2, design an algorithm (and write psudeocode for it) to sort all the numbers (from small on top to large on bottom) and store them in the originally empty stack S2, using only the stack ADT functions with the two given stacks, and a fixed number (independent of n) of int and char variables. What is the time complexity of your algorithm (related to n) in the BEST/WORST case?

Answer 1

The worst case time-complexity is O(n).

Code:

#include <bits/stdc++.h>
using namespace std;

// method to sort stack
stack<int> sort(stack<int> &st1)
{
   stack<int> st2;

   while (!st1.empty())
   {
  
       int tmp = st1.top();
       st1.pop();

   // untill st2 is not empty and top is larger than temp value
       while (!st2.empty() && st2.top() > tmp)
       {
      
       //pop from st2 and push to st1
           st1.push(st2.top());
           st2.pop();
       }

  
       st2.push(tmp);
   }

   return st2;
}

int main()
{
// main method to test sorting of stack
// intialize stack 1 and push elements to it
   stack<int> st1;
   st1.push(7);
   st1.push(3);
   st1.push(4);
   st1.push(9);
   st1.push(2);
   st1.push(5);

   // call method to sort stack and store return value in another stack
   stack<int> st2 = sort(st1);
   cout << "Sorted stack values are:\n";

   while (!st2.empty())
   {
   // display the values
       cout << st2.top()<< " ";
       st2.pop();
   }
}

Screenshots:

Output: