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!

You can get the code from this post by clicking here.

Next time, we will take a look at hash tables. Stay tuned.

Thanks for reading! Also, don’t forget to clap if you like this post :)

PS: As we move forward in mastering data structures, subjects discussed thoroughly on previous posts are not covered in great detail. If you want to get the most of this series, I recommend you to start from the first post about linked list.