Module

Data.Stack

Package
purescript-stack
Repository
ashutoshdas96/purescript-stack

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.

<https://upload.wikimedia.org/wikipedia/commons/b/b4/Lifo_stack.png>

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

#Stack Source

data Stack a

Abstract Stack data type

Constructors

Instances

#stackNew Source

stackNew :: forall a. Stack a

/O(1)/. Create new empty Stack

#stackPush Source

stackPush :: forall a. Stack a -> a -> Stack a

/O(1)/. Push item onto Stack

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

#stackPeek Source

stackPeek :: forall a. Stack a -> Maybe a

/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 Source

stackPop :: forall a. Stack a -> Maybe (Tuple (Stack a) a)

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

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

#stackIsEmpty Source

stackIsEmpty :: forall a. Stack a -> Boolean

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

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

#stackSize Source

stackSize :: forall a. Stack a -> Int

/O(1)/. Compute number of elements contained in the Stack

stackSize stackNew == 0 (∀x)(∀s)((stackSize s == n) ⇒ (stackSize (stackPush s x) == n+1))

Modules
Data.Stack