Stacks

Data Structures & Algorithms

Continuing our journey exploring data structures and algorithms using Ruby as a means to implement them, we will now turn our attention to Stacks. If you have followed along up until now, this is going to be a piece of cake.

What is a stack? A stack is a linear data structure, like a linked list or an array. As a matter of fact, the most common stack implementations involve either a linked list or an array as the underlying data structure. The defining quality of a stack is the fact that it is Last In First Out (LIFO). In other words the last item that was added, or “pushed”, to the stack is the first item that the stack will return, or “pop”.

So a stack has two basic methods associated with it that we hinted at above. The “push” is how we add an item to the stack. The “pop” is how we get the top element off of the stack. You can imagine a stack as pez dispenser. The first piece of pez that you insert into the dispenser is the last one you will get out of it, conversely, the last piece of candy you put in the dispenser is the first you get out. Perhaps the image below will clear up any confusion.

There is one other method that many stacks implement, the “peek”. This method allows us to see the topmost element without actually “popping” it off. It is considered optional because of the fact that is essentially just a “pop” followed by a “push” of the element back onto the stack.

Ruby makes implementing a Stack trivial. As a matter of fact, Ruby arrays give us a push and pop method built in, and Ruby’s last method is essentially a “peek”, returning the last element of the array without actually removing it. So the below implementation of a Stack feels unnecessary, and it is, but hopefully this gives you a better understanding of how a Stack works.

class Stack
  def initialize
    @stack = []
  end

  def push(item)
    @stack.push(item)
  end

  def pop
    @stack.pop
  end

  def peek
    @stack.last
  end
end

That’s it, as discussed above, this is entirely an academic, learning implementation. Since Ruby provides us with all the functionality to mimic a Stack with its Array data structure. We create a new stack on initialization which is really just an empty array. We then leverage the built in push, pop and last methods to implement the push, pop, and peek methods of the Stack class.

Stacks are not uncommon in the wild, although, working at the abstraction level that most web developers work, we don’t think of them very often. Anytime you need to retrace your steps a Stack is a handy data structure, perhaps using the back button in a browser or traversing a maze. At a hardware level Stacks allow for recursive algorithms, pushing results on the stack for use later when the recursion bubbles back up to the initial call. This can also result in the dreaded stack overflow, duh, duh, duh. At the most basic hardware level, there is only so much memory available to the stack, try to push an extra element onto the stack and you get a stack overflow, or worse, a locked up computer.

Hopefully you have a better understanding of stacks now, how they work, and what they might be used for. Thanks for reading along, I suggest taking a look at the wikipedia link below for a more in depth article on Stacks that doesn’t focus only on Ruby. Until next time.

Stack (abstract data type) - Wikipedia