[algogeeks] DataStructure - Push,Pop & Find_Min in O(1)

[Prunthaban Kanthakumar]

Hi All,

One of my friends asked me this questions:
Can you frame a Stack like Data structure where Push,Pop and find_min takes O(1) time?

Well...
A Stack is already doing a good job by giving O(1) for Push and Pop.
We need a method to make it support O(1) find_min too.

Let me share my ideas. Comments are welcome.

Double Array (Linked lists can also be used) based Stack
------------------------------------------------------------------------------------

1. There will be two arrays A and MIN
2. There will be two indices top and topmin;

Here the array MIN stores the minimum value occured so far.
Let me show the implementation.

Method: Push(Val)
{
A[top] = Val
If(top = 0)
  MIN[topmin] = top
  topmin = topmin + 1
Else
  If(A[MIN[topmin-1]] > Val)
    MIN[topmin] = top
    topmin = topmin + 1
top = top + 1
}

Method: Pop
{
If(top == 0)
   throw exception
top = top - 1
If(MIN[topmin-1] == top)
   topmin = tommin - 1
return A[top]
}

Method: find_min
{
return A[MIN[topmin-1]]
}

(I think there is no need for a proof for why it always return the minimum)

Note: In the worst case... both arrays will be equal in size. This occurs when you push numbers in descending order.

Is there a better way????

Regards,
Prunthaban
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---