There are multiple types of Queue data structure. In this article, we will learn about FIFO, Double-Ended, and Priority Queue. We will also implement some common Queue operations including

  • Enqueue: adds an item into a queue

  • Dequeue: retrieves and removes an item from a queue

FIFO Queue

FIFO queue data structure is a collection of items in First In First Out (FIFO) order as items can only be added into the rear and removed from the front

You can implement a FIFO queue with either a linked list or an array. The following implementation example uses an array

import java.util.NoSuchElementException;

public class QueueByArray {  
    private int[] queue;
    private int front;
    private int rear;

    public QueueByArray(int capacity) {
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public void enqueue(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        queue[rear++] = x;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return queue[front++];
    }

    public int front() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return queue[front];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return rear == queue.length;
    }

    public int size() {
        return rear - front;
    }

    public static void main(String[] args) {
        QueueByArray myQueue = new QueueByArray(3);
        myQueue.enqueue(1);
        myQueue.enqueue(2);
        myQueue.enqueue(3);

        System.out.println(myQueue.front()); // 1
        System.out.println(myQueue.dequeue()); // 1
        System.out.println(myQueue.front()); // 2

        System.out.println(myQueue.size()); // 2
        System.out.println(myQueue.isEmpty()); // false
        System.out.println(myQueue.isFull()); // false
    }
}

Double-Ended Queue (Deque)

Deque is a collection where items can be added to or removed from either at the front or rear

You can implement a deque with either an array or a doubly-linked list. The following implementation example uses an array

import java.util.NoSuchElementException;

public class DequeueByArray {  
    private int[] dequeue;
    private int front;
    private int rear;

    public DequeueByArray(int capacity) {
        this.dequeue = new int[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public void enqueueFirst(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        for (int i = rear; i > front ; i--) {
            dequeue[i] = dequeue[i-1];
        }

        dequeue[front] = x;
        rear++;
    }

    public void enqueueLast(int x) {
        if (isFull()) {
            throw new IllegalStateException();
        }

        dequeue[rear++] = x;
    }

    public int dequeueFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[front++];
    }

    public int dequeueLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[rear--];
    }

    public int front() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[front];
    }

    public int rear() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        return dequeue[rear-1];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return rear == dequeue.length;
    }

    public int size() {
        return rear - front;
    }

    public static void main(String[] args) {
        DequeueByArray myQueue = new DequeueByArray(3);
        myQueue.enqueueFirst(1);
        myQueue.enqueueLast(2);
        myQueue.enqueueFirst(3);

        System.out.println(myQueue.front()); // 3
        System.out.println(myQueue.dequeueFirst()); // 3
        System.out.println(myQueue.front()); // 1

        System.out.println(myQueue.size()); // 2
        System.out.println(myQueue.isEmpty()); // false
        System.out.println(myQueue.isFull()); // false
    }
}

Priority Queue Data Structure

Priority Queue is a collection where items can be retrieved and removed by priority

You can implement a priority queue with either an array, a linked list, or a binary heap. The following implementation example uses a binary heap

public class PriorityQueueByHeap {  
    private MaxHeapByArray maxHeapByArray;

    public PriorityQueueByHeap(int capacity) {
        this.maxHeapByArray = new MaxHeapByArray(capacity);
    }

    public void enqueue(int x) {
        maxHeapByArray.push(x);
    }

    public int dequeue() {
        return maxHeapByArray.pop();
    }

    public int front() {
        return maxHeapByArray.peek();
    }

    public static void main(String[] args) {
        PriorityQueueByHeap myQueue = new PriorityQueueByHeap(5);
        myQueue.enqueue(7);
        myQueue.enqueue(2);
        myQueue.enqueue(3);
        myQueue.enqueue(1);
        myQueue.enqueue(9);

        System.out.println(myQueue.front()); // 9
        System.out.println(myQueue.dequeue()); // 9
        System.out.println(myQueue.front()); // 7
    }
}

MaxHeapByArray is defined in Heap Data Structure

Data Structure