Each element in the stack will contain not only its own value, but the
min value at that depth of the stack:
struct stackItemStruct
{
int value;
int min;
struct stackItemStruct *next;
};
typedef struct stackItemStruct stackItem;
class stack
{
public:
stack();
void push(int v);
int pop();
int min();
private:
stackItem *_stack;
};
stack::stack()
{
_stack = 0;
}
void stack::push(int v)
{
stackItem newItem = new stackItem;
newItem->value = newItem->min = v;
if (_stack && (_stack->min < v) )
newItem->min = _stack->min;
newItem->next = _stack;
_stack = newItem;
}
int stack::pop()
{
int result = 0;
if (_stack)
{
result = _stack->val;
stackItem *tmp = _stack;
_stack = tmp->next;
delete tmp;
}
return result;
}
int stack::min()
{
return _stack ? _stack->min : 0;
}
On Sep 4, 12:08 pm, Sangeeta <[email protected]> wrote:
> How would you design a stack which,in addition to push and pop,also
> has a function min which returns the minimum element?push,pop and min
> should all operate in O(1) time
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
