Design Most Recently Used Queue - Leetcode Solution

Problem Statement: Design a queue that supports retrieving the most recently used element in O(1) time complexity.

Solution: We can solve this problem using a hash table and a doubly linked list.

• Hash table: It will store the mapping between the keys and the corresponding doubly linked list nodes. The key will be the item that we want to add to the queue and the value will be the pointer to the node in the doubly linked list.
• Doubly linked list: It will store the items inserted in the queue and their order.

We will implement the following methods:

1. enqueue(item) – Add an item to the queue. If the item already exists, remove it from the doubly linked list and add it to the front. Otherwise, add the item to the front of the doubly linked list and add its pointer to the hash table.

2. dequeue() – Remove the least recently used item from the queue.

3. most_recently_used() – Return the most recently used item from the queue in O(1) time complexity.

Let's see their implementation:

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class MostRecentlyUsedQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hash_table = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def enqueue(self, item):
        if item in self.hash_table:
            node = self.hash_table[item]
            self.remove(node)
        node = Node(item, item)
        self.hash_table[item] = node
        self.add_to_front(node)
        if len(self.hash_table) > self.capacity:
            self.dequeue()
    
    def dequeue(self):
        if not self.tail.prev:
            return -1
        node = self.tail.prev
        self.remove(node)
        del self.hash_table[node.key]
        return node.key
    
    def most_recently_used(self):
        if not self.head.next:
            return -1
        return self.head.next.value
    
    def remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
    
    def add_to_front(self, node):
        n = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = n
        n.prev = node

In the above code, we first create a doubly linked list with head and tail nodes. We also create a hash table to store the key and the corresponding doubly linked list node.

In the enqueue method, we first check if the item already exists in the hash table, and if it does, we remove it from the doubly linked list and add it to the front. Otherwise, we create a new node and add it to the front of the list and also add its pointer to the hash table. We also check if the capacity of the queue is exceeded, then we dequeue the least recently used item.

In the dequeue method, we remove the least recently used item from the tail of the list and also remove it from the hash table.

In the most_recently_used method, we return the value of the node at the front of the doubly linked list.

We have used the remove method to remove a node from the list and the add_to_front method to add a node to the front of the list.

Time Complexity: The time complexity of the enqueue, dequeue, and most_recently_used methods is O(1).

Space Complexity: The space complexity of the queue is O(n) where n is the capacity of the queue.

1