Queue Data Structure

Exploring the Concept of a Queue

In computer science, a Queue is a fundamental data structure that mirrors the concept of a real-world queue. Just like waiting in line at a store, a queue follows the principle of FIFO (First-In-First-Out). This means that the item that is added first to the queue will also be the first one to be removed.

To delve deeper, a queue can be visualized as a list or collection where new elements are inserted at one end, typically referred to as the rear end or the tail of the queue. On the other hand, elements are removed from the opposite end, often known as the front end or the head of the queue. This orderly structure ensures that items are processed in the same sequence in which they were added, maintaining a fair and organized flow of data..

The concept of a queue can be likened to the real-world scenario of a ticket queue outside a cinema hall. In this scenario, the person who joins the queue first receives their ticket first, while the last person in line receives their ticket last. This parallels the FIFO (First In First Out) principle followed in data structure queues.

1. A queue is essentially an ordered list that allows insert operations to occur at one end, known as the REAR, and delete operations to take place at the other end, known as the FRONT.

2. The term "queue" is synonymous with a First In First Out list, emphasizing the order in which elements are processed.

3. An everyday example of a queue is the line of people waiting to purchase a rail ticket, where individuals are served in the order they joined the queue.

Operations performed on a queue

Queues support several fundamental operations that are crucial for their functionality. These operations include:

• Enqueue: Enqueueing involves inserting an element at the rear end of the queue. This operation does not return any value.

• Dequeue: Dequeueing entails removing an element from the front end of the queue. It also returns the element that has been removed from the front end, typically returning an integer value.

• Peek: The Peek operation allows you to view the element pointed to by the front pointer in the queue without deleting it.

• Queue overflow (isfull): This operation indicates an overflow condition when the queue reaches its maximum capacity and can no longer accept new elements.

• Queue underflow (isempty): This operation signifies an underflow condition when the queue is empty, meaning there are no elements present in the queue.

Different ways to implement a queue

There are two primary methods for implementing a queue:

• Implementation using an array: Queue implementation through sequential allocation can be achieved using an array data structure.

• Implementation using a linked list: Queue implementation through linked list allocation involves using a linked list data structure.

Types of Queues in Data Structure

There are four different types of queues in data structures:

• Simple Queue

• Circular Queue

• Priority Queue

• Double-Ended Queue (Deque)

Simple Queue

Simple Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are added to the rear (back) and removed from the front (head).

• Ordered collection of comparable data kinds.

• Queue structure is FIFO (First in, First Out).

• When a new element is added, all elements added before the new element must be deleted in order to remove the new element.

Circular Queue

A circular queue is a special case of a simple queue in which the last member is linked to the first. As a result, a circle-like structure is formed.

• The last node is connected to the first node.

• Also known as a Ring Buffer, the nodes are connected end to end.

• Insertion takes place at the front of the queue, and deletion at the end of the queue.

• Circular queue application: Insertion of days in a week.

Priority Queue

In a priority queue, the nodes will have some predefined priority in the priority queue. The node with the least priority will be the first to be removed from the queue. Insertion takes place in the order of arrival of the nodes.

Some of the applications of priority queue:

• Dijkstra’s shortest path algorithm

• Prim’s algorithm

• Data compression techniques like Huffman code

Below diagram shows how an application use priority queue for the items consumed by the user.

Deque (Double Ended Queue)

In a double-ended queue, insertion and deletion can occur at both the queue's front and rear ends.

Easy Problems on Queue Data Structure:

• Implement Stack using Queues

• Detect cycle in an undirected graph using BFS

• Breadth First Search or BFS for a Graph

• Traversing directory in Java using BFS

• Vertical order traversal of Binary Tree using Map

• Print Right View of a Binary Tree

• Find Minimum Depth of a Binary Tree

• Check whether a given graph is Bipartite or not

Medium Problems on Queue Data Structure:

• Flatten a multilevel linked list

• Level with maximum number of nodes

• Find if there is a path between two vertices in a directed graph

• Print all nodes between two given levels in Binary Tree

• Find next right node of a given key

• Minimum steps to reach target by a Knight

• Islands in a graph using BFS

• Level order traversal line by line | Set 3 (Using One Queue)

• Find the first non-repeating character from a stream of characters

Hard Problems on Queue Data Structure:

• Sliding Window Maximum (Maximum of all subarrays of size K)

• Flood Fill Algorithm

• Minimum time required to rot all oranges

• Shortest path in a Binary Maze

• An Interesting Method to Generate Binary Numbers from 1 to n

• Maximum cost path from source node to destination

• Shortest distance between two cells in a matrix or grid

• Snake and Ladder Problem

• Find shortest safe route in a path with landmines

• Count all possible walks from a source to a destination with exactly K edges

• Minimum Cost of Simple Path between two nodes in a directed and weighted graph

• Minimum Cost Path in a directed graph via given set of intermediate nodes

• Find the first circular tour that visits all petrol pumps