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(); } };
|