QUEUES

Queues are linear data structures that follow the First In First Out (FIFO) principle. Elements are added to the rear end of the queue, and removed from the front end of the queue. Queues are used to model real-world scenarios, such as customer service lines, printing jobs, and messaging applications. They can be implemented using an array, a linked list, or a circular buffer, among other data structures. Some common operations on queues include:

Enqueue: Adds an element to the rear end of the queue.
Dequeue: Removes and returns the front element of the queue.
Peek: Returns the front element of the queue without removing it.
IsEmpty: Returns true if the queue is empty, and false otherwise.
Size: Returns the number of elements currently in the queue.

Queues can also be implemented with priority, where elements have a priority value that determines their order in the queue. In this case, the element with the highest priority is always at the front of the queue. Priority queues are commonly used in computer science for scheduling tasks and event handling.

ARRAY BASED QUEUES

An array-based queue is a data structure that uses an array to implement the basic operations of a queue. A queue is a collection of elements that supports adding elements to the back and removing elements from the front. An array-based queue uses an array to store the elements of the queue and two pointers, one that points to the front of the queue and another that points to the back of the queue.

The basic operations of a queue include:

enqueue - This operation adds an element to the back of the queue. To do this, we first check if the queue is full, and if so, we resize the array. We then increment the back pointer and add the new element to the end of the array.
dequeue - This operation removes the element at the front of the queue. To do this, we first check if the queue is empty, and if so, we return an error. We then return the element at the front of the queue and increment the front pointer.
isEmpty - This operation checks if the queue is empty. It returns true if the front pointer is equal to the back pointer.
isFull - This operation checks if the queue is full. It returns true if the back pointer is equal to the size of the array.

An array-based queue is a simple and efficient data structure that can be used in a variety of applications. However, one limitation of this data structure is that the size of the array must be fixed in advance, which can lead to inefficiencies if the queue size exceeds the capacity of the array. To overcome this limitation, a circular buffer or dynamic resizing can be used to improve the efficiency of an array-based queue.

Here's an implementation of an array-based queue in Java that uses generics:


public class ArrayQueue<T> {
    private T[] arr;
    private int front, back;
    
    public ArrayQueue(int capacity) {
        arr = (T[]) new Object[capacity];
        front = back = 0;
    }
    
    public void enqueue(T item) {
        if (isFull()) {
            resize();
        }
        arr[back++] = item;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new
        NoSuchElementException("Queue is empty");
        }
        T item = arr[front++];
        if (isEmpty()) {
            front = back = 0;
        }
        return item;
    }
    
    public boolean isEmpty() {
        return front == back;
    }
    
    public boolean isFull() {
        return back == arr.length;
    }
    
    private void resize() {
        int size = back - front;
        T[] newArr = (T[]) new Object[2 * arr.length];
        System.arraycopy(arr, front, newArr, 0, size);
        arr = newArr;
        back = size;
        front = 0;
    }
}

In this implementation, the T type parameter is used to represent the type of element stored in the queue. The arr field is an array of type T that stores the elements of the queue. The front and back fields are integers that represent the indices of the front and back of the queue.

The enqueue() method adds an element to the back of the queue. If the queue is full, the resize() method is called to double the size of the array. The new element is added to the back index of the array.

The dequeue() method removes the element at the front of the queue. If the queue is empty, a NoSuchElementException is thrown. The element at the front index is returned and the front index is incremented. If the queue becomes empty after the element is removed, the front and back indices are reset to 0.

The isEmpty() and isFull() methods return true if the queue is empty or full, respectively.

The resize() method doubles the size of the array and copies the elements from the old array to the new array. The front index is set to 0 and the back index is set to the number of elements in the queue.

LINKED LIST BASED QUEUES

A linked list based queue is a data structure that uses a linked list to implement the basic operations of a queue. A queue is a collection of elements that supports adding elements to the back and removing elements from the front. A linked list based queue uses a linked list to store the elements of the queue and two pointers, one that points to the front of the queue and another that points to the back of the queue.

A linked list based queue is a simple and efficient data structure that can be used in a variety of applications. Unlike an array-based queue, the size of the queue is not limited by the data structure itself, as the linked list can dynamically grow as new elements are added to the queue. However, one potential drawback of a linked list based queue is that the memory allocation for each node can lead to inefficiencies in some scenarios.

Here's an example implementation of a linked list based queue in Java:


public class LinkedListQueue<T> {
    private Node<T> front, back;
    
    public LinkedListQueue() {
        front = back = null;
    }
    
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);

        if (isEmpty()) {
            front = back = newNode;
        } else {
            back.next = newNode;
            back = newNode;
        }
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new
        NoSuchElementException("Queue is empty");
        }
        T item = front.item;
        front = front.next;
        if (front == null) {
            back = null;
        }
        return item;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
}

In this implementation, the T type parameter is used to represent the type of element stored in the queue. The front and back fields are nodes that represent the front and back of the queue, respectively.

The enqueue() method adds an element to the back of the queue. If the queue is empty, a new node is created with the element to be added, and both the front and back pointers are set to point to the new node. Otherwise, a new node is created and added to the end of the linked list, and the back pointer is updated to point to the new node.

The dequeue() method removes the element at the front of the queue. If the queue is empty, a NoSuchElementException is thrown. The element at the front of the queue is returned, and the front pointer is updated to point to the next node in the linked list. If the front pointer becomes null after the element is removed, the back pointer is also set to null, indicating that the queue is empty.

The isEmpty() method checks if the queue is empty by checking if the front pointer is null.

This implementation is simple and easy to understand, but it has some limitations. For example, the dequeue() method can throw an exception if the queue is empty, which may not be ideal in all scenarios. Additionally, this implementation does not support removing elements from the back of the queue, as there is no direct pointer to the node before the back of the queue. However, these limitations can be addressed by modifying the implementation to suit specific use cases.

PRIORITY QUEUES

A priority queue is a type of queue where each element has a priority associated with it, and elements are dequeued based on their priority. Elements with higher priority are dequeued first, while elements with lower priority are dequeued later. Priority queues are often used in algorithms where elements must be processed in a particular order, such as graph traversal algorithms or scheduling algorithms.

There are two main types of priority queues: max priority queues and min priority queues. In a max priority queue, elements with higher priority have higher values, while in a min priority queue, elements with lower priority have higher values.

Priority queues can be implemented using a variety of data structures, such as heaps, binary trees, or arrays. One common implementation of a priority queue is a binary heap. A binary heap is a binary tree where each parent node has at most two child nodes, and the value of each parent node is greater than or equal to the values of its child nodes. This makes it possible to efficiently retrieve the element with the highest priority.

The basic operations of a priority queue are:

insert - This operation adds an element to the priority queue. The element is added based on its priority, so it is inserted in the appropriate position in the data structure.
delete - This operation removes the element with the highest priority from the priority queue. This is typically the element at the top of the binary heap.
isEmpty - This operation checks if the priority queue is empty.
peek - This operation returns the element with the highest priority without removing it from the priority queue.

Here's an example implementation of a priority queue using a binary heap in Java:


public class PriorityQueue<T extends Comparable<T>> {
    private Node root;
    private int size;
    
    public PriorityQueue() {
        root = null;
        size = 0;
    }
    
    public void insert(T item) {
        if (root == null) {
            root = new Node(item);
        } else {
            insertHelper(root, item);
        }
        size++;
    }
    
    private void insertHelper(Node node, T item) {
        if (node.left == null) {
            node.left = new Node(item);
            node.left.parent = node;
            siftUp(node.left);
        } else if (node.right == null) {
            node.right = new Node(item);
            node.right.parent = node;
            siftUp(node.right);
        } else if (node.left.height <= node.right.height)
        {
            insertHelper(node.left, item);
        } else {
            insertHelper(node.right, item);
        }
    }
    
    public T delete() {
        if (root == null) {
            throw new
        NoSuchElementException("Priority queue is empty");
        }
        T result = root.item;
        if (size == 1) {
            root = null;
        } else {
            Node lastNode = findLastNode();
            root.item = lastNode.item;
            if (lastNode.parent.left == lastNode)
        {
                lastNode.parent.left =
        null;
            } else {
                lastNode.parent.right =
        null;
            }
            siftDown(root);
        }
        size--;
        return result;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public T peek() {
        if (root == null) {
            throw new
        NoSuchElementException("Priority queue is empty");
        }
        return root.item;
    }
    
    private Node findLastNode() {
        Node node = root;
        while (node.left != null || node.right != null) {

            if (node.right != null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return node;
    }
    
    private void siftUp(Node node) {
        while (node.parent != null &&
        node.item.compareTo(node.parent.item) > 0) {
            T temp = node.item;
            node.item = node.parent.item;
            node.parent.item = temp;
            node = node.parent;
        }
    }
    
    private void siftDown(Node node) {
        while (node.left != null || node.right != null) {

            Node maxChild = node.left;
            if (node.right != null &&
        node.right.item.compareTo(node.left.item) > 0) {
                maxChild = node.right;

            }
            if (node.item.compareTo(maxChild.item) <
        0) {
                T temp = node.item;

                node.item =
        maxChild.item;
                maxChild.item = temp;

                node = maxChild;
            } else {
                break;
            }
        }
    }
    
    private class Node {
        T item;
        Node parent;
        Node left;
        Node right;
        int height;
        
        public Node(T item) {
            this.item = item;
            parent = null;
            left = null;
            right = null;
            height = 0;
        }
    }
}

In this implementation, the binary heap is represented as a binary tree of Node objects. The root variable points to the root node of the tree, and the size variable keeps track of the number of elements in the priority queue. The insert method inserts a new element into the priority queue by adding a new node to the tree and then using the siftUp method to move the node up the tree to its correct position. The delete method removes the maximum element from the priority queue by swapping it with the last node in the tree, deleting the last node, and then using the siftDown method to move the new root node down the tree to its correct position.

The siftUp and siftDown methods are used to maintain the heap property of the tree. The siftUp method moves a node up the tree as necessary to maintain the heap property, and the siftDown method moves a node down the tree as necessary to maintain the heap property.

The Node class represents a node in the binary tree. It contains fields for the item, parent node, left child node, right child node, and height of the node.

This implementation is more memory-efficient than the previous implementation that used an array, since it only allocates space for the nodes that are actually in the tree. However, it may be slower than the array-based implementation due to the extra overhead of managing the tree structure.

DOUBLE ENDED QUEUES

A double-ended queue (deque) is a data structure that allows for insertion and removal of elements at both ends of the queue. It can be thought of as a combination of a stack and a queue. In a deque, elements can be added and removed from both the front and the back of the queue.

Here's an example implementation of a deque in Java using a doubly linked list:


public class Deque<T> {
    private Node head;
    private Node tail;
    private int size;
    
    private class Node {
        T value;
        Node next;
        Node prev;
    }
    
    public Deque() {
        head = null;
        tail = null;
        size = 0;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
    
    public void addFirst(T item) {
        Node newNode = new Node();
        newNode.value = item;
        newNode.next = head;
        newNode.prev = null;
        
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
        
        if (tail == null) {
            tail = head;
        }
        size++;
    }
    
    public void addLast(T item) {
        Node newNode = new Node();
        newNode.value = item;
        newNode.next = null;
        newNode.prev = tail;
        
        if (tail != null) {
            tail.next = newNode;
        }
        tail = newNode;
        
        if (head == null) {
            head = tail;
        }
        size++;
    }
    
    public T removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();

        }
        T value = head.value;
        head = head.next;
        
        if (head == null) {
            tail = null;
        } else {
            head.prev = null;
        }
        size--;
        return value;
    }
    
    public T removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();

        }
        T value = tail.value;
        tail = tail.prev;
        
        if (tail == null) {
            head = null;
        } else {
            tail.next = null;
        }
        size--;
        return value;
    }
    
    public T peekFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();

        }
        return head.value;
    }
    
    public T peekLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();

        }
        return tail.value;
    }
}

In this implementation, the deque is implemented as a doubly linked list of Node objects. Each Node object contains a value, a reference to the next node, and a reference to the previous node. The head field refers to the first node in the list, and the tail field refers to the last node in the list. The size field keeps track of the number of elements in the deque.

The addFirst method adds a new element to the front of the deque by creating a new node and setting its next field to the current head node. The addLast method adds a new element to the end of the deque by creating a new node and setting its prev field to the current tail node.

The removeFirst method removes the first element from the deque by setting the head field to the next node in the list and updating the prev field of the new head node. The removeLast method removes the last element from the deque by setting the tail field to the previous node in the list and updating the next field of the new tail node.

The peekFirst method returns the value of the first element in the deque without removing it, and the peekLast method returns the value of the last element in the deque without removing it.

Double-ended queues are useful when elements need to be inserted or removed from both the front and the back of the queue with equal frequency. They can be used in a variety of applications such as implementing a sliding window algorithm or maintaining a collection of elements with a natural ordering.

PATTERNS

BREADTH FIRST SEARCH

In BFS, we traverse a graph or tree level by level. To implement BFS, we typically use a queue to keep track of the nodes we need to visit in the next level.

Here's a sample implementation of the BFS algorithm using a queue:


public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    
    queue.add(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.println(current);

        for (Node neighbor : current.getNeighbors()) {
            if (!visited.contains(neighbor)) {

                queue.add(neighbor);

                visited.add(neighbor);

            }
        }
    }
}

In this implementation, we use a Queue to keep track of the nodes we need to visit in the next level. We also use a Set to keep track of the nodes we have already visited, so that we don't visit them again.

We start by adding the start node to the queue and marking it as visited. Then, we enter a loop where we continue to remove nodes from the front of the queue, process them (in this case, print them), and add their unvisited neighbors to the back of the queue. We repeat this process until the queue is empty, which means we have visited all the nodes reachable from the start node.

Note that this implementation assumes that the Node class has a method called getNeighbors() that returns a list of the node's neighbors. You may need to modify the implementation to fit your specific use case.

PROBLEMS

Easy

Medium

Hard