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 Type | Definition |
---|---|

Priority queue | Elements are prioritized, meaning those with the highest priority are dequeue first. These don’t obey the FIFO principle. |

Deprioritized queue | Instead of being removed, elements are de-prioritized. |

Double-ended queue | Elements can be inserted and removed from both ends of the queue. |

Delay queue | Elements 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.

Operation | Explanation |
---|---|

Enqueue | Adds elements to the queue. |

Dequeue | Removes elements from the queue. |

Front | Returns the front element. |

Rear | Returns the rear element. |

IsEmpty | Checks if a queue is empty. |

Size | Checks 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 Type | Pros | Cons |
---|---|---|

Linear | Simple to use, obeys FIFO principle | Inefficient for large datasets, and frequent insertion/deletion |

Circular | Efficient memory use, and constant time complexity for enqueue/dequeue | Fixed-size, complex implementation |

Priority | Efficient access of important elements | Relatively slow insertion/deletion, can be complicated |

Deprioritized | Allows retention of elements rather than removal, as well as history of removal | Additional memory required, and complexity increases |

Double-ended | Flexible insertion/deletion, | More complex than linear or circular queues, and slower operations |

Delay | Allows timed operations, and efficient access | May need external management, and can be complex |

Queue Type | Application |
---|---|

Linear | Print and task scheduling, real-life queues |

Circular | CPU task scheduling, traffic light systems |

Priority | Prioritizing tasks, shortest path calculations |

Deprioritized | Managing tasks, logging events |

Double-ended | Search algorithms |

Delay | Task 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 Type | Time Complexity for Enqueue | Time Complexity for Dequeue |
---|---|---|

Linear | O(1) | O(1) |

Circular | O(1) | O(1) |

Priority | O(log n) | O(log n) |

Deprioritized | O(1) | O(n) |

Double-ended | O(1) | O(1) |

Delay | O(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.

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