Home

 › 

Articles

 › 

Understanding Queue in Data Structure, With Examples

What Are Tree Traversals?

Understanding Queue in Data Structure, With Examples

Key Points

  • Queues are a versatile data structure used in programming and real-life scenarios.
  • There are many types of queues that don’t follow the First-In-First-Out principle.
  • Basic operations of queues include enqueue, dequeue, front, rear, isEmpty, and size.
  • Queues can be implemented using arrays or linked lists, each with their own advantages and disadvantages.
  • Queues are commonly used in real-life scenarios, such as managing queues at a store or scheduling operations.

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.

Queue TypeDefinition
Priority queueElements are prioritized, meaning those with the highest priority are dequeue first. These don’t obey the FIFO principle.
Deprioritized queueInstead of being removed, elements are de-prioritized.
Double-ended queueElements can be inserted and removed from both ends of the queue.
Delay queueElements are dequeued after a specific time has lapsed, rather than by the FIFO principle.

Basic Operations of Queues

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

OperationExplanation
EnqueueAdds elements to the queue.
DequeueRemoves elements from the queue.
FrontReturns the front element.
RearReturns the rear element.
IsEmptyChecks if a queue is empty.
SizeChecks the queue size.

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.

Queue TypeProsCons
LinearSimple to use, obeys FIFO principleInefficient for large datasets, and frequent insertion/deletion
CircularEfficient memory use, and constant time complexity for enqueue/dequeueFixed-size, complex implementation
PriorityEfficient access of important elementsRelatively slow insertion/deletion, can be complicated
DeprioritizedAllows retention of elements rather than removal, as well as history of removalAdditional memory required, and complexity increases
Double-endedFlexible insertion/deletion,More complex than linear or circular queues, and slower operations
DelayAllows timed operations, and efficient accessMay need external management, and can be complex
Queue TypeApplication
LinearPrint and task scheduling, real-life queues
CircularCPU task scheduling, traffic light systems
PriorityPrioritizing tasks, shortest path calculations
DeprioritizedManaging tasks, logging events
Double-endedSearch algorithms
DelayTask and event scheduling according to time

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.

Queue TypeTime Complexity for EnqueueTime Complexity for Dequeue
LinearO(1)O(1)
CircularO(1)O(1)
PriorityO(log n)O(log n)
DeprioritizedO(1)O(n)
Double-endedO(1)O(1)
DelayO(log n)O(log n)

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.

Frequently Asked Questions

What are queues?

Queues are data structures used to model real-life queues, usually obeying the First-In-First-Out (FIFO) principle. This is where the first element added is the first to be removed. The exceptions to this are priority queues, deprioritized queues and double-ended queues.

Why are queues important?

Queues are widely used to solve both computer science problems and real-life problems, so having an understanding of them is essential if you’re working with code.

What different kinds of queues are there?

The most common types of queues are linear queues, circular queues, priority queues, deprioritized queues, double-ended queues and delay queues.

What are the pros and cons of using queues?

Queues generally allow for efficient insertion and deletion of elements, as well as various ways to maintain an order and manage memory. However, accessing the middle elements is generally not every efficient, and particularly large queues can run into performance issues.

What operations do queues use?

Queues often make use of enqueue and dequeue to add and remove elements, as well as isEmpty and isFull to check the status of the queue. Append and pop can be used to add and remove elements for relatively simple queues, such as linear queues and double-ended queues.

What type of dataset do queues use?

Queues usually use either an array or linked list.

What is the time complexity of queue operations?

This depends on the queue type, but, generally, the complexity is constant for enqueue and dequeue operations. This is different in the case of priority queues, where the complexity of O(log n). Deprioritized queues also take linear time, O(n), to remove the deprioritized element. Delay queues also differ, depending on their implementation, but for the queue in the article, the complexity would be O(log n).

What are the applications of queues?

Queues are commonly used to manage memory, as well as schedule operations, tasks and print jobs. As well as this, they can be used to manage traffic light systems, prioritize tasks and manage real-life queues where the person at the front leaves the queue first. For example, people queuing at an amusement park, or in a call center queue. Queues can also be used for network protocols, as data must be sent in packets and is often ordered and prioritized. Data is also managed using queues in when listening to music or streaming media, as some of the content is usually loaded in advance to allow seamless streaming.

To top