Don's solution is correct.
At each push() operation, you update the value of min element upto that
depth in stack.
Can be illustrated with the following example -
stack = {}
push(2) stack = {(2,2)}
push(3) stack = {(3,2),(2,2)}
push(1) stack = {(1,1),(3,2),(2,2)}
where b in tuple (a,b) represents the min value upto current depth in stack.
pop() and min() are straight forward.
On Mon, Sep 5, 2011 at 12:48 AM, Don <[email protected]> wrote:
> 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.
>
>
--
Nitin Garg
"Personality can open doors... but only Character can keep them open"
--
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.
