Data Structures in Ruby: Stack

Anthony Lepore
Apr 16 · 4 min read

A stack is a simple data structure that follows the principle, “Last In, First Out.” Unlike many terms used in computer science, this one actually says what it is: A stack. Think of a stack of papers. If you piled the bills you received in the mail on a table one on top of the other as you received them each day, you would have a stack of bills. Let say you did this all month, and at the end of the month, you went to pay them all. You may simply begin at the top of the pile of the bills and continue to grab from the top for each bill you pay. In effect, you would be paying the last bill you received first. This is a stack: Last in, first out.

The Stack Data Structure can be thought of as a pile of books.

In computing, stacks are used when order is important and constant time is a concern. The Big O time complexity of the two main methods for the stack data structure is O(1) for insertion and removal. The history of your internet browser is an example of information stored as a Stack. Whenever you hit the back button, the last page you visited is the first page you see. The undo function of a text editor is another example of the use of a stack. In the following posts on data structures, we will need to use stacks and its cousin, queues for more involved data structures, and their traversal.

We are going to create a stack using a data structure we have already covered, the Singly Linked List. The two main methods for Stack are #push and #pop. These operate the same way that #unshift and #shift work in a Singly Linked List. However, since it is conventional to name the method to add to a list #push, and to remove from a list #pop, we will follow this guideline.

To begin creating our Stack data structure in Ruby, we’ll begin similarly to the creation of the Singly Linked List. A Node class needs to be initialized with instance variables to store the data or value of the node, as well as the pointer to the next node.

class Node
attr_accessor :data, :next
def initialize(data)
@data = data
@next = nil
end
end

For the Stack class, we will begin by initializing variables for the beginning of the list, commonly called the root, the last node in the list, and the size of the list.

class Stack
attr_accessor :root, :last, :size
def initialize
@root = nil
@last = nil
@size = 0
end
end

To begin populating the Stack, we will first code our #push method. Unlike an array or standard linked list, we will be pushing onto the front of the list, not the end. This is specifically to keep time complexity to constant time: O(1). If you recall, removing a node at the end of a Singly Linked List is O(n) since we have to traverse the entire list to get to the pointer of the node previous to the end. Here, we are setting up our data structure to always operate at the beginning of the linked list

The #push method begins by creating a new Node. Then, we check if the Stack is currently empty. If so, we just assign both the root and the last variables to be the newly created node. If there is at least one other node already in the Stack, we set the next pointer of the newly created node to be the old root, and reassign @root to be the newly created node. The return of the method can be a few different things, such as true or the node just entered. Here, we will return the size of the Stack. But this is up to you.

def push(data)
new_node = Node.new(data)
if !@root
@root = new_node
@last = new_node
else
old_head = @root
@root = new_node
new_node.next = old_head
end
return @size += 1
end

To remove from a Stack, we use the #pop method. Here, the method returns the root, or the last element pushed onto the Stack and also reassigns the node that was after the root to be the new @root. If this was the last node in the Stack, we need to set @last to nil. Also, if the Stack was empty we also need to return nil.

def pop
return nil if @size==0
old_head = @root
if @root==@last
@last = nil
end
@root = @root.next
@size -= 1
return old_head
end

There are two other minor methods that are often a part of the Stack functionality: #is_empty? and #peek. The #is_empty? method returns a Boolean true/false and checks to see if there is a root present. We could have also done this by checking the size of the Stack. The #peek method returns what is on the top of the Stack without actually removing it.

def is_empty?
return !@root
end
def peek
return @root
end

At this point, you make be asking if we could have just done this using #pop and #push on a standard Ruby array and still keep Big O to O(1). Yes, of course. However, the Ruby array object comes loaded with many other functions that may be unnecessary for your purpose, and the flexibility of being able to populate the Node Class with any type of information that you want is good to have in case you need it.

Next week we will delve into the Queue Data Structure in Ruby.

CodeX

Everything connected with Tech & Code

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store