Queue is a data-structure, which follows the FIFO. It means ‘First In First Out’. The element which goes first in the array should be the first to come out.
To achieve this process, we add elements at one end of the array and remove it from the other end.
Things that we need to do while implementing a queue using an array.
- Decide the size of queue, that needs to be created. We can create a fixed implementation or pass the size in a constructor.
- Acquire that much of memory, by creating an array of that size.
- We need two variables to track the locations, locations to add and remove the elements.
- create a function, which checks if a queue is empty.
- check a function which checks if queue is full
- a function to put/enqueue a value in the array
- a function to remove/dequeue a value from the array
#1 – size of the array
private final int MAX = 100;
#2 – acquiring the memory
private final int queue[] = new int[MAX];
#3 – variables to track the loactions of enquing and dequing
private int front = -1; private int rear = -1;
#4 – check if queue is empty
if front and rear are -1, then queue is empty. Because, there are no values in the queue, that’s why they can not point to any locations within the array.
private boolean queueIsEmpty() {
return (front == -1) && (rear == -1);
}
#5 – check if queue is full
If next location for adding any element is equal to index of front. Then the queue is full. While adding any element, we add one to rear index – point to next empty index. But, the next empty index is occupied, because front index is pointing to it.
private boolean queueIsFull() {
return (((rear + 1) % MAX) == front);
}
#6 – Enqueue – insert in a queue
we find the next empty index and put value in that index.
private void enqueue(final int value) {
if(queueIsFull()) {
throw new IllegalStateException("Queue is full!!!");
}
//Special case for first element in the queue
if(queueIsEmpty()) {
front = rear = 0;
} else {
rear = nextIndex(rear);
}
queue[rear] = value;
}
#7 – Dequeue – remove element from the queue
We simple decrement count of rear index by one. In real scenario, we will also free the memory. But, here the value is still in the array, which will get overwritten in next insertion.
private int dequeue() {
if(queueIsEmpty()) throw new IllegalStateException("Queue is empty!!!");
int value = queue[front];
if(queueHasOnlyOneElement()) {
front = rear = QUEUE_EMPTY;
} else {
front = nextIndex(front);
}
out.printf("Value popped %d \n" , value;)
return value;
}
Complete Code :-
import static java.lang.System.out;
public class QueueUsingArray {
private final int QUEUE_EMPTY = -1;
private final int MAX = 100;
private final int queue[] = new int[MAX];
private int front = -1;
private int rear = -1;
private int nextIndex(int currentIndex) {
return (currentIndex + 1) % MAX;
}
private boolean queueIsEmpty() {
return (front == -1) && (rear == -1);
}
private boolean queueIsFull() {
return (((rear + 1) % MAX) == front);
}
private boolean queueHasOnlyOneElement() {
return front == rear && front != QUEUE_EMPTY;
}
private int dequeue() {
if(queueIsEmpty()) throw new IllegalStateException("Queue is empty!!!");
int value = queue[front];
if(queueHasOnlyOneElement()) {
front = rear = QUEUE_EMPTY;
} else {
front = nextIndex(front);
}
out.printf("Value popped %d \n" , value;)
return value;
}
private void enqueue(final int value) {
if(queueIsFull()) {
throw new IllegalStateException("Queue is full!!!");
}
//Special case for first element in the queue
if(queueIsEmpty()) {
front = rear = 0;
} else {
rear = nextIndex(rear);
}
queue[rear] = value;
}
private void printFrontAndRear() {
out.printf("f :- %d, r :- %d \n" , this.front, this.rear);
}
private void printQueue() {
int f_temp = front;
while(f_temp != rear) {
out.printf("index :- %d, value :- %d \n", f_temp, queue[f_temp]);
f_temp = nextIndex(f_temp);
}
out.printf("index :- %d, value :- %d \n", f_temp, queue[f_temp]);
}
public static void main(String ... commandLineArguments) {
QueueUsingArray q = new QueueUsingArray();
//Enquing
out.println("Enqueue");
for(int i = 0; i < q.MAX; ++i) {
q.enqueue(i);
q. printFrontAndRear();
}
//dequing
out.println("Deque - 10");
for(int i = 0; i < 10; ++i) {
q.dequeue();
q. printFrontAndRear();
}
//Enqueue 2
out.println("Enqueue 2");
for(int i=0; i<2; ++i) {
q.enqueue(i);
q.printFrontAndRear();
}
out.println("Print the entire queue");
q.printQueue();
}
}
Output :-
This is a very long output. And going through it will make enqueue and dequeue a lot clear.
At first, we are only inserting elements in the queue, that’s why you see front remains 0 and rear goes till 99.
Enqueue f :- 0, r :- 0 f :- 0, r :- 1 f :- 0, r :- 2 f :- 0, r :- 3 f :- 0, r :- 4 f :- 0, r :- 5 f :- 0, r :- 6 f :- 0, r :- 7 f :- 0, r :- 8 f :- 0, r :- 9 f :- 0, r :- 10 f :- 0, r :- 11 f :- 0, r :- 12 f :- 0, r :- 13 f :- 0, r :- 14 f :- 0, r :- 15 f :- 0, r :- 16 f :- 0, r :- 17 f :- 0, r :- 18 f :- 0, r :- 19 f :- 0, r :- 20 f :- 0, r :- 21 f :- 0, r :- 22 f :- 0, r :- 23 f :- 0, r :- 24 f :- 0, r :- 25 f :- 0, r :- 26 f :- 0, r :- 27 f :- 0, r :- 28 f :- 0, r :- 29 f :- 0, r :- 30 f :- 0, r :- 31 f :- 0, r :- 32 f :- 0, r :- 33 f :- 0, r :- 34 f :- 0, r :- 35 f :- 0, r :- 36 f :- 0, r :- 37 f :- 0, r :- 38 f :- 0, r :- 39 f :- 0, r :- 40 f :- 0, r :- 41 f :- 0, r :- 42 f :- 0, r :- 43 f :- 0, r :- 44 f :- 0, r :- 45 f :- 0, r :- 46 f :- 0, r :- 47 f :- 0, r :- 48 f :- 0, r :- 49 f :- 0, r :- 50 f :- 0, r :- 51 f :- 0, r :- 52 f :- 0, r :- 53 f :- 0, r :- 54 f :- 0, r :- 55 f :- 0, r :- 56 f :- 0, r :- 57 f :- 0, r :- 58 f :- 0, r :- 59 f :- 0, r :- 60 f :- 0, r :- 61 f :- 0, r :- 62 f :- 0, r :- 63 f :- 0, r :- 64 f :- 0, r :- 65 f :- 0, r :- 66 f :- 0, r :- 67 f :- 0, r :- 68 f :- 0, r :- 69 f :- 0, r :- 70 f :- 0, r :- 71 f :- 0, r :- 72 f :- 0, r :- 73 f :- 0, r :- 74 f :- 0, r :- 75 f :- 0, r :- 76 f :- 0, r :- 77 f :- 0, r :- 78 f :- 0, r :- 79 f :- 0, r :- 80 f :- 0, r :- 81 f :- 0, r :- 82 f :- 0, r :- 83 f :- 0, r :- 84 f :- 0, r :- 85 f :- 0, r :- 86 f :- 0, r :- 87 f :- 0, r :- 88 f :- 0, r :- 89 f :- 0, r :- 90 f :- 0, r :- 91 f :- 0, r :- 92 f :- 0, r :- 93 f :- 0, r :- 94 f :- 0, r :- 95 f :- 0, r :- 96 f :- 0, r :- 97 f :- 0, r :- 98 f :- 0, r :- 99 Deque - 10 Value popped 0 f :- 1, r :- 99 Value popped 1 f :- 2, r :- 99 Value popped 2 f :- 3, r :- 99 Value popped 3 f :- 4, r :- 99 Value popped 4 f :- 5, r :- 99 Value popped 5 f :- 6, r :- 99 Value popped 6 f :- 7, r :- 99 Value popped 7 f :- 8, r :- 99 Value popped 8 f :- 9, r :- 99 Value popped 9 f :- 10, r :- 99 Enqueue 2 f :- 10, r :- 0 f :- 10, r :- 1 Print the entire queue index :- 10, value :- 10 index :- 11, value :- 11 index :- 12, value :- 12 index :- 13, value :- 13 index :- 14, value :- 14 index :- 15, value :- 15 index :- 16, value :- 16 index :- 17, value :- 17 index :- 18, value :- 18 index :- 19, value :- 19 index :- 20, value :- 20 index :- 21, value :- 21 index :- 22, value :- 22 index :- 23, value :- 23 index :- 24, value :- 24 index :- 25, value :- 25 index :- 26, value :- 26 index :- 27, value :- 27 index :- 28, value :- 28 index :- 29, value :- 29 index :- 30, value :- 30 index :- 31, value :- 31 index :- 32, value :- 32 index :- 33, value :- 33 index :- 34, value :- 34 index :- 35, value :- 35 index :- 36, value :- 36 index :- 37, value :- 37 index :- 38, value :- 38 index :- 39, value :- 39 index :- 40, value :- 40 index :- 41, value :- 41 index :- 42, value :- 42 index :- 43, value :- 43 index :- 44, value :- 44 index :- 45, value :- 45 index :- 46, value :- 46 index :- 47, value :- 47 index :- 48, value :- 48 index :- 49, value :- 49 index :- 50, value :- 50 index :- 51, value :- 51 index :- 52, value :- 52 index :- 53, value :- 53 index :- 54, value :- 54 index :- 55, value :- 55 index :- 56, value :- 56 index :- 57, value :- 57 index :- 58, value :- 58 index :- 59, value :- 59 index :- 60, value :- 60 index :- 61, value :- 61 index :- 62, value :- 62 index :- 63, value :- 63 index :- 64, value :- 64 index :- 65, value :- 65 index :- 66, value :- 66 index :- 67, value :- 67 index :- 68, value :- 68 index :- 69, value :- 69 index :- 70, value :- 70 index :- 71, value :- 71 index :- 72, value :- 72 index :- 73, value :- 73 index :- 74, value :- 74 index :- 75, value :- 75 index :- 76, value :- 76 index :- 77, value :- 77 index :- 78, value :- 78 index :- 79, value :- 79 index :- 80, value :- 80 index :- 81, value :- 81 index :- 82, value :- 82 index :- 83, value :- 83 index :- 84, value :- 84 index :- 85, value :- 85 index :- 86, value :- 86 index :- 87, value :- 87 index :- 88, value :- 88 index :- 89, value :- 89 index :- 90, value :- 90 index :- 91, value :- 91 index :- 92, value :- 92 index :- 93, value :- 93 index :- 94, value :- 94 index :- 95, value :- 95 index :- 96, value :- 96 index :- 97, value :- 97 index :- 98, value :- 98 index :- 99, value :- 99 index :- 0, value :- 0 index :- 1, value :- 1