CC150 3.2

3_2.cpp

/* CC150 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.
 */

#include <iostream>
#include <stack>

using namespace std;

class myStack {
public:
	void push(int data);
	void pop();
	int top() { return s.top(); }
	int min() { return s.empty() ? 65535 : minValue.top(); } // return current minimum
	bool empty() { return s.empty(); }
private:
	stack<int> s;
	stack<int> minValue;
};

void myStack::push(int data) // push into minValue when new data is smaller than or equal to current minimum
{
	if (data <= min())
		minValue.push(data);
	s.push(data);
}

void myStack::pop() // pop from minValue if the popped-out value was current minimum
{
	if (s.empty()) {
		cerr << "Empty stack!" << endl;
		return;
	}
	if (s.top() == min())
		minValue.pop();
	s.pop();
}

int main()
{
	myStack s;
	s.push(5); // min = 5
	cout << "Minimum value is " << s.min() << endl;
	s.push(6); // min = 5
	cout << "Minimum value is " << s.min() << endl;
	s.push(3); // min = 3
	cout << "Minimum value is " << s.min() << endl;
	s.push(7); // min = 3
	cout << "Minimum value is " << s.min() << endl;
	s.pop(); // min = 3
	cout << "Minimum value is " << s.min() << endl;
	s.pop(); // min = 5
	cout << "Minimum value is " << s.min() << endl;
	return 0;
}