A Queue is a linear data structure in which deletions can only occur at one end, known as the **front**, and insertions can only occur at the other end, known as the **rear**. It is similar to the real-life queue where the first person entering the queue is the first person who comes out of the queue. Thus queues are also called **FIFO**(First In First Out) lists.

## Basic Operations of Queue

A queue allows the following basic operations:

**Enqueue**– Add new element to the end of the queue.**Dequeue**– Remove an element from the front of the queue.

Every queue includes two pointers, `FRONT`

and `REAR`

, which indicate the position where deletion and insertion can be performed. Initially, values of FRONT and REAR is set to -1.

#### Enqueue Operation

Inserting a new element in the position pointed by REAR is called the enqueue operation. We must check if the queue is full before insertion. After the enqueue operation the REAR is incremented by 1 and will point to the newly inserted element.

For inserting the first element in a queue, the value of FRONT has to be set to 0.

Consider a queue of size 5. Suppose we have to insert A, B, C, D and E into the queue. The following changes will be made to the queue.

#### Dequeue Operation

Deleting an element in the position pointed by FRONT is called the dequeue operation. We must check if the queue is empty before deletion. After the dequeue operation, the FRONT is incremented by 1.

After deleting the last element in a queue, the value of FRONT and REAR has to be set to 0.

Consider the following example where we dequeue elements one by one until the queue becomes empty.

## Representation of Queues

Queue is usually represented in the computer using a linear array or a one-way linked list.

### Array Representation of Queue

A queue can be represented in a program by using a linear array of elements and three pointer variables FRONT, REAR and MAX.

The queue is empty if `FRONT = REAR = -1`

. The queue is full if` FRONT =1 `

and `REAR = MAX - 1`

.

The size of the above queue is 5. It has 3 elements A, B and C. The FRONT, REAR and MAX pointers will have values 0, 2 and 5 respectively.

The algorithms for enqueue and dequeue operations are given below.

#### Algorithm: ENQUEUE(QUEUE, MAX, FRONT, REAR, ITEM)

Step 1: IF REAR = MAX-1 Write OVERFLOW Goto step 4 [END OF IF] Step 2: IF FRONT=-1 and REAR=-1 SET FRONT = REAR = 0 ELSE SET REAR = REAR + 1 [END OF IF] Step 3: SET QUEUE[REAR] = ITEM Step 4: EXIT

- Print overflow and exit if the queue is full.
- For adding first element make
`FRONT = 0`

. - Increment REAR by 1.
- Insert new element in the position pointed by REAR.

#### Algorithm DEQUEUE(QUEUE, MAX, FRONT, REAR, ITEM)

Step 1: IF FRONT = -1 OR FRONT > REAR Write UNDERFLOW ELSE SET ITEM = QUEUE[FRONT] SET FRONT = FRONT + 1 [END OF IF] Step 2: EXIT

- Print underflow and exit if the queue is empty.
- Return the value pointed by FRONT.
- Increment FRONT by 1.
- Set
`FRONT = REAR = -1`

for the last element.

### Linked Representation of Queues

The disadvantage of using an array to represent a queue is that the array must be specified to have a fixed size. If the array size cannot be known ahead of time, then the linked representation is used.

The HEAD pointer of the linked list is used as the FRONT. Also, use another pointer called REAR to store the address of the last element of the queue.

The algorithms for enqueue and dequeue operations are given below.

#### Algorithm: LINK_ENQUEUE

Step 1: Allocate memory for the new node and name it as PTR Step 2: SET PTR -> DATA = VAL Step 3: IF FRONT = NULL SET FRONT = REAR = PTR SET FRONT -> NEXT = REAR -> NEXT = NULL ELSE SET REAR -> NEXT = PTR SET REAR = PTR SET REAR -> NEXT = NULL [END OF IF] Step 4: END

#### Algorithm: LINK_DEQUEUE

Step 1: IF FRONT = NULL Write Underflow Go to Step 5 [END OF IF] Step 2: SET PTR = FRONT Step 3: SET FRONT = FRONT -> NEXT Step 4: FREE PTR Step 5: END

## Disadvantage of Queue

Look at the following queue.

You cannot insert a new value now, because the queue is completely full. Consider the following case: two consecutive deletions are made.

Even though there is enough space to hold a new element, the overflow condition still occurs since the condition `REAR = MAX – 1`

is still valid. This is a major drawback of a linear queue. A solution to this problem is to make the queue circular.

## Types of Queues

A queue data structure can be classified into the following types:

- Circular Queue.
- Priority Queue.
- Dequeue.

## Application of Queue

- Manage resource sharing such as CPU scheduling, disk scheduling..etc
- When data is sent and received between two processes asynchronously.
- Hadling of inrepputs in real time.
- Call waiting systems in call centers.