Queues are everywhere. So abundant that a person might go through their day and utilize a queue without even recognizing it. For example, they might have had to wait in line in a busy restaurant, or driven down a one-way street, and maybe even had the unfortunate pleasure of being on an escalator with a person blocking the walk lane. Without a doubt, the "first come, first serve" nature of queues are present in the real world, and it should be no surprise that they're used frequently in the development world as well.

Assumptions

Knowledge of <a href="https://www.devmaking.com/learn/data-structures/linked-list/" target="_blank" style="color:inherit;">Linked Lists</a> and Arrays
Understanding of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" target="_blank" style="color:inherit;">Big-O Notation</a>

What is a Queue?

A queue is a list of objects where each item is added and removed in first-in-first-out (FIFO) order. A queue is often implemented with an array, linked list, or stack.

Understanding FIFO

First-in First-out is the driving idea behind queues; If you place two elements into the queue, the element that was inserted first, will always be the first element to be removed.

Conceptualization

To put this into a concrete perspective, imagine cars driving down a one way street. A red car turns down the street, and is followed by a blue car. At the end of the street, you can intuitively expect that the first car to leave will be the red car, followed by the blue car.

If we look at this example from the perspective of a queue, we could say that when a car enters the one-way street, the street is being enqueued with that car. Two cars could be enqueued into the street and when the first car reaches the end of the street it will be dequeued from the street.

Array Based Queue vs Linked List Based Queue

Before diving into the implementations and common methods of queues, let's look at two common ways that queues are implemented. In this article, the examples shown will be done using a linked list implementation.

Array Based Queue

Implementing a queue with an array is one of the most basic versions to implement. Depending on how the array-based implementation is created, the array may perform shifts or expansions given the statically sized nature of arrays. Using arrays to implement a queue usually performs faster than a linked list based queue, mainly due to not having to allocate space from the heap with every new enqueue. Some implementations of array-based queues will double the size of the array when the queue is filled up. The downside of this implementation is that when the array is doubled to fit more elements, there is a large amount of unused memory.

Linked List Based Queue

While linked list based queues may not perform as quickly compared to arrays due to the cost of heap memory allocation, they do perform better in memory in the sense that only the amount of memory that is needed will be used. Additionally, linked list queues do not necessarily need a limit to their size whereas an array may not always increase in size when it becomes full. If you are familiar with the dynamics of linked lists, implementing a queue structure using a linked list may seem more intuitive than using an array.

> Lower level languages like C++ allow the programmer to 'pre-allocate' memory in a practice called "memory-pooling" that helps overcome heap-allocations by 'reserving' memory in advance.

Stack Based Queue

As a side note, it is possible to implement a queue using two stacks, passing all the elements back and forth to dequeue elements. For academic and educational purposes it may be worth implementing. However the performance of this implementation does not compete well against array and linked list based queues.

Linked List Queue Composition

The composition of a linked list based queue is often setup like a regular linked list, but utilizing a tail node in addition to the head node representing the back and the front of the queue respectively. Additionally, the data structure often utilizes a size variable to quickly tell the length of the queue and check if the queue is empty or full.

Basic Queue Operations

So far there have been two methods of queues touched on: enqueue and dequeue. These two operations encapsulate the vast majority of queue functionality. As mentioned, we will be implementing a queue using a linked list approach.

Enqueue

The premise of enqueueing into a queue is as simple as adding the new element to the end of the list. In the linked list style queue, we call to the tail node, set it's next pointer to the new element being enqueued, and set the reference to the tail as the new element in the list.

Enqueue follows a similar logic pattern as the addLast function in a doubly linked list, except we do not need to worry about setting any previous pointers. As such, we can expect this operation to take O(1) time as opposed to a traditional O(n) time that would be incurred without the use of a tail node.

In implementation, there is an additional edge case where the queue may currently be empty, and if so, then a new node is created that represents both the head and the tail of the queue until another element is added (or the element is dequeued). Visualizing this in pseudo code looks like the following:

/* pseudo-code */
// The front and back of the queue references.
Node head;
Node tail;
// the size of our current queue.
int size;

function enqueue(int value){
    // Cover the base case.
    if( queue is empty ) {
        // Insert a new node at the 'end'
        tail = new Node(value);
        // Set the front to the same point as the end.
        head = tail;
        // Increment the size.
        size += 1;
        // Exit the function.
        return;
    }
    // Otherwise, add to the end of the queue.
    tail.next = new Node(value);
    // Set the new end of the queue.
    tail = tail.next;
    // Increment the current size.
    size += 1;
    return;
}

Dequeue

Removing, or dequeuing an element from a queue means that the element in the front of the list is popped off and the value of that element is returned. Queues contain another similar method called poll that has nearly identical functionality with a subtle difference in how the method handles an empty queue. In the dequeue method, if the function is called and the queue is empty, an error exception is thrown.

If you are familiar with the linked list removeFirst function, the logic involved when dequeuing will follow a similar process.

/* pseudo-code */
Node head;
Node tail;
int size;

function dequeue() {
    // Base case check for an empty queue
    if( queue is empty ){
        throw an exception;
    }
    // Special case where there is 1 element in the queue.
    if ( size == 1 ){
        // make a tmp node pointing to the head.
        Node tmp = head;
        // set the head and tail null.
        head = null;
        tail = null;
        // our queue now has 0 elements.
        size = 0;
        // give back the value of the dequeued item.
        return tmp.value;
    }
    // Make a tmp node pointing at the current head.
    Node tmp = head;
    // Move the head up to the next item.
    head = head.next;
    // Decrement the size.
    size -= 1;
    // Return the dequeued item's value.
    return tmp.value;

}

Additional Queue Operations

While enqueue and dequeue cover a majority of the functionality required when utilizing a queue, sometimes there are additional methods are needed to get the job done.

For instance, suppose you want to see what the next element in the queue is without removing it, or perhaps you want to receive null instead of an exception when trying to dequeue from an empty queue, even then you might also want to be able to tell if the queue is empty - or full for that matter! Luckily, many of these functions are popularly used when implementing queues, and they go by the names of peek, poll, isEmpty, and isFull.

Peek

Imagine a scenario where you need to dequeue from a queue until a certain element is returned. To do this would be simple; dequeue until the dequeued value is a certain element. What if instead, now you needed to dequeue until the first item in the queue is a certain value, without removing it from the queue. This is where the peek method comes in handy.

By being able to "peek" at the first element in the queue, we can tell what value is going to be dequeued next. In the thought problem above, we can peek the first element in the queue and remove it until the head node contains the desired value.

The peek method is very simple, consisting only of returning the value of the head node:

/* pseudo-code */
Node head;

function peek(){
    if( queue is empty ) {
        throw an exception;
    }
    return head.value;
}

Poll

It was mentioned earlier how dequeuing from an empty queue causes an error to be thrown. In some cases it is okay, but other times it may not be to our advantage to have the function throw an error if the queue is already empty. That is precisely what poll achieves.

With the near identical functionality that poll shares with dequeue, it can be expected that the function implementation would look identical.

/* pseudo-code */

function poll(){
    if (queue is empty) {
        return null;
    } 
    // you can call dequeue here, 
    // or copy in the dequeue code.
    else return dequeue();
}

Is Empty

The isEmpty method call does just that; checks if the queue is empty. Some implementations might check if the head node is null, while other's might verify this by checking the size of the queue, and it might look something like this:

/* pseudo-code */
int size = 0;

function isEmpty(){
    return size &lt;= 0;
    /* using &lt;= as opposed to == isn't 
    really necessary, but is a defensive practice */
}

> It is worth noting that using dequeue in combination with isEmpty eliminates the need for poll in many cases.

Is Full

Lastly, the isFull method checks to see if the queue is currently at it's maximum size. It is not always necessary to implement this method, however certain use cases may call for it such as a web server that can only allow so many backed-up connections at a time before rejecting any more connection requests until the queue has grown smaller.

If you are implementing this method into your queue, you might consider adding this method call in the enqueue method before inserting new elements.

/* pseudo-code */
int maxSize = 10;
int size = 0;

function isFull(){
    return size &gt;= maxSize;
    /*again, &gt;= is not necessarily needed 
    in this case as opposed to == if 
    the other methods are implemented correctly.*/
}

When to use a Queue

When considering a problem, a queue is great for ensuring elements are removed in the same order that they were inserted.

This is especially practical in web-servers where a new client connects and is placed in a queue until it is their turn to be served. Imagine instead a stack, or a structure where order is not guaranteed; the client could be waiting a long time to hear back from the server!

Other use cases include synchronizing data sent from asynchronous processes, and when low level programming and scheduling tasks in a computer system.