easy way to create a Max stack in cpp using stl:
(same idea for Min Stack)
stack<pair<int,int>> s;
insert:
/* new max will be given no. if stack is empty else we compare given no. to max at current top of stack*/
int new_max=s.empty()?given_element : max(given_element,s.top().second);
// we push the pair of given_element,new_max in s
s.push({given_element,new_max});
pop:
if (!s.smpty()){
// popped has popped number
int popped=s.top().first;
s.pop();
}
else{
// print a mesage or throw exception etc
}
max:
int maximum_elem=s.top().second;
.
.
and since all operations of stack are O(1) and .first and .second of pair is also O(1)
every operation above of Max Stack is O(1)
and we are storing just pairs of numbers so ofcourse it's O(1) space.