Headline

A last in, first out (LIFO) abstract data type

Illustration

A simple implementation of stacks (of ints) is shown here as a functional data structure in Language:Haskell:.

{-| A simple implementation of stacks in Haskell -}

module Stack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
data Stack = Empty | Push Int Stack
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Empty
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty Empty = True
isEmpty (Push _ _) = False
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push = Push
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top (Push x s) = x
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop (Push x s) = s

-- | Compute size of stack
size :: Stack -> Int
size Empty = 0
size (Push _ s) = 1 + size s

These stacks are immutable. The push operation does not modify the given stack; it returns a new stack which shares the argument stack possibly with other parts of the program. The pop operation does not modify the given stack; it returns a part of the argument stack. We refer to Document:Handbook of data structures and applications for a profound discussion of functional data structures including the stack example. The functions for operations top and pop, as given above, are partial because they are undefined for the empty stack.

There are also alternative illustrative Stack implementations available:

https://github.com/101companies/101repo/tree/master/concepts/Stack

Stacks as lists without information hiding

{-| 

A leaky list-based implementation of stacks in Haskell.
That is, the representation type is not hidden.

-}

module LeakyListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
type Stack = [Int]
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = []
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push = (:)
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop = tail

-- | Compute size of stack
size :: Stack -> Int
size = length

That is, stacks are represented as lists while the Stack type is simply defined as a type synonym to this end. This implementation does not enforce information hiding.

Stacks as lists with information hiding

{-| 

An opaque list-based implementation of stacks in Haskell.
That is, the representation type is hidden. 

-}

module OpaqueListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
newtype Stack = Stack { getStack :: [Int] }
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Stack []
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null . getStack
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push x s = Stack ( x : getStack s)
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head . getStack
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop = Stack . tail . getStack

-- | Compute size of stack
size :: Stack -> Int
size = length . getStack

As before, stacks are represented as lists, but the Stack type is defined as a newtype which hides the representation as its constructor is not exported.

Stack with length

{-| 

An opaque list-based implementation of stacks in Haskell.
That is, the representation type is hidden.
The size of the stack is readily maintained.
Thus, the size can be returned with traversing the stack.

-}

module FastListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
data Stack = Stack { getStack :: [Int], getSize :: Int }
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Stack [] 0
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null . getStack
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push x s
  = Stack { 
      getStack = x : getStack s,
      getSize = getSize s + 1
    }
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head . getStack
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop s
  = Stack {
      getStack = tail (getStack s),
      getSize = getSize s - 1
    }

-- | Compute size of stack
size :: Stack -> Int
size = getSize

As before, stacks are represented as lists and again this representation is hidden, but an additional data component for the size of the stack is maintained so that the size of a stack can be returned without traversing the stack.

An application of stacks

See Concept:Reverse_Polish_notation.


Ralf Lämmel edited this article at Fri, 07 Jul 2023 18:22:46 +0200
Compare revisions Compare revisions

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.