Comment on page
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 modified 4yr ago