loading...

Learning Queues

123jackcole profile image Jack Cole Updated on ・2 min read

In this week's post I'll be going over queues. Similar to stacks, which we discussed last week, queues are a linear data structure, meaning the data elements are arranged sequentially. However, queues operate on the first in first out principle, or FIFO.

Queue Diagram from Wikipedia

The term queue originates from the British term for a waiting line. Queues require two main methods, enqueue and dequeue. Enqueue adds an element to the end of the queue. And dequeue removes and element from from the beginning of the queue. In Javascript this can easily be done by representing the queue as an array. We can then use the push method to add the the end of the queue, and shift to remove from the beginning of the queue.

Basic queue

Next, I'd like to do a little callback to my post on linked lists and look at how we can implement a queue using a linked list.

Instead of having basic elements like our first example this queue will have nodes. These nodes will contain the data we want, as well as a pointer to the next node in the queue.

To implement the queue would first need some constructors. One for our nodes and another for our queue.

Node and Queue Constructors

Next, we will need to implement our enqueue function. The concept is still the same, but we need to tweak it to conform to the linked list structure. We'll begin by creating a node using the data we need. Then we make our node the head if there is no current head, otherwise we'll add a pointer to the node at the end of our queue, then add our new node to the end of the queue.

Enqueue

For our dequeue method, we save the data we want from the first node in our queue, our head, then we replace that head with the next node in the queue.

Dequeue

As always you can check out the code from this post at my Github.

Posted on by:

123jackcole profile

Jack Cole

@123jackcole

Software engineer, tea lover, wannabe ramen chef

Discussion

markdown guide