Queue

What is a queue?

Queue is an abstract data structure that follows a particular order in which operations are performed on it. The method in which those operations are done is called as First-In-First-Out (or Last-In-Last-Out). The operations of insertion and deletion are called as Enqueue and Dequeue respectively.

Let’s dive deep into queue

Our data structure queue can be easily related with their counterparts in real world queues like a ticket counter or a line to ride a roller coaster.

A good example would be a traffic toll booth where the vehicle which comes in first is allowed to pay up the necessary fees and then proceed, while the following vehicles which come later can continue to line up one behind the other and exit in an orderly manner.

Queue behaves in a similar manner which we term as First-In-First-Out (FIFO).

What features does it provide?

1. Queue is like a line at a ticket counter where the person who comes in first will get its ticket first
2. Operations that can be done:
   1. Enqueue: inserting a new element.
   2. Dequeue: removing an existing element.
3. Queue is said to be in an Overflow State when it is full, the operation enqueue cannot be performed during this state.
4. Queue is said to be in an Underflow State when it is empty, the operation dequeue cannot be performed during this state.

Types of queue:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue

Where do we use queue?

• Queues are used in most of the Operating Systems (OS) for Operation Scheduling and CPU Scheduling.
• Breadth First Search (BFS) algorithm uses queues to traverse a tree or a graph.
• Dijkstra’s shortest path algorithm implementation makes use of priority queues.

How to implement?

Queues can be implemented by using arrays or even linked-lists. We will be using an array with front and rear pointer to perform operations.

Rear pointer points to the last element. Front pointer points to the first element.

enqueue() operation:

1. Check if the queue is full.
2. If the queue is full, print out an error stating “Queue is in an Overflow State.” and exit the function.
3. If the queue is not full then, increase the rear pointer by one.
4. Add the element at the location where the rear pointer is pointing.

dequeue() operation:

1. Check if the queue is empty.
2. If the queue is empty, print out an error stating “Queue is in an Underflow State.” and exit the function.
3. If the queue is not full, increment the front pointer to point to the next element.
4. Delete the first element and reduce the array size by one.

Let’s Code

To code in any language other than C++,  Click here 

C++ program to implement queue: