A queue is a linear data structure that follows an order i.e FIFO(First In First Out), where the element which is inserted at the first will come out first.
Unlike Stack, while implementing a queue, an element is inserted from one end and removed from another end.
Basically, there are 4 basic operations that are performed in the queue:
- Enqueue: Addition of an element to the queue.
- Dequeue: Removal of an element from the queue.
- Front: Get the front element from the queue.
- Display: Print all element of the queue.
In this example, we’ll see how to implement a queue using an array:
1. Java
public class QueueImpl {
int[] queueArray;
int front, rear, maxSize, nItems;
public QueueImpl(int size) {
this.queueArray = new int[size];
this.maxSize = size;
this.front = 0;
this.rear = -1;
this.nItems = 0;
}
public void insert(int value) {
if(rear == maxSize - 1) { // if reached end of array while inserting. Set rear to -1 so that insertion can began from First index.
rear = -1;
}
queueArray[rear++] = value;
nItems++;
}
public void retrieve() {
System.out.println(Arrays.toString(queueArray));
}
public int remove() { // remove element from front of the queue.
int firstElement = queueArray[front];
front++;
if(front == maxSize) { // here we reached at last index of array.
front = 0;
}
nItems--;
return firstElement;
}
public int peekFront() {
return queueArray[front];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
}
Performing Operations:
public class QueueApp {
public static void main(String[] args) {
QueueImpl impl = new QueueImpl(5);
impl.insert(1);
impl.insert(2);
impl.insert(3);
impl.insert(4);
impl.insert(5);
impl.retrieve();
}
}
Output:
1 2 3 4 5
Queue Time Complexity:
The time complexity of the operations performed on Queue totally depends on how you implemented the Queue. Based on the above implementation below is the worst time complexity.
- Enqueue: O(1) time
- Dequeue: O(1) time
- Display: O(N) time
- Size: O(1) time.
Complete Java Solutions can be found here: Github Link