Stacks

A stack is a collection that is based on the Last In First Out (LIFO) policy.

The following figure presents a sample stack:

To implement a simple functional stack, we need to provide push, pop, isEmpty, and size operations. We implemented a functional LinkedList in the previous section, which can be used to implement a simple functional stack with the following operations:

• push: The cons operation in LinkedList
• pop:
• isEmpty: The isEmpty operation in LinkedList
• size: The size method in LinkedList

As seen here, the only operation that is missing is pop. Let's implement that:

func pop() -> (element: Element, list: Stack)? { 
    switch self { 
    case .node(let data, let next): 
        return (data, next) 
    case .end: 
        return nil 
    } 
} 

To test this, we can execute the following:

let stack = Stack<Int>.end.cons(1).cons(2).cons(3) 

if let (elment, stack) = stack.pop() { 
    print(elment) 
    if let newStack = stack.pop() { 
        print(newStack) 
    } else { 
  ...