Understanding Queue in Data Structure, With Examples

Queues are a useful data structure in programming for modeling both technical and real-life situations. Understanding how the different kinds of queues work is an essential part of learning about data structures. In this article, we’ll explain the queue structure and illustrate it with examples. Let’s begin.

What Is the Queue Structure and How Does It Work?

There are many types of queues, but most of them operate on the First-In-First-Out (FIFO) principle. This is similar to a real-life queue, where the first person in the queue is the first person to leave the queue. This would be an example of a linear queue, but we can also have circular queues. These kinds of queues don’t have a fixed front and rear, such as a traffic light system. The last position in the queue simply wraps around to the front position.

Although these are the most common queue types, there are many others, which don’t obey the FIFO principle. A brief overview of these is given in the table.

Basic Operations of Queues

Most queue structures use the same basic operations. A summary of these follows.

How to Implement the Queue Structure

Most queues can be implemented using either an array or a linked list. The latter stores elements in a node and uses front and rear pointers. If we want to add an element, we need to check if the queue is full. Likewise, if we want to remove an element, we need to check if the queue is empty. In these cases, the operations can’t be performed.

When creating an array-based queue, we can add elements by incrementing the rear pointer by 1, or remove them by incrementing the front pointer. However, using a linked list is a little more complicated. When adding an element, we point the rear node to the new node and point the new node to be the rear node. To remove an element, the front pointer is assigned to the next node.

Next, let’s take a look at some simple examples of how queues are implemented, starting with linear queues. These examples are given in Python.

Linear Queue Implementation

The following code gives a basic example of creating a linear queue.

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            print("Queue is empty. Unable to dequeue.")
            return None

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

We usually begin the code by declaring the class and then defining the operations we’re going to use. For a linear queue, adding and removing elements is simple, using the “append” and “pop” methods. Next, circular queues will be explored.

Circular Queue Implementation

These queues are a little more complex but fairly intuitive. The following code demonstrates how to create an array-based circular queue structure.

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def enqueue(self, item):
        if self.is_full():
            print("Queue is full. Unable to enqueue.")
            return
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty. Unable to dequeue.")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

    def is_empty(self):
        return self.front == -1 and self.rear == -1

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def size(self):
        if self.is_empty():
            return 0
        return (self.rear - self.front + self.capacity) % self.capacity + 1

The process is similar, but the definitions of the operations are more elaborate. Some of the key differences are that we define a specific capacity with the circular queue, and have to account for circular behavior. As such, we must check if the queue is full or empty when adding or removing elements respectively. We increment the rear element by one and set the new element to the rear index to add an element. To remove an element, we increment the front pointer by one to remove the first element.

Priority Queue Implementation

Creating a priority queue structure isn’t as hard as it might sound. Consider this code:

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)[0]
        else:
            print("Priority queue is empty.")
            return None

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

Much of the logic here is the same, except we must indicate the priority when adding an element. The queue is then sorted based on the priority of its elements. When removing an element, the element with the highest priority is selected, since this has been sorted into the first position.

Deprioritized Queue Implementation

To create a deprioritized queue, we can modify the deque method as follows:

def dequeue(self):
        if not self.is_empty():
            max_priority = max(self.queue, key=lambda x: x[1])[1]
            deprioritized_items = [item for item in self.queue if item[1] != max_priority]
            deprioritized_item = next(item for item in self.queue if item[1] == max_priority)
            self.queue = deprioritized_items + [deprioritized_item]
            return deprioritized_item[0]
        else:
            print("Deprioritized queue is empty.")
            return None

The highest priority element is determined with the “max” and “lambda” functions, and a new list is created for all other elements. The deprioritized element is added to the end of the queue, instead of being removed.

Double-Ended Queue Implementation

A double-ended queue, or deque, is a queue structure where insertion and removal can happen at either end. We can achieve this with the following code:

class Deque:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            print("Deque is empty. Unable to remove from the front.")
            return None

    def remove_rear(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            print("Deque is empty. Unable to remove from the rear.")
            return None

    def size(self):
        return len(self.items)

Elements are added to the rear using “append,” and to the front using “insert.” Elements are removed at either end using the “pop” method.

Delay Queue Implementation

We use a min heap structure to implement a delay queue. This is a tree-like structure where the parent node is equal to or less than its derived nodes. This is done so that elements are processed at specific times in the correct order. We can implement this with the following code:

import time
from heapq import heappush, heappop

class DelayQueue:
    def __init__(self):
        self.queue = []

    def put(self, item, delay):
        expiration_time = time.time() + delay
        heappush(self.queue, (expiration_time, item))

    def get(self):
        if self.queue:
            current_time = time.time()
            expiration_time, item = self.queue[0]
            if current_time >= expiration_time:
                heappop(self.queue)
                return item
        return None

    def size(self):
        return len(self.queue)

    def is_empty(self):
        return len(self.queue) == 0

We include the “delay” argument to specify the time that passes before the item is dequeued. The delay is added to the current time in order to calculate the expiration time. Elements are added with a specific delay argument and are removed according to these delay times.

Pros, Cons, and Applications of Queue Structure

To finish, we’re giving a brief summary of the advantages and drawbacks of the queue data structure, along with how they’re often used.

Time Complexity of Queues

The time complexity of queue operations largely depends on the queue type. The table gives the time complexity for each queue operation.

Wrapping Up

Queues are a key concept in computer science, as one of the most common data structures. Most queues follow the FIFO principle, except for priority queues, deprioritized queues, and double-ended queues. The complexity and applications depend on the queue type, so being aware of them is essential to helping you effectively solve programming problems you may come across.

The image featured at the top of this post is ©NicoElNino/Shutterstock.com.