Queue Data Structure
In this article, I will cover the major aspects of the Queue data structure. I will cover the operations and their time and space complexities, use cases and implementations of this data structure. This material is aimed to quickly get you up and running with Queue before diving into problem solving with it.
This is a part of my data structures series. More topics I have covered:
So what is Queue?
Queue is a linear data structure that follows the FIFO (First In First Out) order of operations. Similar to Stack, the insertion and deletion operations need to be in constant O(1) time.
The major operations of Queue:
- Enqueue: Inserts an item to the queue
- Dequeue: Removes an item from the queue
- isEmpty: Checks if the queue is empty
- isFull: Checks if the queue is full
- display: Additional function to display the contents in the queue
Applications of Queue
Generally used in cases where we need to manage a group of data based on their order of arrival. Below are some use-cases.
- Serving requests on a shared resource. For example, when multiple users need to use a shared printer, their requests may be put in a queue to serve the first request before the second, and so on.
- In CPU Scheduling algorithms, use of queue is common.
- In real life scenario, like a call center phone system. The customers can be put into a queue based on their order of calling.
- Handling of interrupts in real-time systems.
FOUR types of Queue
Simple/Linear Queue: The basic queue where insertion takes place at rear end and removal occurs from front.
Circular Queue: This type is similar to a linear queue with the additional requirement that the last element should point to the first element, making a circular link. Circular queue is good for memory utilization. When the last position is full and if the first position is empty, we can insert in the first position, reducing space wastage. Also known as circular buffer or ring buffer.
Dequeue: Double Ended Queue or dequeue. Here, insertions and deletions can be performed from either the front or the rear. So it does not follow the FIFO order. Multiprocessor scheduling algorithms and storing a web browser’s history are some of this queue’s use cases. You can further read this answer from stack overflow.
Priority Queue: Its a special type of queue, where each element is associated with a priority and served according to that. If the priority is equal, then their order in the queue is taken into account. Insertions occur according to order of arrival and removal occurs based on priority. As heaps are preferred to implement a priority queue because of better performance, its not in the scope of this article. However, you can read about it here.
Implementation
We can implement a queue with an array, linked-list or with stacks. Since the enqueue and dequeue operations need to be in O(1), we have to keep this constraint in mind while designing our implementations. For the simplicity of understanding, I will be working with only integer data type. You can try implementing for other data types in addition to building a generic queue.
Simple Queue Implementation with Array
public class SimpleQueueWithArray {
private static int [] a;
private int size;
private int capacity;
private int front,rear;
public SimpleQueueWithArray(int capacity){
size = 0;
this.capacity = capacity;
a = new int[this.capacity];
front = -1;
rear = -1;
}
public boolean isEmpty(){
if(size==0){
return true;
}else{
return false;
}
}
public boolean isFull(){
if(size==capacity){
return true;
}else{
return false;
}
}
public void enQueue(int element){
if(isFull()){
System.out.println("Queue is full");
return;
}
else if(isEmpty()){
front = rear = 0;
}
else{
rear = rear+1;
}
a[rear] = element;
size++;
}
public int deQueue(){
if(isEmpty()){
System.out.println("Empty queue");
return -1;
}
//when only one element in queue
else if(front==rear){
int temp = a[front];
front = rear = -1;
size--;
return temp;
}
else{
int temp = a[front
front++;
size--;
return temp;
}
}
public int getFront(){
if(isEmpty()){
return -1;
}else{
return a[front];
}
}
public int getSize(){
return size;
}
public void display(){
if(isEmpty()){
System.out.println("Queue is Empty");
}else{
for(int i=front;i<=rear;i++){
System.out.print(a[i]+" ");
}
}
}
}Simple Queue Implementation with Linked List
It is essential to understand here that, as we insert elements to the queue, we need to update the rear and set it as the last element, so that we don’t have to traverse the whole linked list to insert it at last.
We first create our node class!
public class Node{
private int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}public class SimpleQueueWithLL {
private Node front;
private Node rear;
public SimpleQueueWithLL(){
this.front = null;
this.rear = null;
}
public void enQueue(int data){
Node n = new Node(data);
if(isEmpty()){
front = rear = n;
}
else{
Node temp = rear;
temp.next = n;
rear = n; //updating the rear
}
}
public int deQueue(){
if(isEmpty()){
System.out.println("Empty Queue");
return -1;
}
else if(front==rear){
int temp = front.data;
front = rear = null;
return temp;
}
else{
int temp = front.data;
front = front.next;
return temp;
}
}
public boolean isEmpty(){
if(front==null && rear==null){
return true;
}else{
return false;
}
}
public int front(){
if(!isEmpty()){
return front.data;
}else{
return -1;
}
}
public void display(){
Node temp = front;
if(front==null){
System.out.println("Nothing to show");
}else{
while(temp!=rear){
System.out.print(front.data+" ");
temp = temp.next;
}
System.out.println(temp.data);
}
}
}Circular Queue Implementation with Array
public class CircularQueueWithArray {
private static int [] a;
private int front,rear;
//for circular traversal, taking the capacity is essential!
private int capacity;
CircularQueueWithArray(int capacity){
this.capacity = capacity;
a = new int[capacity];
this.front = -1;
this.rear = -1;
}
public boolean isEmpty(){
if(front==-1 && rear==-1){
return true;
}else{
return false;
}
}
public void enQueue(int element){
if(isEmpty()){
front = rear = 0;
}
else if(isFull()){
System.out.println("Overflow");
return;
}
else{
rear = (rear+1)%capacity; // circular traversal
}
a[rear] = element;
}
public int deQueue(){
if(isEmpty()){
System.out.println("Underflow");
return -1;
}
else if(front==rear){
int temp = a[front];
front=rear=-1;
return temp;
}else{
int temp = a[front];
front =(front+1)%capacity;
return temp;
}
}
public int front(){
if(!isEmpty()){
return a[rear];
}else{
return -1;
}
}
public boolean isFull(){
if((rear+1)%capacity==front){
return true;
} else{
return false;
}
}
public void display(){
for(int i=front;i!=rear;i=(i+1)%capacity){
System.out.print(a[i]+" ");
}
//printing the remaining element
System.out.println(a[rear]);
}
}Circular Queue Implementation with Linked List
This is the same as implementing a linear queue with linked lists. However, we have to keep in mind the circular aspect while writing the implementation. We need to connect the rear to the front in the deQueue() and enQueue() functions. I am providing the code for the two operations, in addition a slightly changed display() method, but the rest will be the same as above implementation with linked list.
public void enQueue(int element){
Node node = new Node(element);
if(isEmpty()){
front=rear=node;
}
else{
Node temp = rear;
temp.next=node;
rear = node;
rear.next = front;
}
}
public int deQueue(){
if(isEmpty()){
System.out.println("Underflow");
return -1;
}else if(front==rear){
int temp = front.data;
front = rear =null;
return temp;
}else{
int temp = front.data;
front = front.next;
rear.next = front;
return temp;
}
}
public void display(){
if(!isEmpty()){
Node temp = front;
do{
System.out.print(temp.data+" ");
temp = temp.next;
}while(temp!=rear);
System.out.println(temp.data);
}
}Dequeue Implementation
While it is better to implement a dequeue with a circular array and modulo operations, I chose not to use that for readability. You can practice with a circular array too!
public class Dequeue{
static int [] a;
private int front,rear;
private int size;
public Dequeue(int size){
this.size = size;
a = new int[size];
front = -1;
rear = -1;
}
public void enQueueFront(int element){
if(isEmpty()){
front=rear=0;
}else if(isFull()){
System.out.println("Queue is Full");
return;
}else if(front==0){
front = size-1;
}
else{
front--;
}
a[front]=element;
}
public int deQueueFront(){
if(isEmpty()){
System.out.println("Nothing in the Queue");
return -1;
}
else if(front==rear){
int temp = a[front];
front=rear=-1;
return temp;
}
else if(front==size-1){
int temp = a[front];
front = 0;
return temp;
}else{
int temp = a[front];
front++;
return temp;
}
}
public void enQueueRear(int element){
if(isFull()){
System.out.println("Queue is Full");
return;
}
else if(isEmpty()){
front = rear = 0;
}
else if(rear==size-1){
rear = 0;
}else{
rear++;
}
a[rear] = element;
}
public int deQueueRear(){
if(isEmpty()){
System.out.println("Nothing in the Queue");
return -1;
}
else if(front==rear){
int temp = a[rear];
front=rear=-1;
return temp;
}
else if(rear==0){
int temp = a[rear];
rear = size-1;
return temp;
}
else{
int temp = a[rear];
rear--;
return temp;
}
} private boolean isEmpty() {
if(front==-1 || rear==-1){
return true;
}else{
return false;
}
} private boolean isFull() {
if((front==0 && rear==size-1) || (front==rear+1)){
return true;
}else{
return false;
}
}
void display(){
if(isEmpty()){
System.out.println("Nothing in the Queue");
}else{
int i=front;
while(i!=rear){
System.out.print(a[i]+" ");
i = (i+1)%size;
}
System.out.println(a[rear]);
}
}
}
Queue Implementation with Stack
We can implement a queue using two stacks. Idea is, we will use one stack as a push-stack and the other as a pop-stack, to ensure the FIFO order. In this type of implementation, we can either make the enQueue() operation costly or the deQueue() operation costly. The code below makes the enQueue() operation perform in O(1), and the amortized analysis of deQueue() will be θ(1). You can read more about this implementation here.
public class QueueWithStack {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public QueueWithStack(){
this.pushStack = new Stack<>();
this.popStack = new Stack<>();
}
public void enQueue(int element){
pushStack.push(element);
}
public int deQueue(){
if(popStack.isEmpty()){
if(pushStack.isEmpty()){
System.out.println("Nothing in the Queue");
return -1;
}else{
while(!pushStack.isEmpty()){
popStack.push(pushStack.pop());
}
int temp = popStack.pop();
return temp;
}
}else{
int temp = popStack.pop();
return temp;
}
}
}Conclusion
To summarize, we have learnt about the basic operations of queue, the application of this FIFO data structure, the different types of queue and their implementations with arrays, linked lists and stacks.
Please note that the code above has been written based on certain assumptions and are always subject to optimization. While this article can get you up to speed with queue data structure, true mastery will only come by diving into problem solving. Good luck and thanks for reading.
