What are and how to use Queues (Queue)

A QUEUE, or Queue, is a collection of elements used to organize and manipulate elements in a specific order.

Queues are also called FIFO (First-In, First-Out) structures, because they follow the principle that the first element inserted (First-In) is the first to be removed (First-Out).

Whenever a new element is inserted into the QUEUE, it is placed at the back. When an element is removed, it is taken from the front.

This is achieved through two main operations:

• Enqueue: Adds an element to the end of the queue.
• Dequeue: Removes and returns the front element of the queue.

Internally, a QUEUE can be implemented using a simple Array or a linked list, or a ring buffer, among other options.

In addition to these basic operations, other operations can also be performed on a QUEUE, such as checking if it is empty or accessing the front element without removing it.

Properties

When to use a Queue

It makes sense to use a QUEUE in processes that involve waiting and where it is logical that those who have been waiting the longest should be served first.

A queue resembles a line of people waiting their turn for a service, for example to enter the cinema. It is reasonable for the person who arrived first, has been waiting the longest, and should be the first to be served.

In a computer, for example, it makes sense in the print queue. Documents waiting to be printed on the printer should be served in the order they arrived.

But there are many more examples. Almost always when we have to deal with issues related to waiting for processes, or communications, we will possibly have a queue-like structure.

Example of Queue in different programming languages

Below are examples of how to implement a queue in different programming languages:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        Queue<int> queue = new Queue<int>();

        queue.Enqueue(5);
        queue.Enqueue(10);
        queue.Enqueue(15);

        int frontElement = queue.Dequeue(); // Returns 5
        Console.WriteLine(frontElement);
    }
}

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> queue;

    queue.push(5);
    queue.push(10);
    queue.push(15);

    int frontElement = queue.front(); // Returns 5
    queue.pop();

    cout << frontElement << endl;
    return 0;
}

class Queue {
    constructor() {
        this.queue = [];
    }

    enqueue(element) {
        this.queue.push(element);
    }

    dequeue() {
        return this.queue.shift();
    }

    peek() {
        return this.queue[0];
    }

    isEmpty() {
        return this.queue.length === 0;
    }
}

const queue = new Queue();
queue.enqueue(5);
queue.enqueue(10);
queue.enqueue(15);

const frontElement = queue.dequeue(); // Returns 5
console.log(frontElement);

from collections import deque

queue = deque()

queue.append(5)
queue.append(10)
queue.append(15)

front_element = queue.popleft() # Returns 5
print(front_element)

In the previous examples, it is shown how to create a queue using the data structures provided by each programming language. Insertion, deletion, and access to the front element of the queue are performed.

Efficiency

The efficiency of a QUEUE will depend on how it has been implemented internally. But, let’s consider that it has been implemented “well”.

In this case, reading and removing elements in a queue are done in constant time O(1), since it accesses the first element of the queue.

Insertion in a queue is also efficient, as it is added to the end of the queue in constant time O(1).

The rest of the operations do not make sense since you can only access the element at the top of the stack. You cannot access elements at intermediate positions without popping all the elements above.