[Stacks and Queues] interview questions #5

[rygh4775]

Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

[RoyMoon]

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class MinStack {
  stack<int> st; 
  stack<int> st_tmp;
  public:
  void push(int val) {
    while(st.empty() == false) {
      auto peekValue = st.top();
      if(peekValue < val) {
        st.pop();
        st_tmp.push(peekValue);
      } else { break; }
    };
    st.push(val);
    while(st_tmp.empty() == false) {
      auto tmp = st_tmp.top();
      st_tmp.pop();
      st.push(tmp);
    };
  }

  void pop(){
    st.pop();
  }

  int peek() {
    return st.top();
  }
  int empty() {
    return st.empty();
  }
};

int main()
{
  auto st = new MinStack(); 
  vector<int> list={2,4,1,5};

  for(auto n : list) {
    st->push(n);
    cout << "top stack " << st->peek() << endl;
  }

  while(st->empty() == false) {
    cout << "top stack " << st->peek() << endl;
    st->pop();
  };

  return 0;
}