Datastructure with push(), pop() and min() in O(1)

A Stack is a last-in, first-out data structure. It provides push(), pop() and top() operations which can be performed in O(1) time. The push() and pop() operations occur only at one end of the stack. The top() operation returns the topmost element on the stack without deleting it.

Consider a stack of integers (may contain duplicates). To keep track of the running minimum, we can have a side stack. The topmost element on the side stack is the minimum element for the current stack instance. This requires a slight modification to the push() and pop() operations. Let us call the stacks 'numbers' and 'stack_min'.

A straight forward approach is to have a side stack which is of the same size as the original stack. While inserting an element 'num' onto the 'numbers' stack, the 'stack_min' is also updated by inserting 'num' or by duplicating the current minimum. While performing a pop(), the topmost elements on both the stacks are popped.

Consider an example to push elements 8, 4, 1, 3, 6, 1 onto the stack and pop them. The following shows both the stack contents at each step. The highlighted value on the 'stack_min' stack is the current minimum.

Operation             numbers                stack_min                             Comments

push(8)                 8                           8                                           first element

push(4)                 8 4                        8 4                                        num (4) < min (8)

push(1)                8 4 1                      8 4 1                                     num (1) < min (4)

push(3)                8 4 1 3                   8 4 1 1                                  duplicate 1;

                                                                                                       num(3) > min(1)

push(6)                8 4 1 3 6                8 4 1 1 1                               duplicate 1;

                                                                                                       num(6) > min(1)

push(1)                8 4 1 3 6 1             8 4 1 1 1 1                            insert 1;

                                                                                                       num(1) = min(1)

pop()                   8 4 1 3 6                8 4 1 1 1                                pop from both

pop()                   8 4 1 3                   8 4 1 1                                   pop from both

pop()                   8 4 1                      8 4 1                                      pop from both

pop()                   8 4                         8 4                                         pop from both

pop()                   8                            8                                            pop from both

This approach needs 2x the space required for a stack. To improve the average case space consumption, we can perform an insertion onto the 'stack_min' only when a 'num' which is <= the current minimum is encountered. Consider the same example with this change:

Operation           numbers                 stack_min                             Comments

push(8)               8                            8                                           first element

push(4)               8 4                         8 4                                        num (4) < min (8)

push(1)               8 4 1                      8 4 1                                     num (1) < min (4)

push(3)               8 4 1 3                   8 4 1                                     num(3) > min(1)

push(6)               8 4 1 3 6                8 4 1                                     num(6) > min(1)

push(1)               8 4 1 3 6 1             8 4 1 1                                  insert 1;

                                                                                                      num(1) = min(1)

pop()                  8 4 1 3 6                8 4 1                                      pop from both;

                                                                                                      num(1) = min(1)

pop()                  8 4 1 3                   8 4 1                                      num(6) > min(1)

pop()                  8 4 1                      8 4 1                                      num(3) > min(1)

pop()                  8 4                         8 4                                         pop from both;

                                                                                                      num(1) = min(1)

pop()                  8                            8                                            pop from both;

                                                                                                       num(4) = min(4)

For this version, here is the C++ code:

#include <stack>

class StackMinimum {

stack<int> numbers_;

stack<int> stack_min_;

public:

int GetMin() const {

return stack_min_.top();

}

int GetTopNumber() const {

return numbers_.top();

}

void PushNumber(int num); //modified push() operation

int PopNumber(); //modified pop() operation

};

void StackMinimum::PushNumber(int num) {

numbers_.push(num);

if(stack_min_.empty() || num <= GetMin()) {

stack_min_.push(num);

}

}

int StackMinimum::PopNumber() {

if(numbers_.empty()) {

return -1;

}

int num = GetTopNumber();

numbers_.pop();

if(num == GetMin()) {

stack_min_.pop();

}

return num;

}

At each point, the minimum value can be got by performing a top() operation on the 'stack_min' stack, which takes O(1) time. The worst case space complexity is still 2x the normal stack – still O(n).