Session 35: Queue

Original Session

Date: 25 Jan 2025

Topic: Queue

Concept: FIFO

Concept: Queue<Integer> que = new LinkedList();

Concept: LRU cache implementation.

Concept: LFU cache implementation.

Rule1: Less frequency will be removed.
Rule2: If tie then follow LRU cache.

Programs

Create Equeue and Dequeue.

Enqueue

void enqueue(int x) {
	// write using two pointer front and rear
	// rear moves forward to new node rear.next = temp; rear = rear.next;
	//read from front pointer and move front pointer ahead.
}

Dequeue
```
void dequeue(int x) {

}
```

232. Implement Queue using Stacks

leetcode here

class MyQueue {

    private Stack<Integer> stack1 = new Stack();
    private Stack<Integer> stack2 = new Stack();

    public MyQueue() {
        
    }
    
    public void push(int x) {
        
        stack1.add(x);
    }
    
    public int pop() {
        
        if (stack1.isEmpty()) {
            throw new IllegalStateException("Cannot pop empty stack.");
        }

        while (!stack1.isEmpty()) {
            stack2.add(stack1.pop());
        }

        int pop = stack2.pop();
        while (!stack2.isEmpty()) {
            stack1.add(stack2.pop());
        }
        return pop;
    }
    
    public int peek() {
        
        while (!stack1.isEmpty()) {
            stack2.add(stack1.pop());
        }

        int pop = stack2.peek();
        while (!stack2.isEmpty()) {
            stack1.add(stack2.pop());
        }

        return pop;
    }
    
    public boolean empty() {
        return stack1.isEmpty();
    }
}

225. Implement Stack using Queues

leetcode here

class MyStack {

    Queue<Integer> q1 = new LinkedList();
    Queue<Integer> q2 = new LinkedList();
    int top;

    public MyStack() {
        
    }
    
    public void push(int x) {
        q1.add(x);
        top = x;
    }
    
    public int pop() {
        
        while (q1.size() > 1) {
            top = q1.remove();
            q2.add(top);
        }
        int ans = q1.remove();
        Queue<Integer> temp = q2;
        q2 = q1;
        q1 = temp;
        return ans;
        
    }
    
    public int top() {
         return top;
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

146. LRU Cache

leetcode here

class Node {

        int key, val;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
}
class LRUCache {
    
    Node head = new Node(-1, -1);
    Node tail = new Node(-1, -1);
    HashMap<Integer, Node> map = new HashMap();
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        
        if (map.containsKey(key)) {

            Node resNode = map.get(key);
            int ans = resNode.val;
            map.remove(key);
            deleteNode(resNode);
            addNode(resNode);
            map.put(key, head.next);
            return ans;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        
        if (map.containsKey(key)) {

            Node curr = map.get(key);
            map.remove(key);
            deleteNode(curr);
        }
        if (map.size() == capacity) {

            map.remove(tail.prev.key);
            deleteNode(tail.prev);
        }

        addNode(new Node(key, value));
        map.put(key, head.next);
    }

    private void addNode(Node newNode) {

        Node temp = head.next;
        newNode.next = temp;
        newNode.prev = head;
        head.next = newNode;
        temp.prev = newNode;
    }

    private void deleteNode(Node delNode) {

        Node prev = delNode.prev;
        Node next = delNode.next;
        prev.next = next;
        next.prev = prev;
    }
}

460. LFU Cache

leetcode here

class LFUCache {

    Map<Integer, Pair<Integer, Integer>> cache = new HashMap();
    Map<Integer, LinkedHashSet<Integer>> frequencies = new HashMap();
    int minf;
    int capacity;

    public LFUCache(int capacity) {
        this.minf = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        
        Pair<Integer, Integer> freqAndValue = cache.get(key);
        if (freqAndValue == null) {
            return -1;
        }

        int freq = freqAndValue.getKey();
        Set<Integer> keys = frequencies.get(freq);
        keys.remove(key);
        if (keys.isEmpty()) {
            frequencies.remove(freq);

            if (minf == freq) {
                minf++;
            }
        }
        int value = freqAndValue.getValue();
        insert(key, freq+1, value);
        return value;
    }
    
    public void put(int key, int value) {
        
        if (capacity <= 0) {
            return;
        }

        Pair<Integer, Integer> freqAndValue = cache.get(key);
        if (freqAndValue != null) {

            cache.put(key, new Pair<Integer, Integer>(freqAndValue.getKey(), value));
            get(key);
            return;
        }

        if (capacity == cache.size()) {

            Set<Integer> keys = frequencies.get(minf);
            int last = keys.iterator().next();
            cache.remove(last);
            keys.remove(last);

            if (keys.isEmpty()) {
                frequencies.remove(minf);
            }
        }

        minf = 1;
        insert(key, 1, value);
    }

    private void insert(int key, int frequency, int value) {

        cache.put(key, new Pair<Integer, Integer>(frequency, value));
        frequencies.putIfAbsent(frequency, new LinkedHashSet());
        frequencies.get(frequency).add(key);
    }
}