[LeetCode] Design Most Recently Used Queue

1756. Design Most Recently Used Queue

Design a queue-like data structure that moves the most recently used element to the end of the queue.

Implement the MRUQueue class:

  • MRUQueue(int n) constructs the MRUQueue with n elements: [1,2,3,…,n].
  • int fetch(int k) moves the kth element (1-indexed) to the end of the queue and returns it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MRUQueue {
int bucket;
list<int> l;
vector<list<int>::iterator> skip;
public:
MRUQueue(int n) {
bucket = sqrt(n);
for(int i = 1; i <= n; i++) {
l.push_back(i);
if(((i-1) % bucket) == 0)
skip.push_back(prev(end(l)));
}
}

int fetch(int k) {
k--;
int index = k / bucket;
auto it = skip[index];
for(auto remainder = k % bucket; remainder > 0; remainder--)
it++;
l.push_back(*it);

if(k % bucket != 0) index++;
for(int i = index; i < skip.size(); i++)
if(next(skip[i]) != end(l))
skip[i] = next(skip[i]);

l.erase(it);

return l.back();
}
};

/**
* Your MRUQueue object will be instantiated and called as such:
* MRUQueue* obj = new MRUQueue(n);
* int param_1 = obj->fetch(k);
*/
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/19/PS/LeetCode/design-most-recently-used-queue/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.