Careercup 3.2 - How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. 1. how to use stack in STL; 2. how to throw an exception;

careercup3.2

#include <iostream>
#include <stack>

using namespace std;

class MyException{
 public:
  MyException(){cout << "the stack is empty" << endl;}
};

class Stackmin{
private:
  stack<int> s1;
	stack<int> s2;
	int min;


public:
	Stackmin(){
		min = 0;
	}

	void push(int val){
		if(val<min||s1.empty()) min = val;
		s2.push(min);
		s1.push(val);
	}

	int top(){
		if(!s1.empty())
			return s1.top();
		throw MyException();
	}

	int top_min(){
		if(!s2.empty())
			return s2.top();
	    throw MyException();

	}

	void pop(){
		if(!s1.empty()&&!s2.empty()){
			s1.pop();
			s2.pop();
		}
	}
};

int main(){
	Stackmin s;
	s.push(3);
	s.push(5);
	s.push(2);
	s.push(100);
	s.push(1000);
	s.push(19);
	for(int i = 0;i<7;i++){
		cout << s.top() << " " << s.top_min() << endl;
		s.pop();
	}
	return 0;
}