Queue Data Structure

CSL 102; Data Structures; IIIT Nagpur; Created by: Dr. Aniket Pingley

Introduction Similar to the Stack ADT, a Queue is also a linear data structure. However, unlinke Stack, which follows LIFO order, the Queue ADT First In First Out (FIFO) order for data-operations, i.e., the data item stored first will be accessed first. In addition, unlike Stack, Queue supports insertion and removal/deletion operations at two different ends of the data structure. The insertion operation is performed at a position known as 'back', 'rear' or 'tail', and the deletion operation is performed at 'front' or 'head' of the data structure. The insertion operation is also referred as 'enqueue' and the removal operation as 'dequeue'.

Image source: http://www.btechsmartclass.com/

Basic Operations

Following operations can be performed on a stack:

• enqueue(): Insert element the back of the queue (if the queue is not full).
• dequeue(): Remove and return the element from the front of the queue (if the queue is not empty).
• front(): Get (return) the element at the front of the queue (without dequeuing).
• back(): Get (return) the element at the back of the queue.
• size(): Return the number of elements in the queue.
• isEmpty(): Return TRUE (1) if the queue is empty, otherwise return FALSE (0).
• isFull(): Return TRUE (1) if the queue is full, otherwise return FALSE (0). The MAX SIZE of the queue is set during initialization.

Animation for Queue ADT: https://www.cs.usfca.edu/~galles/visualization/QueueArray.html

Circular Queue

A severe limitation in the array-based implementation of Queue is encountered when the multiple dequeue operations results vacant spaces are in the beginning, which cannot be utilized since enqueue operation occurs at the 'back'. To overcome such limitations, the concept of the circular queue was introduced. Circular Queue is a linear data structure in which the operations are performed based on First In First Out (FIFO) order for data-operations. However, the indices of of the underlying array are reused once the enqueue operations causes the 'back' of the Queue to reach its maximum size. Pictographically, last position in the array is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

Image source: https://prepinsta.com/data-structures-algorithms/circular-queue/

Implementation of Queue ADT

• Link to header file - HERE
• Link to implementation - HERE