Queue Data Structure

In this article, we are going to understand Queue Data Structures. We will go over the benefits and operations of the queue data structure. We will dive into their visual representation and at last, we will see how to implement Queue in Java.

Advertisements

1. Queue Data Structure

A stack is a FIFO (first-in-first-out) principle-based data structure; it maintains two pointers “FRONT” where the elements would be removed and “REAR” where the elements would be inserted. You can think of a queue of people for movie tickets as a Queue data structure; the first person in the queue would get the ticket first and it would add any new person to the last. Similarly, an element will be added at the rear of the Queue and deleted from the front of the Queue.

I define a Queue with a capacity and it will store max those many elements

1.1. Queue Basic Operations.

  • Enqueue: To add an element at the rear of the queue.
  • Dequeue: To remove an element from the front of the queue.
  • Peek: To get the front element without removing it.
  • IsEmpty: To check if the queue is empty.
  • IsFull: To check if the queue is full.

Here is a visual representation of Queue data structure, and its operations for a better understanding.

queue data structure

Let’s look at some of the important operations of the Queue

1.2. Enqueue Operation

  • Check if queue is full or not.
  • Show queue full message / overflow error to the application.
  • Add element to the tail and increase the size.

1.3. Deque Operation.

  • Show empty message/ underflow error if queue is empty.
  • If queue is not empty, deque the element from front and increment the head.

2. Implementing of Queue Data Structure

There are multiple way to implement a Queue in Java. We can use Array, Linked List or even the Stack. Array is the easiest one but doesn’t have the dynamic array properties. Linked List is a good option, but we need to keep in mind the overhead of link management and dynamic array. Let’s see how to implement a queue in Java.

Advertisements
Advertisements
package com.javadevjournal.queue;

class MyQueue {
    private int[] array;
    private int front;
    private int rear;
    private int capacity;
    private int size;

    MyQueue(int size) {
        array = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        this.size = 0;
    }

    /**
     * dequeue from queue
     */
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("Can't dequeue, Queue is empty");
            return;
        }
        System.out.println("Dequeue:" + array[front]);
        front = (front + 1) % capacity;
        size--;
    }

    /**
     * enqueue an item to the queue
     * @param item
     */
    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Can't enqueue, Queue is full");
            return;
        }
        System.out.println("Enqueuing:" + item);
        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;
    }

    /**
     * @return the size of the queue
     */
    public int size() {
        return size;
    }

    /**
     * checks if queue is empty
     * @return
     */
    public Boolean isEmpty() {
        return (size() == 0);
    }

    /**
     * check if queue is full
     * @return
     */
    public Boolean isFull() {
        return (size() == capacity);
    }

    /**
     * main method
     * @param args
     */
    public static void main(String[] args) {
        MyQueue queue = new MyQueue(3);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        System.out.println("The queue size is " + queue.size());
        queue.enqueue(5);
        System.out.println("The queue size is " + queue.size());
        queue.dequeue();
        System.out.println("The queue size is " + queue.size());
    }
}

This program is for giving your overview of the data structure. For production, consider using Queue available in JDK

To check if the Queue is empty, we are using the isEmpty() method from our implementation.

/**
* checks if queue is empty
* @return
*/
public int isEmpty() {
   return size;
}

We will use the isFull() method to check if Queue is full

/**
* @return the size of the queue
*/
public int size() {
   return size;
}

3. Queue Applications

The Queue data structure is helpful every time we need to arrange items in the order they came in, also take out the first item while other wait in the queue. Here are some of the important applications of Queue.

  1. A Queue is used for asynchronous calls between software services.
  2. For Tree/Graph Breadth-First Search.
  3. Used for waiting lists for operating system resources.
  4. A Queue is used in many music apps to maintain the order of songs.

4. Queue Data Structure Time Complexity

With Queue, add and removal are very clear. We know it will add a new element at the end of the Queue while it will remove the element on the front of the queue first. Here is the time complexity for Queue

OperationTime Complexity
EnqueueO(1)
DequeueO(1)
AccessO(n)
SearchO(n)
SpaceO(n)

5. Difference Between Stack and Queue Data Structure

StackQueue
It’s a LIFO based data structureIt is a FIFO based Data Structure
Only one end “Top” is used for both insertion and deletion of the elementsInsertion and deletion happen at a different end of the queue. Insertion happens from rear and deletion from front
Insertion is called “push” and deletion is called “pop” operationInsertion is called “enqueue” and deletion is called “dequeue” operation
We used it for solving problems with “recursion”It is used for sequential processing
Think it as a vertical collection of itemsThink it as a horizontal collection of items
No variant of a stackQueue has a circular queue, double-ended queue and priority queue

Summary

  • In this article, we have learned what is a queue data structure.
  • We have learned basic operations of the queue.
  • Java implementation of the queue.
  • we have understood the high-level difference between the stack and the queue

The source code for this article and other from our data structure series are available on our GitHub repository.

Advertisements