It' similar to implement min in O(1) in stack.
http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1
suppose you have implemented stack through linked list.
you can maintain another stack in parallel (say midstack)where you
keep the pointer of middle element for corresponding element in
main_stack, you will have to maintain a counter starting from 0 while
pushing elements (you can do it through a static variable or global
variable or just pass a parameter), if counter=2 then push [middle
here is top element in midstack] middle->next in midstack
corresponding to that position and reset the counter, else if counter
=1 just push the value at top of midstack again.
// pseudo code
push function:
main_stack.push(element);
counter++;
if (counter==2)
if (midstack.peek()!=NULL)
midstack.push(midstack.peek()->next);
else
midstack.push(head_of_main_stack); // initial condition.
counter=0;
else
midstack.push(midstack.peek());
pop function can be implemented on similar lines.
On Wed, May 22, 2013 at 9:37 PM, MAC <macatad...@gmail.com> wrote:
> i meant the middle elemnt
>
> so if 1 ,2,3 <--top then 2 is mid value /..
>
>
> accessing a middle element via the index is not right as it would mean you
> are not using it as a stack , but as an array ..
>
> thanks
> --mac
>
>
> On Wed, May 22, 2013 at 9:34 PM, Don <dondod...@gmail.com> wrote:
>>
>> Do you mean the middle position or median value?
>>
>> If you implement the stack in an array, finding the middle position
>> should be easy.
>>
>> Don
>>
>> On May 22, 11:45 am, MAC <macatad...@gmail.com> wrote:
>> > Saw this on a seperate group .. Since answer not known to me sharing it
>> > here
>> >
>> > you have a stack . Exposed functionality is push and pop only .
>> >
>> > What minimal modifications would you do such that
>> > you should find middle element in o(1) time .
>> >
>> > I think this is only possible if you make sure that at push you store
>> > the
>> > middle element with the top element as well .. this would mean push
>> > would
>> > cease to be o(1) & become o(n) .. . or is there some other trick ?
>> >
>> > thanks
>> > --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
