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.

package com.cb.queue;
import java.util.NoSuchElementException;
/*
* Queue using array
* Time: O(1)
* Space: O(N)
* */
public class QU1_ImplementQueueUsingArray {
private int start, end, maxSize, currentSize;
private int arr[];
public QU1_ImplementQueueUsingArray(int maxSize) {
this.arr = new int[maxSize];
this.start = -1;
this.end = -1;
this.maxSize = maxSize;
this.currentSize = 0;
}
public void add(int e) {
if (currentSize == maxSize) {
System.out.println("Queue is full !!!");
return;
}
if (end == -1) {
start = 0;
end = 0;
} else {
// to use array circularly
end = (end + 1) % maxSize;
}
arr[end] = e;
currentSize++;
}
public int peek() {
if (currentSize == 0)
throw new NoSuchElementException();
return arr[start];
}
public int poll() {
if (currentSize == 0)
throw new NoSuchElementException();
int e = arr[start];
// to use array circularly
start = (start + 1) % maxSize;
currentSize--;
return e;
}
public int size() {
return currentSize;
}
}
class Impl {
public static void main(String[] args) {
QU1_ImplementQueueUsingArray q = new QU1_ImplementQueueUsingArray(6);
q.add(4);
q.add(14);
q.add(24);
q.add(34);
System.out.println(q.peek());
System.out.println(q.size());
System.out.println(q.poll());
System.out.println(q.peek());
System.out.println(q.size());
}
}

Complexity

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

Related


Implementation of Stack data structure using Array

Implement Stack using Queue (using single queue)

Find the next greater element for every element in an array

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

Implement Queue using Stack in amortized O(1) time