What will be the data structure in the next scenario? (Max stack)
Please note that there is no memory limit. I need to insert an int from 1 to 1000.
I can perform each of the following operations in a constant order of time:
- push (): adds to the beginning
- pop (): removes the top element
- getMax (): returns the max element
Please suggest me a suitable data structure.
source to share
Since there is no memory limit, I will be using 2 vectors - one for the actual data on the stack and the other for keeping track of the max in each state of the stack.
For simplicity's sake, I'll assume this stack contains only + ve ints.
I know this is not error checking. But I'm just suggesting the data structure idea here, not a complete solution.
class StackWithMax
{
public:
StackWithMax() : top(-1), currentMax(0) { }
void push(int x);
int pop();
int getMax() { return m[top]; }
private:
vector<int> v; // to store the actual elements
vector<int> m; // to store the max element at each state
int top;
int currentMax;
};
void StackWithMax::push(int x)
{
v[++top] = x;
m[top] = max(x, currentMax);
}
int StackWithMax::pop()
{
int x = v[top--];
currentMax = m[top];
return x;
}
source to share
Use a standard stack structure and an optional array for counters
int c[1..1000]
and variable int maxVal=0
.
In the code, add actions after the stack operations:
On push(x) -> c[x]++ ; maxVal = max(x,maxVal)
On pop():x -> c[x]-- ; if (c[x] == 0) { j=x; while(c[--j] == 0); maxVal = j; }
maxVal should always be at the maximum value.
I may be wrong, this should have amortized the computational complexity of O (1). It has been a long time since I analyzed the algorithms.
source to share