Home

›

Articles

›

Understanding Queue in Data Structure, With Examples # 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)

def dequeue(self):
if not self.is_empty():
return self.queue.pop(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)
deprioritized_items = [item for item in self.queue if item != max_priority]
deprioritized_item = next(item for item in self.queue if item == max_priority)
self.queue = deprioritized_items + [deprioritized_item]
return deprioritized_item
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

self.items.insert(0, 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
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.

## Understanding Queue in Data Structure, With Examples FAQs (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. #### Duncan Dodsworth, Author for History-Computer

Duncan Dodsworth is a writer at History Computer. If you find yourself reading an article about games, tech, or coding, you might see his name there. He majored in chemistry but realized he's much more comfortable behind a keyboard than a conical flask. When he's not tapping away, he's probably listening to music or reading a book about half as often as he says.