Queue Data Structure and Implementation

Introduction

In 1837, Scottish historian Thomas Carlyle introduced a linear construct to address the people in a line, requesting to fulfill their needs and wants. The people followed specific rules that determined a way to choose from those on the waiting list. As the line of people increased like a tail, the structure was called a Queue (tail or cauda in Latin).

What is Queue?

A queue is a linear data structure from which the elements may be deleted at one end (FRONT) and inserted from another (REAR). It is also called the First In First Out (FIFO) data structure.

In other words, a queue is an unlimited, ordered collection of data elements maintained in sequential order. The capacity to store the number of data elements safely and ensure quick access is the size of the Queue. A Queue is said to be full if all the storage locations contain data elements. An element added to Full Queue results in an Overflow. A queue with no data element is said to be an Empty Queue, and the removal of any data element from an Empty Queue is impossible and causes an Underflow.

The insertion of a new data element is always at the REAR and does not affect the FRONT. The removal of all the data elements before the REAR element allows the removal of the REAR.

As the number of elements added to a Queue may be infinite, a Queue is an Abstract Data Type (ADT).

Here is a sample code to create Queue as an ADT

#define MAX 100

struct queue

{
 int front, rear;
 int element[MAX];
};
struct queue q;        

There are four types of queues in data structures

A descending priority queue allows the deletion of only the largest element.

Continue Reading