Implementation of Queue data structure using Array

Posted by on Mar 31, 2024

Implement Queue Data Structure using Array with all functions like poll(), add(), peek(), size() etc.

Note: A queue is a data structure that follows the FIFO (First-In, First-Out) approach.


Solutions

Method 1: In O(1) time and O(n) space

A queue works on the principle of first in, first out, so we have to keep track of the "start" and "end" of the queue.

Initially, "start" and "end" will both point to "-1". All additions will be done at "end" and "deletion/poll" will be performed at "start".

Add an element in the queue by increasing the end by (end + 1) % maxSize.

To poll, make sure currentSize is not equal to zero. If it is not, return element at start and increase start's value by start+1 % maxSize.

Complexity

The time complexity of this solution is O(1) and space complexity is O(N).

Related


Implement Stack using Queue (using single queue)

Implement Queue using Stack in amortized O(1) time

Implementation of Stack data structure using Array

Find the next greater element for every element in an array

Find the next greater element for every element in a circular array