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 <sangeeta15...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.