Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

Stack data structure and associated operations

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.

In other words, a `Stack`

is an abstract data type that serves as a collection of elements, with two principal operations: `stackPush`

, which adds an element to the collection, and `stackPop`

, which removes the most recently added element that was not yet removed.

See also https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

# Documentation

Abstract Stack data type

stackPush :: Stack a -> a -> Stack a Source #

*O(1)*. Push item onto Stack

(∀x)(∀s)(stackPop (stackPush s x) == Just (s,x))

stackPeek :: Stack a -> Maybe a Source #

*O(1)*. Pop most recently added item without removing from the Stack

stackPeek stackNew == Nothing (∀x)(∀s)(stackPeek (stackPush s x) == Just x) (∀s)(stackPeek s == fmap snd (stackPop s))

stackPop :: Stack a -> Maybe (Stack a, a) Source #

*O(1)*. Pop most recently added item from Stack

stackPop stackNew == Nothing (∀x)(∀s)(stackPop (stackPush s x) == Just (s,x))

stackIsEmpty :: Stack a -> Bool Source #

*O(1)*. Test if stack is empty

stackIsEmpty stackNew == True (∀x)(∀s)(stackIsEmpty (stackPush s x) == True) (∀s)((stackSize s == 0) ⇔ (stackIsEmpty s == True))