Implementation of Queue Data Structure 2022 - Programmrs

Queue

A queue is an ordered collection of items from which items may be deleted at one end called the Front of the queue and into which items may be inserted at the other end called the Rear of the queue.

Queue follows the First In First Out (FIFO) Rule- the element which is inserted first is the term that gets out first.

Queue Operations

The Queue is an Abstract Data Type (ADT) that allows performing the following operations:

• Enqueue: It is used to add an item to the rear of the queue
• De queue: It is used to remove an item from the front of the queue
• IsFull: Check if the queue is Full
• IsEmpty: Check if the queue is Empty
• Peek: Get the element at the front of the queue

The initial value of Front is 0 and Rear is -1.

Algorithm for Enqueue and Dequeue Operation

ENQUEUE

1. Start

2. If (rear = = MaxSize -1)

Printf(“queue overflow”);

3. Else

If (front = = -1)

Front = 0;

Rear = rear + 1;

Queue [rear] =item;

4. Stop

DEQUEUE

1. Start 
2. If (front = = -1)|| (front >rear) 
 Printf (“Queue under flow”);
 Return;
 3. Else 
Printf (“Element detected from queue”, queue [front]); 
front = front +1; 
4. Stop

Working of Queue

Queue operations work as follows:

1. Two pointers FRONT and REAR
2. FRONT track the first element of the queue
3. REAR track the last element of the queue
4. Initially, set the value of FRONT and REAR to -1

Problems with Linear Queue

As items are removed from the queue, both front and rear indices are increased. The storage space at the beginning of the queue is discarded and never used again. Hence, the queue is considered full even though there is space at the beginning of the queue.

Time Complexity Analysis

The complexity of en queue and dequeue operations in a queue using an array is O(1).

Applications of Queue

1. CPU scheduling, Disk Scheduling
2. When data is transferred asynchronously between two processes. The queue is used for synchronization. For example IO Buffers, pipes, file IO, etc
3. Handling of interrupts in real-time systems.
4. Call Center phone systems use Queues to hold people calling them in order.