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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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).