What are Queues?

Queues are very important linear data structures that help in solving structural problems in all programming languages. Queues can be thought of as physical queues in front of ticket stations. A queue might have many people in it at a time. The person that enters the queue first gets served first. If someone enters the queue last, he/she will consequently be served last. In Java as well, the queue data structures work in a similar fashion. The algorithm that queues follow is commonly stated as FIFO (First In First Out).

How are Queues different from Stacks?

The fundamental difference lies in the entry and exit points of the two data structures. As mentioned above, a new element in a queue is added to the end while a new element in a Stack is added at the top. Therefore, Stacks use the FIFO (First In First Out) mechanism while Queues use FIFO (First In First Out).

Various Operations in Queues

• Enqueue – Enqueue is the process of adding new elements to a queue. If the queue is already full, an error message is displayed that reads Queue Overflow.
• Dequeue – Dequeue is the process of removing elements from an existing queue. If the queue is empty, an underflow message is displayed. While enqueue takes place at the end of the queue, dequeue takes place at the start of the queue.
• Front – Similar to the peek option, this operation when invoked, returns the first element in the queue.
• Rear – This operation returns the last element of the queue.

Both front and rear are also used as variables to control the entry and exit of elements in a queue. These act as indices when using arrays and links when using linked lists.

Implementation of Queues using Arrays

Queues can be implemented in Java using Arrays and Linked Lists. The following code below will show the array interpretation of Arrays.

//The main queue class that has codes for all the various operations
class Queue
{
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity)
{
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
// This is a condition to check whether the queue is full. Returns true if full or else false.
boolean isFull(Queue queue)
{
return (queue.size == queue.capacity);
}

boolean isEmpty(Queue queue)
{
return (queue.size == 0);
}
//To add elements to the queue.
void enqueue(int item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}
// Method to remove an item from the queue.
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
return item;
}
// This is a method that returns the front index 
{
if (isEmpty(this)) return Integer.MIN_VALUE;
return this.array[this.front];
}
// Method to get rear of queue int rear()
{
if (isEmpty(this)) return Integer.MIN_VALUE; return this.array[this.rear];
}
}
// Main Class
public class Test { public static void main(String[] args)
{
Queue queue = new Queue(1000);
queue.enqueue(100);
queue.enqueue(50);
queue.enqueue(200);
queue.enqueue(300);
System.out.println(queue.dequeue() + " dequeued from queue\n");
System.out.println("Front item is " + queue.front());
System.out.println("Rear item is " + queue.rear());
}
}

OUTPUT

100 enqueued to the queue
50 enqueued to the queue
200 enqueued to the queue
300 enqueued to the queue
100 dequeued from queue
Front item is 50
Rear item is 300

Time Complexity

All the various operation of queues has the same time complexity that is O(1) i.e. Enqueue, Dequeue, Front, and Rear.