Design Most Recently Used Queue

We’ll implement the MRUQueue class using a list as the underlying data structure. The __init__ method initializes the queue with n elements, and the fetch method takes the k-th element from the queue, moves it to the end, and returns it.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class MRUQueue:

    def __init__(self, n: int):
        # Initialize the queue with elements from 1 to n
        self.queue = [i for i in range(1, n + 1)]

    def fetch(self, k: int) -> int:
        # Fetch the k-th element (1-indexed), so we'll adjust it to 0-indexed
        element = self.queue[k - 1]

        # Move the fetched element to the end of the queue
        self.queue.append(element)

        # Remove the fetched element from its original position
        self.queue.pop(k - 1)

        return element

Explanation:

• The __init__ method initializes the queue with a list containing integers from 1 to n.

• The fetch method fetches the k-th element, appends it to the end of the queue, and removes it from its original position. Since the input k is 1-indexed, we adjust it to 0-indexed when accessing the list.

• By using the append method to add the element to the end and pop method to remove it from the original position, we’re ensuring the MRU (Most Recently Used) element is moved to the end of the queue.

The given code meets the problem’s constraints and provides the desired functionality for the MRUQueue class.