Mastering data structures in Ruby — Stacks

Stacks are a special kind of linked lists that allow us to efficiently store retrieve data in last in, first out order (LIFO). Or in other words, elements are retrieved in the opposite order they were stored on the stack.

As well as it happens with queues, stacks won’t allow us to insert/remove elements at random locations, and just like queues, they are no more than sequences of connected nodes.

Stack-based virtual machines like YARV (Ruby’s virtual machine) use stacks to store and eval bytecode instructions.

Let’s see the way a stack grows as we store (push) items onto it.

push(1) push(2) push(3) 
--- --- ---
 1   2   3 
--- --- --- 
 1   2 
--- --- 
 1 
---

Now let’s take a look at the way it shrinks when we remove (pop) items out of it.

pop pop pop
--- --- --- 
 3   2   1
--- --- --- 
 2   1
--- --- 
 1 
---

Stacks interface

The interface for stacks it’s similar to queues in the sense that they don’t have many methods, which is nice because the interface is easy to learn and hard to miss use.

The rationale behind helper methods for this data structure is the same we apply to the queues — Don’t have them —

Stack interface. Method names, summaries, and complexity.

Implementation details

Elements on the stack are represented by nodes that contain two attributes:

• The value that the current node holds.
• A pointer to the next node in the stack.

The first node of the stack is called head and the last one tail. To mark the end of the stack we must set the next pointer of the last element to nil.

As opposed to what happens with regular linked lists, when working with stacks you should not use head and tail directly from your code. The safest way to interact with stacks is thru the push, peek and pop methods.

What follows is a brief description of each method, its complexity and source code.

Initialize

This method is the stack constructor. It creates an empty stack, sets the head node to nil and the stack’s length to 0.

The complexity of this method is O(1).

def initialize
  self.head = nil
  self.length = 0
end

Push

Creates a new node to insert a value into the stack. The new node moves the element that’s at the head of the list and becomes the new head of the list.

Since the stack keeps pointers to its head and its tail, the complexity of this method is O(1).

def push data
  node = Node.new data
  if length == 0
    self.tail = node
  end

  node.next = self.head
  self.head = node
  self.length += 1
end

Pop

Removes an element from the stack. As it happens with queues, removals are straightforward because they always happen at the head of the stack.

To remove an element from the stack, we point the head to the node that it’s next to it and set tail to nil if the stack contains just one element.

The complexity of this method is O(1).

def pop
  return nil unless self.length > 0
  self.head = self.head.next
  self.tail = nil if self.length == 1
  self.length -= 1
end

Peek

Returns the node that’s at the head of the stack without removing it or nil if the stack is empty.

Since pop doesn’t return the removed element, peek is the way to go if you have to do something with that element.

The complexity of this method is O(1).

def peek
  self.head
end

Clear

Pops all elements from the stack.

The complexity of this method is O(n).

def clear
  while self.peek
    pop
  end
end

Each

This method walks the stack yielding one at a time until it reaches the last element.

The complexity to yield the next item in the stack is O(1). The complexity to yield the whole stack is O(n).

def each
  return nil unless block_given?
  current = self.head
  while current
    yield current
    current = current.next
  end
end

Print

Print the contents of the stack by walking its items.

The complexity of this method is O(n).

def print
  if self.length == 0
    puts "empty"
  else
    self.each { |node| puts node.data }
  end
end

When to use stacks

As someone who spent the past decade working on compilers, I can tell you for sure that stacks are one of the most used data structure in the field.

Stacks are great at managing instruction sequences, parsing expressions, and solving operators precedence; to name a few.

So that’s pretty much it about stacks. I hope you enjoyed it!

Next time, we will take a look at Hash Tables.

Thanks for reading!

PS: If you are a member of the Kindle Unlimited program, you can read a bit polished version of this series for free on your Kindle device.

Data Structures From Scratch — Ruby Edition.