Tutorial on Implementing a Deque in Ruby
Examples and methods —
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
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.
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.
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
Next, we need to declare
pushBack, a method to add nodes to the back 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
Now, the back, with
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
And, then, the last with
Another important question we may want to ask our deque is if it is empty:
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.