Max Stack
Implement a stack that is able to return the maximum of the stack at any moment. All operations must be O(1), or amortized O(1) on the push operation.
The Idea:
We maintain a secondary stack, that which we will call MaxStack. It is a special kind of stack, so it should have very similar methods, with a few exceptions.
We will encapsulate a regular stack, that will be used to maintain the
MaxStack
ordinary operators likepush
,pop
,top
.MaxStack
will interface with another stack we will callmax_s
that overwrites a few operators.push
will add the new integer to max stack iff it exceeds the current size of its current max. This has the effect of maintaining a history of the max elements pushed in.So when we
pop
we will naturally obtain the previous max element that will always be inline with the ordinary stack, since we pop from both containers.
class Stack
{
public:
Stack(const size_t n) {
s.reserve(n);
iter = 0;
}
Stack() { iter = 0; }
void reserve(const size_t n) { s.reserve(n); }
virtual bool empty() { return iter == 0; }
int top()
{
if (!empty()) return (s.at(iter - 1));
else throw "empty";
}
virtual void push(const int n)
{
if (iter >= s.size()) {
s.push_back(n);
iter++;
}
else s.at(iter++) = n;
}
virtual void pop()
{
if (!empty()) iter--;
else throw "empty";
}
private:
vector<int> s;
int iter;
};
class MaxStack : public Stack
{
public:
MaxStack(const size_t size) {
Stack::reserve(size);
max_s.reserve(size);
iter = 0;
}
void push(const int n)
{
Stack::push(n);
if (empty()) max_s.push(n);
else if (!empty() && n < max_s.top()) {
max_s.push(max_s.top());
}
else max_s.push(n);
iter++;
}
void pop()
{
if (!empty()) {
Stack::pop();
max_s.pop();
iter--;
}
else throw "empty";
}
int max()
{
if (!empty())
return max_s.top();
else throw "empty";
}
bool empty() { return iter == 0; }
private:
Stack max_s;
int iter;
};
int main()
{
cout << "ascending" << endl;
MaxStack s(30);
vector<int> elements = {1,2,3,4,5,6,7,8,9,9,9};
for (int i : elements) {
s.push(i);
cout << s.max() << " ";
}
cout << "\n\n";
try
{
while (!s.empty()) {
s.pop();
cout << s.max() << " ";
}
}
catch (const char* msg) {
cerr << msg << endl;
}
cout << "\n\n\n";
cout << "descending" << endl;
MaxStack s2(30);
vector<int> elements2 = { 9,9,9,8,7,6,5,4,3,2,1 };
for (int i : elements2) {
s2.push(i);
cout << s2.max() << " ";
}
cout << "\n\n";
try
{
while (!s2.empty()) {
s2.pop();
cout << s2.max() << " ";
}
}
catch (const char* msg) {
cerr << msg << endl;
}
}
output
ascending
1 2 3 4 5 6 7 8 9 9 9
9 9 8 7 6 5 4 3 2 1 empty
descending
9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 empty
Last updated
Was this helpful?