Queue in Data Structure

What is Queue in Data Structure?

The Queue in data structure is an ordered, linear sequence of items. It is a FIFO (First In First Out) data structure, which means that we can insert an item to the rear end of the queue and remove from the front of the queue only. A Queue is a sequential data type, unlike an array, in an array, we can access any of its elements using indexing, but we can only access the element at the front of the queue at a time.

A queue of people waiting for their turn or a queue of airplanes waiting for landing instructions are also some real life examples of the queue data structure. In the above illustration, we can see that the person standing at the front of the queue will be the first one to leave the queue and the person standing at the last of the queue will be the last one to leave.

Other real-life applications of queues include:

• Managing people on an escalator
• Organizing customers in a cashier line at a store
• Queueing vehicles at a car wash
• Regulating traffic flow through one-way exits

Queue Representation

A Queue in data structure can be accessed from both of its sides (at the front for deletion and back for insertion).

The following diagram tries to explain the queue representation as a data structure-

A Queue in data structure can be implemented using arrays, linked lists, or vectors. For the sake of simplicity, we will be implementing queue using a one-dimensional array.

Types of Queue in Data Structure

1. Simple Queue:

• Follows the First-In-First-Out (FIFO) principle.
• Elements are inserted to the rear and removed from the front.
• Linear structure with ordered collection of comparable data.
• Addition of new elements requires deletion of older elements in order.

2. Circular Queue:

• Last member is linked to the first, forming a circular structure.
• Also known as a Ring Buffer.
• Insertion occurs at the front, and deletion at the end of the queue.

3. Priority Queue:

• Nodes have predefined priorities.
• Node with the least priority is removed first.
• Insertion based on the order of node arrival.
• Used in algorithms like Dijkstra’s shortest path and Prim’s algorithm, and in data compression techniques like Huffman coding.

4. Deque (Double-Ended Queue):

• Allows insertion and deletion at both front and rear ends.
• Provides flexibility in managing data with operations from both ends.

Queue Operations

Enqueue

The Enqueue operation inserts an element at the rear of the queue.

Algorithm Procedure:

1. Verify if the Queue is at full capacity.
2. Initialize front to 0 for the initial element.
3. Increment rear by 1.
4. Place the new element at the rear index.

Dequeue

The Dequeue operation extracts an element from the front of the queue.

Algorithm Procedure:

1. Verify if the Queue is empty.
2. Retrieve the value at the front index.
3. Increment front by 1.
4. For the last element, set both front and rear to -1.

Peek

The Peek operation is used to return the front most element of the queue.

Algorithm Procedure:

1. Check if the Queue is empty.
2. Return the value at the front index.

isFull

The isFull operation is used to check if the queue is full or not.

Algorithm Procedure:

1. Check if the number of elements in the queue (size) is equal to the capacity, if yes, return True.
2. Return False.

isEmpty

The isEmpty operation is used to check if the queue is empty or not.

Algorithm Procedure:

1. Check if the number of elements in the queue (size) is equal to 0, if yes, return True.
2. Return False.

Code Implementation of Queue in Data Structure

C++:

Java:

Python:

Output:

Limitations of Queue

Following are the limitations/disadvantages of a Queue data structure:

1. A queue is not readily searchable: You might have to maintain another queue to store the dequeued elements in search of the wanted element.
2. Traversal possible only once: The front most element needs to be dequeued to access the element behind it, this happens throughout the queue while traversing through it. In this process, the queue becomes empty.
3. Memory Wastage: In a Static Queue, the array's size determines the queue capacity, the space occupied by the array remains the same, no matter how many elements are in the queue.

Applications of Queue

A Queue data structure is used when things don't have to be accessed immediately but in FIFO (First In First Out) order. This property of the queue data structure makes queue applicable for the following situations:

1. Job Scheduling The computer schedules the job execution one by one. There are many jobs like a key press, a mouse click, etc. in the system. The jobs are brought in the main memory and are assigned to the processor one by one which is organized using a queue.

   For eg, Round Robin processor scheduling in queues.

2. Multiprogramming If there are multiple programs in the main memory, then that state is called multiprogramming. The programs in the main memory are organized in the form of queues, which are then called "Ready Queues". The processors will execute the programs by accessing them from the "Cache Memory" for simultaneous execution.

3. Operation on data structures Certain operations like BFS (Breadth First Search), and tree traversal uses Queue. The sequence of traversal of inputs is set using queues.

4. Buffer Space Queues are used in networking, during transmission of data from one point to another point.