Queue in Data Structure

What is Queue?

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.

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.

Working of Queue

We can use queue to perform its main two operations: Enqueue and Dequeue, other operations being Peek, isEmpty and isFull.

Queue operations

Enqueue

The Enqueue operation is used to add an element to the front of the queue.

Steps of the algorithm:

1. Check if the Queue is full.
2. Set the front as 0 for the first element.
3. Increase rear by 1.
4. Add the new element at the rear index.

Dequeue

The Dequeue operation is used to remove an element from the rear of the queue.

Steps of the algorithm:

1. Check if the Queue is empty.
2. Return the value at the front index.
3. Increase front by 1.
4. Set front and rear as -1 for the last element.

Peek

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

Steps of the algorithm:

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.

Steps of the algorithm:

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.

Steps of the algorithm:

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

Implementation of Queue Data Structure (C++, Python, Java)

We will be implementing the Queue data structure using an array in C++ and Java, and list in Python.

Queue Implementation in C++ 17

Implementing the Queue data structure in C++ with the help of an array.

Code

Output

In the above example, we are implementing a static queue data structure with of capacity 1000 with the help of an array in C++ using switch case. The static stack implementation has the following operations: enqueue, dequeue, peek, isEmpty, and isFull.

Examples

Let us discuss all the operations of the Queue data structure using code snippets (without implementing the operations, refer to the implementation section for completing the code) given below:

Adding and Removing Elements in the Queue

To add an element at the front of the queue, we can use the Enqueue operation.

Code (C++ 17)

Output

In the above examples, we are enqueueing an element at the rear of the queue, and then dequeueing the foremost element of the queue.

Accessing the Front of the Queue

The front of the queue is the first element to enter the queue. We will access the front most element of the queue using the Peek operation.

Code (C++ 17)

Output

In the above examples, we are accessing the front most element of the queue.

Checking If the Queue is Empty or Not

To check if the queue is empty or not, we can use the isEmpty operation discussed in the implementation section above.

Code (C++ 17)

Output

In the above examples, we are checking if the queue is empty or not.

Checking If the Queue is Full or Not

To check if the queue is empty or not, we can use the isEmpty operation discussed in the implementation section above.

This operation can only be used with static queues (C++ and Java implementation).

Code (C++ 17)

Output

In the above examples, we are checking if the queue is full or not.

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 the transmission of data from the source machine to the destination.