## Introduction

A queue is a linear data structure where an item can be inserted from one end and can be removed from another end. We can not insert and remove items from the same end. Figure 1 shows the structure of a queue.

One end of the queue is called a *front* and the other end is called a *rear*. Items are inserted in the rear end and are removed from the front end. A queue is called a **F**irst **I**n **F**irst **O**ut data structure because the item that goes first comes out first.

A real-life example of a queue would be a queue of people in a bank. A cashier can serve only one person at a time. When a person comes while the cashier is serving another person, he/she needs to sit in the queue. If there is more than one person in the queue, the person needs to go to the rear end of the queue and wait for his/her turn.

The queue as an Abstract Data Type (ADT) has following operations.

**EnQueue**: It is also called a Push or an Insert operation. It inserts an item at the rear end of the queue.**DeQueue**: It is also called a Pop or a Remove operation. It removes the item from the front end of the queue.**front**: It returns the item at the front of the queue.**isEmpty**: It checks whether the queue is empty. If the queue is empty, we cannot do*front*and*dequeue*operations.

Details of these operations are described below.

## Operations on a queue

### EnQueue

The enqueue operation inserts a new item at the rear end of the queue. After the enqueue operation, the value of `rear`

is increased by 1. Figure 2 shows the enqueue operation.

In Figure 2, when an item *i4* is inserted, the `rear`

moves one step to the right but the `front`

remains in the same place. The algorithm for the insertion operation using an array is given below.

if (size of queue is > N) { print "Error: queue is full" return } rear = rear + 1 queue[rear] = item

### DeQueue

The dequeue operation removes the item at the front of the queue. When we remove the item at the front, we increase the value of `front`

. Figure 3 shows the dequeue operation.

In Figure 3, when the item *i1* is removed from the queue, we increase move the `front`

one step to the right whereas the `rear`

remains in the same place. The algorithm for dequeue operation using an array is given below.

if (rear == -1 and front == -1) { print "Error: queue is empty" return } item = queue[front] front = front + 1 return item

### front

The front operation returns the item at the front of the queue. This operation does not affect the position of both `rear`

and `front`

.

### isEmpty

The isEmpty operation checks whether the queue is empty or note. The queue is empty when the value of both the `rear`

and `front`

is -1 (initially we set both `front`

and `rear`

to -1).

## Illustration of enqueue and dequeue

Figure 4 shows the enqueue and dequeue operations and changes in the value of `rear`

and `front`

for some insertions and deletions.

Initially, we set both `rear`

and `front`

to -1. When the first item is inserted we increase the value of both `rear`

and `front`

by 1. After that for every enqueue operation, we increase the value of `rear`

by 1 keeping the `front`

as it is and for every dequeue operation, we increase the value of `front`

by 1 keeping the `rear`

as it is.

In both enqueue and dequeue operations, we increase the value of `front`

and `rear`

. We never decrease the value of both of them. For a limited sized queue (i.e. array implementation) this creates a problem when the `rear`

of the queue reaches the maximum index. Figure 5 illustrates this.

Figure 5 shows a queue that can hold 9 items. Currently, there are only 3 items. Even though the queue can still hold 6 more items, when we try to insert a new item, it says the queue is full. This is because the `rear`

of the queue is already in its maximum index position. This problem can be avoided using the *circular array*.

## Circular Queue

In a linear queue, when a new item is inserted, we increase the value of a `rear`

by 1 and insert the new item in the new position. However, in a circular queue, when a new item is inserted, we update the `rear`

as `rear = (rear + 1) % N`

where N is the capacity of the queue. This makes the queue circular. Let us illustrate this by an example.

Suppose we have a queue whose capacity is 7 i.e. it can hold at most 7 items. Suppose the `rear`

of the queue is at 7^{th} position and the `front`

of the queue is at 3^{rd} position which means the 1st and 2nd position are unused. Let us try to insert a new item. The new position of the `rear`

will be (7 + 1) % 7 = 1. Since the 1st position is unused, the item is inserted there. We do the similar for the `front`

. When an item is deleted, we update the `front`

as `front = (front + 1) % N`

. Figure 6 shows an example of a circular queue.

Since there is no boundary in a circular queue, how do we know when the queue is full? The queue is full when `rear`

and `front`

are adjacent to each other i.e. when `(rear + 1) % N == front`

, the queue is full. The implement of a circular queue is given in the implementation section.

## Complexities

All the operations of a queue take a constant time.

Operation | Complexity |
---|---|

enqueue | O(1) |

dequeue | O(1) |

front (Peek) | O(1) |

isEmpty | O(1) |

## Applications of a queue

- In shared resources like a printer, jobs are stored in a queue.
- In task CPU scheduling, tasks are stored in a queue.
- In many graphs algorithms like Breadth First Search, vertices stored in a queue.
- Interrupt handling. Interrupts are stored in a queue.
- Many messaging queue systems using the queue to store messages.

## Implementation in C, C++, Java, and Python

### Using array

1 | // Circular queue implementation in C using array |

1 | // C++ implementation of queue using array |

1 | // Java implementation of Queue using array |

### Using linked list

1 | // Queue implementation in C using linked list |

1 | // C++ implementation of queue using array |

1 | // Java implementation of Queue using array |

1 | # Python implementation of queue using linked list |