Posts Tagged ‘minstack’

Programming Praxis – Min Stack

July 27, 2012

In today’s Programming Praxis exercise, our goal is to create s stack-like data structure that can push, pop and give the minimum element in the stack in O(1). Let’s get started, shall we?

To represent a stack, we can use a basic linked list. We’ll need two of them, one to hold the elements and one to hold the consecutive minimums. I’ve put them in a tuple, though a datatype declaration would’ve been an option as well.

An empty minstack is just two empty lists.

empty :: ([a], [a1])
empty = ([], [])

When pusing a new element we add it at the front of the list and optionally in the list of minimums as well.

push :: Ord a => a -> ([a], [a]) -> ([a], [a])
push x (ms,xs) = (if null ms || x < head ms then x:ms else ms, x: xs)

To pop, we return the popped element (if any) and the new minstack.

pop :: Eq a => ([a], [a]) -> (Maybe a, ([a], [a]))
pop (m:ms,x:xs) = (Just x, (if m == x then ms else m:ms, xs))
pop s           = (Nothing, s)

To find the minimum element we simple take the first element in the list of minimums.

min' :: ([a], [a]) -> Maybe a
min' (m:_, _) = Just m
min' _        = Nothing

Some tests to see if everything is working properly:

main :: IO ()
main = do let top = fst . pop
          let pop' = snd . pop
          let a = push 5 . push 4 $ push 3 empty
          print $ top a == Just 5
          print $ min' a == Just 3
          let b = push 2 $ push 1 a
          print $ top b == Just 2
          print $ min' b == Just 1
          let c = pop' . pop' $ pop' b
          print $ top c == Just 4
          print $ min' c == Just 3
          let d = pop' $ pop' c
          print $ d == empty