The Stack is a special data structure. We use lists to augment it and everything is the same, except for 3 small constraints -
- Data can only be inserted at the end of the stack
- Data can only be deleted from the end of the stack
- Only the last element of the stack can be accessed
A quick note- The terms end and start will change depending on which direction you’re parsing the array. This might lead to confusion. The solution is, it doesn’t matter which direction you parse it, as long as you are consistent.
In Elixir, prepending to a list is extremely efficient and takes only linear time (O(1)). For this reason, unless otherwise mentioned, we will always prepend to a list and pop the first element only.
Now you might be wondering, what do these additional constraints offer that makes stack so powerful?
Understanding the Stack
Stack simply follows the LIFO (Last In First Out) principle. Imagine this to be the naughty kids in school. They’ll be the last to enter the class, and the first to leave. We are only concerned about the naughty kids. This means we can only read/pop/append items at the end of the stack.
This behavior is extremely useful in day-to-day programs as demonstrated by the following examples-
The Undo action is a good example of stack. We keep appending the list of changes in a document to the stack, and just delete the last change to undo the previous action
Another example is the valid parentheses problem. Given a string, we are required to check if the parentheses are in the correct order & form a valid pair. We append each opening parenthesis to the stack, and delete it if the next character is its corresponding closing one. Finally, if the stack is empty, given string is valid.
A fun exercise would be to implement the Towers of Hanoi problem.
Most programming languages use Stack to implement recursion under the hood. Each recursive call is added to the stack until the base case. Then each functions value is interpolated and popped from the stack.
A few fun problems solved using stack are checked into this repo for reference. Do read.
Implementation
For conciseness & simplicity, we’ll implement the stack as a module, and reference functions from it.
As discussed above, stack is just a simple list, with added constraints.
Since we can only interact with a stack to append, read and pop the last element, we’ll name our functions as push/2, peek/1 and pop/1.
The Stack module
The push/2 function
To append items at the end of the stack, we only need 2 things - the stack to append to, and the item to append. That’s a one liner -
def push(stack, item), do: [item | stack]
Prepending to a list is extremely efficient in Elixir, which takes linear time (O(1)) under the hood.
The peek/1 function
Since we can only read the first element, we need to pass in only the stack.
def peek([]), do: nil
def peek([head | _]), do: head
The pop/1 function
To pop the last element, we need to pass in only the stack.
def pop([]), do: []
def pop([_ | tail]), do: tail
The Stack module
defmodule Stack do
def push(stack, item), do: [item | stack]
def peek([]), do: nil
def peek([head | _]), do: head
def pop([]), do: []
def pop([_ | tail]), do: tail
end
To maintain consistency, we’ll always alias in this module and interact with stacks using these functions only. That’ll keep the list from mutating accidentally.