Queues in DSA

What is a Queue in DSA?

• A queue is a linear data structure that holds elements in a certain order. It accesses items using the FIFO (First In First Out) method.
• It can only be changed by adding data entities at one end or removing data entities at the other.
• The end where insertion occurs is known as the Rear, while the end where deletion occurs is known as the Front.
• This ordering guarantees that components are processed in the order in which they were added, much like a real-world queue or queue.

Basic Operations for Queue:

The main operations performed on a queue are:

• Enqueue(): This operation adds an element to the rear of the queue. The new element becomes the last element in the queue.

1. Check if the Queue is full.
2. Set the front as 0 for the first element.
3. Increase rear by 1.
4. Add the new element at the rear index.

• Dequeue(): This operation removes and returns the front element of the queue. The front element is the oldest in the queue.

1. Check if the Queue is empty.
2. Return the value at the front index.
3. Increase front by 1.
4. Set front and rear as -1 for the last element.

• Peek(): This operation retrieves the value of the front element without removing it from the queue. It allows you to examine the next element that will be dequeued.

1. Check if the Queue is empty.
2. Return the value at the front index.

• isEmpty(): This operation checks if the queue is empty. It returns true if there are no elements in the queue and false otherwise.

1. Check if the number of elements in the queue (size) is equal to 0, if yes, return True.
2. Return False.

Implementation of Queue Data Structure:

Array-based Queue:

• In this implementation, the queue is backed by an array. The elements are stored in a continuous block of memory.
• Enqueue operation adds an element to the end of the array.
• Dequeue operation removes the element from the front of the array by shifting all other elements.
• The size of the array determines the maximum capacity of the queue.
• The array-based implementation can suffer from inefficient memory usage when elements are dequeued and new elements are enqueued.

public class ArrayQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int size;
  
    public ArrayQueue(int capacity) {
        arr = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
  
    public void enqueue(int item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % arr.length;
        arr[rear] = item;
        size++;
    }
  
    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int item = arr[front];
        front = (front + 1) % arr.length;
        size--;
        return item;
    }
  
    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return arr[front];
    }
  
    public boolean isFull() {
        return size == arr.length;
    }
  
    public boolean isEmpty() {
        return size == 0;
    }
}

Linked List-based Queue:

• In this implementation, the queue is implemented using a linked list where each element contains a value and a reference to the next element.
• Enqueue operation adds a new element to the end of the linked list.
• Dequeue operation removes the element from the front of the linked list by updating the head reference.
• The linked list-based implementation allows for dynamic resizing and efficient memory usage.

public class LinkedListQueue {
    private class Node {
        int data;
        Node next;
  
        public Node(int data) {
            this.data = data;
        }
    }
  
    private Node front;
    private Node rear;
  
    public LinkedListQueue() {
        front = null;
        rear = null;
    }
  
    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }
  
    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return item;
    }
  
    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.data;
    }
  
    public boolean isEmpty() {
        return front == null;
    }
}

Types of Queues:

• Simple Queue: A simple queue follows the FIFO (First-In-First-Out) principle. The elements are added to the back of the queue, and the elements are removed from the front of the queue.
• Circular Queue:
  • A circular queue is an array-based implementation with a fixed size that wraps around.
  • It uses two pointers, front and rear, to keep track of the front and rear of the queue.
  • Enqueue operation adds an element to the rear of the queue, and the rear pointer is incremented.
  • Dequeue operation removes an element from the front of the queue, and the front pointer is incremented.
  • When the rear pointer reaches the end of the array, it wraps around to the beginning.
  • The circular queue implementation allows for efficient space utilization and avoids shifting elements during dequeue operations.

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
  
    public CircularQueue(int capacity) {
        queue = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
  
    public boolean isFull() {
        return size == queue.length;
    }
  
    public boolean isEmpty() {
        return size == 0;
    }
  
    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue.");
            return;
        }
        rear = (rear + 1) % queue.length;
        queue[rear] = item;
        size++;
    }
  
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1;
        }
        int item = queue[front];
        front = (front + 1) % queue.length;
        size--;
        return item;
    }
  
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return queue[front];
    }
}

• Priority Queue: A priority queue is a queue where each element is assigned a priority value. Elements with higher priority values are dequeued first. It can be implemented using various data structures such as binary heap, Fibonacci heap, or self-balancing binary search trees.

import java.util.Arrays;

public class PriorityQueue {

    private int[] queue;
    private int size;

    public PriorityQueue() {
        queue = new int[10]; // Initial capacity of the queue
        size = 0;
    }

    public void enqueue(int item) {
        if (size == queue.length) {
            // Queue is full, resize the array
            queue = Arrays.copyOf(queue, size * 2);
        }
        int position = findInsertionPosition(item);
        shiftElementsToRight(position);
        queue[position] = item;
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int item = queue[0];
        shiftElementsToLeft();
        size--;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private int findInsertionPosition(int item) {
        int position = 0;
        while (position < size && item > queue[position]) {
            position++;
        }
        return position;
    }

    private void shiftElementsToRight(int position) {
        for (int i = size - 1; i >= position; i--) {
            queue[i + 1] = queue[i];
        }
    }

    private void shiftElementsToLeft() {
        for (int i = 1; i < size; i++) {
            queue[i - 1] = queue[i];
        }
    }
}

• Deque (Double Ended Queue): A deque, or double-ended queue, is a queue-like data structure that allows insertion and removal of elements from both ends. It supports operations such as enqueue/dequeue from both the front and rear ends.

import java.util.NoSuchElementException;

class Node {
    int data;
    Node prev;
    Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class LinkedListDeque {
    private Node head;
    private Node tail;
    private int size;

    public LinkedListDeque() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    public void addLast(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }

    public int removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        int removedData = head.data;
        if (size == 1) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
        return removedData;
    }

    public int removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        int removedData = tail.data;
        if (size == 1) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return removedData;
    }

    public int getFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        return head.data;
    }

    public int getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        return tail.data;
    }
}

Space & Time Complexity:

Data Structure	Enqueue	Dequeue	Peek	Size	Space Complexity
Simple Queue	O(1)	O(1)	O(1)	O(1)	O(n)
Circular Queue	O(1)	O(1)	O(1)	O(1)	O(n)
Double Ended Queue	O(1)	O(1)	O(1)	O(1)	O(n)
Priority Queue	O(log n)	O(log n)	O(1)	O(1)	O(n)

Applications of Queue:

There are various applications of queues discussed as below.

1. Queues are widely used as waiting lists for a single shared resource like printer, disk, or CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) eg. pipes, file IO and sockets.
3. Queues are used as buffers in most applications like MP3 media players, CD players, etc.
4. Queues are used to maintain the playlist in media players in order to add and remove the songs from the playlist.
5. Queues are used in operating systems for handling interrupts.

Note: also read about Stack in DSA

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py