Tutorial on Implementing a Deque in Ruby

Examples and methods — pushFront, popFront, pushBack, and popBack

Oluwadamilare Olusakin
Aug 23 · 4 min read
Photo by Chris Ried on Unsplash

If you’re reading this, I’m guessing you already know what a deque is and you are trying to implement one in Ruby, or you’re in the process of learning about deques.

Very briefly, I will try to refresh your memory or add to your knowledge of deques.

A deque is an abstract data structure. Deque is an acronym for a double-ended queue.

To explain it’s importance, I will assume you have some knowledge of big O notation and the notations for some of the in-built data structures in the programming language you use to create your bugs.

Consider the array of elements below, if you want to access the element in the 0-index via the key, you have a constant time operation O(1).

If you were to add an element to the back of that array, that will also be a constant time operation O(1).

It is the same as removing an element from the back of the array.

Arrays seem great so far, yes?

But, here come the costly operations. Imagine if you wanted to add an element to the front of the array — you would need to move all the elements in the array to the right before that’s possible and this becomes comes with a price of $O(n).

From this, we can see that we had to carry out six operations to add a single element to the front of the array. Imagine if there were a million items in the array, that will quickly turn into a million operations.

And, the above is the same for removing an element from the front of an array, just in reverse.

If you were carrying out some tasks where accessing elements is a secondary concern and you will be adding to and removing from the front of a data structure more often…

This is where a deque comes in handy. It’s like an open-ended array that allows you to add and remove elements from the front or back of the data structure in O(1) time.

It gives you some nifty methods, such as pushFront, popFront, pushBack, popBack, and more.

Deques work on the principles of nodes and pointers:

Every node has at least two parts, the value of the node and at least one pointer (it could have two, as we will see later in this tutorial). Pointers point to other nodes and this is how a deque is linked in memory.

Let’s implement one and see what each of these methods do:

First, we set up our node class to enable us to create nodes.

Create a node class to enable you to add nodes into your deque

From the above class, we can see that the value of the node is stored in @value and the pointers are @next_node which point to the node ‘in front’, and prev_node which points to the one ‘behind’.

Next, we initialize our deque class. There are a bunch of ways to set up the deque but this is my favorite, please experiment with yours.

Initialize the deque with the first element set to nil

Next, we need a pushFront method that’ll allow us to add to the front of the deque. This method is quickly going to become our best friend, as well as its counterpart popFront.

The push front method is really crucial, it allows us to add elements to the front of the deque

Next, we need to declare pushBack, a method to add nodes to the back of the deque.

pushFront adds a new element to the front of the deque

Now that we’ve figured out how to put stuff in the deque, let's try removing. First, from the front by declaring popFront.

Now, the back, with popBack.

Next, we might want to retrieve the first or last element as they’re the most crucial to us. We start with the first, by declaring topFront.

topFront returns the first element in the deque

And, then, the last with topBack.

topBack returns the last element in the queue

Another important question we may want to ask our deque is if it is empty:

isEmpty? returns a boolean by checking if the first element is nil or not

Now, I will stop here for this implementation but there are a few more methods you can add to the deque to get it to do some more amazing stuff.

If you would like some help with those, do let me know and I will make a sequel or several sequels for this tutorial.


Resources

Find the code for this tutorial in my GitHub repo.

For an example on the usefulness of deques, check out my tutorial on the sliding maximum problem.

Advice for programmers.

Oluwadamilare Olusakin

Written by

Better Programming
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade