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 {
...