Queue

  • Data Structures
  • Code
  • Queue

I'm still pretty busy with writing my conference talk, so as promised here is another short Data Structure post. This week I'm writing about Queue, another linear data structure. Where the Stack adhered to a LIFO (Last In, First Out) principle, Queue follows a FIFO (First In, First Out) princple. The first element put into the Queue will be the first element to leave the Queue.

You can visualize this structure with a line at an amusement park ride. The first person to get into the line will be the first person able to board the ride.

Structure and Terminology

Like with Linked Lists and Stack, a single data item within a Queue is called a node. A node in a Queue stores two things:

  1. A Value (I will use val), which is the thing you want stored
  2. A Next reference (I will use prev), which is the pointer that references the next item in the Queue.

As for the Queue itself, it will always keep track of a first property, which is the very first item inserted into the Queue, a last property, which is the last item inserted into the Queue, and the size, which is the number of items in the Queue.

So what does a Queue look like? Here's a very basic example:

1 -> 10 -> 100 -> 1000

In this little example, each number represents a node within the Queue. For each node, the number represents that node's value, and the arrow represents the next pointer reference.

1 would be the first item put into the Queue and the first item to be removed from the Queue. 1's next would reference 10, 10's next would reference 100, and 100's next would reference 1000. 1000 would be the last item in the Queue making it the last item to be removed from the Queue. The size of the Queue is 4, as there are 4 items within the Queue.

Practical Examples of a Queue

So where might you encounter a Queue in real world programming? You might think of a YouTube playlist as a sort of Queue. At its most basic implementation, as you add items into the playlist, the first item you added will get played first before items that were added later. Alternately, if you've ever worked with a copy machine printer in an office, then the print jobs are placed into a Queue. The first jobs that arrive in the Queue get printed first, and if you put your job in after someone else's big print job then you will just have to wait for that job to finish printing.

Big O of a Queue

OperationComplexity
InsertionO(1)
RemovalO(1)
SearchingO(n)
AccessO(n)

Insertion and Removal: Enqueuing and Dequeuing (the terms for Insertion and Removal, respectively, when working with a Queue) are only working with the start or end of the list -- if insertion happens at the beginning of the list then removal happens at the end of the list. Within the Queue implementation we write later, these operations will happen in constant time. However within the Array Implementation (next section), constant time is not possible due to de-indexing. I'll talk more about that in that section.

Searching and Access: Searching and Access are not very efficient in a Queue. Remember that we are concerned with one data item at a time, and accessing one piece of data is highly dependent on its place in the Queue. If we're looking for the last item inserted into the Queue then we have to wait for all of the items before it to be taken out of the Queue, giving us a worst case scenario of O(n).

Implementing a Queue with an Array

There is no built-in Queue data structure within JavaScript, but like with Stack, we can mimic Queue-like behavior using an Array.

Array Implementation #1: .push() and .shift()

One way that we can implement a Queue using an Array is with the .push() and .shift() methods. This method adds items to the end of the Array to enqueue them, and then removes items from the beginning of the Array to dequeue them.

var queue = [];
// Add things inqueue.push("Cheeseburger");queue.push("French Fries");queue.push("Onion Rings");
// Items have been queued up, one after another, newest item last:console.log(queue);// ["Cheeseburger", "French Fries", "Onion Rings"]
// "Peek" at the first item insertedconsole.log(queue.at(0));// "Cheeseburger"
// Check if the "Queue" is emptyconsole.log(!queue.length);// false
// Remove items - First In, First Out (FIFO)queue.shift(); // "Cheeseburger"queue.shift(); // "French Fries"queue.shift(); // "Onion Rings"

As I've pointed out in numerous blog posts, the .shift() array method that removes items from the beginning of an Array struggles with efficiency. When you remove the first item in an Array, you must re-index all of the subsequent items in the Array so that the new first item is at index 0.

If you're curious about what I'm doing with the .at() Method or the !queue.length line, I wrote about those in the Array Implementation Section of the Stack Blog Post.

Array Implementation #2: .unshift() and .pop()

The second way we can implement Queue-like behavior with an Array is with the .unshift() and .pop() methods, which add new items to the beginning of the Array to enqueue them, and removes items from the end of the Array to dequeue them.

var queue = [];
// Add things inqueue.unshift("Cheeseburger");queue.unshift("French Fries");queue.unshift("Onion Rings");
// Items have been queued up, one after another, newest item first:console.log(queue);// ["Onion Rings", "French Fries", "Cheeseburger"]
// "Peek" at the first item insertedconsole.log(queue.at(-1));// "Cheeseburger"
// Check if the "Queue" is emptyconsole.log(!queue.length);
// Remove items - First In, First Out (FIFO)queue.pop(); // "Cheeseburger"queue.pop(); // "French Fries"queue.pop(); // "Onion Rings"

Like .shift(), .unshift() -- the method that adds items to the beginning on an Array -- is inefficient. When a new item gets unshifted into an Array, everything else in the Array must be re-indexed.

A final note in this section is that this simply demonstrates the ability to use the built-in Array structure to achieve Queue-like behavior and treatment of data. You also could use one of our Linked List implementations as well. There are major performance considerations to think about if any of these structures are actually going to get used in a real-world application, and this gets into territory that is well beyond the scope of this blog.

Queue Implementation

I'd also like to implement my own version of the Queue data structure, just like I did with the Linked Lists and Stack. Here's the full implementation for future reference. Sections below will detail each method.

Note that there are a lot of different ways to implement a Queue, and this is just one. The thought with this approach is to continue with the same methods I have used to build Singly Linked List, Doubly Linked List, and Stack implementations, and to demonstrate the foundational concepts behind a Queue. If you want to do an Object- or Array-based implementation, then I highly encourage you to do so! I believe that no matter your approach, understanding the mechanics of these data structures and getting them to work makes you a stronger programmer. There are also methods in other Queue implementations that are not covered here. An example would be determing the Queue's capacity or the maximum number of items allowed in the Queue. I highly encourage you to write this out on your own if you're so inclined!

class Node {  constructor(val) {    this.val = val;    this.next = null;  }}
class Queue {  constructor() {    this.first = null;    this.last = null;    this.size = 0;  }  dequeue() {    if (!this.first) {      return undefined;    }    var currentFirst = this.first;    if (this.size === 1) {      this.first = null;      this.last = null;    } else {      this.first = currentFirst.next;      currentFirst.next = null;    }    this.size--;    return currentFirst.val;  }  enqueue(val) {    var newLast = new Node(val);    if (!this.first) {      this.first = newLast;      this.last = this.first;    } else {      this.last.next = newLast;      this.last = newLast;    }    return ++this.size;  }  isEmpty() {    return this.first ? false : true;  }  peek() {    return this.first ? this.first.val : undefined;  }}

Node Class

Each item within the Queue is called a node. Any time we add a node into the Queue, we'll do it using a Node Class. This class accepts a value, val, and also has a next property. By default next will be assigned the value of null, but as new nodes get added to the Queue, the next on these previously-added nodes will point to the new nodes.

class Node {  constructor(val) {    this.val = val;    this.next = null;  }}

We'll also use a Queue Class to initialize the Queue iteslf. We're starting here with just its constructor, but we'll add in all of the needed methods as we go. On initialization, an empty Queue will have a first set to null, a last also set to null, and a size set to 0.

Queue List Class

class Queue {  constructor() {    this.first = null;    this.last = null;    this.size = 0;  }}

Methods and Operations

.enqueue()

The first method we'll introduce is the .enqueue() method, which adds a new node to the Queue.

Here are the steps we take to create the .enqueue() method:

  1. Create a new node with the value, val. I'll store this in a variable called newLast
  2. Check if the Queue is empty. We'll know we have an empty Queue if the Queue has no first
  3. If the Queue is empty:
    1. Assign the new node as first
    2. Assign the last to also equal first
  4. If the Queue isn't empty:
    1. Set the last item in the Queue's next to point to the new node
    2. Assign the new node as the last item in the Queue
  5. Increment the size by 1
  6. Return the size

.enqueue() Implementation

enqueue(val) {  var newLast = new Node(val);  if (!this.first) {    this.first = newLast;    this.last = this.first;  } else {    this.last.next = newLast;    this.last = newLast;  }  return ++this.size;}

In the very last line, return ++this.size, I'm using the ++ increment operator in a pre-increment fashion. This is done by pre-pending this.size with ++. This code simply increments this.size before returning this.size. It allows me to accomplish, in one line, the following:

this.size++;return this.size;

It's a small optimization. Read more about pre-incrementing in this Stack Overflow thread.

.dequeue()

Now let's look at the .dequeue() method, which removes the first item in the Queue.

  1. Return undefined if the Queue is empty (again, if there's no first then it's an empty Queue)
  2. Store the current first item into a variable named currentFirst
  3. Check whether there is only 1 item in the Queue
  4. If there's only 1 item in the Queue:
    1. Assign first the value of null
    2. Assign last the value of null
  5. If there's more than 1 item in the Queue:
    1. Assign first the value of currentFirst's next
    2. Assign currentFirst's next the value of null, breaking the link between this node and the Queue
  6. Decrement size by 1
  7. Return the value of the node we have removed from the list (currentFirst.val)

.dequeue() Implementation

dequeue() {  if (!this.first) {    return undefined;  }  var currentFirst = this.first;  if (this.size === 1) {    this.first = null;    this.last = null;  } else {    this.first = currentFirst.next;    currentFirst.next = null;  }  this.size--;  return currentFirst.val;}

.peek()

In a Queue we're only concerned with the value of the first item in the Queue. Because of this, there is no .get() method. Instead, our Access method is called .peek().

  1. Check if the Queue is empty
  2. If the Queue is empty:
    1. Return undefined
  3. If the Queue isn't empty:
    1. Return (but do not modify or remove) the value of the first item in the Queue

.peek() Implementation

peek() {  return this.first ? this.first.val : undefined;}

I used a Ternary Operator statement here. I wrote about this statement previously in the Stack .peek() Method implementation.

.isEmpty()

The last method in our Queue implementation is the .isEmpty() method, which returns true if the Queue is empty and false if the Queue is not empty.

  1. Check whether there are any items in the Queue
  2. If there aren't items in the Queue, return true
  3. If there are items in the Queue, return false

.isEmpty() Implementation

isEmpty() {  return this.first ? false : true;}