Queue – Use a doubly-linked list. The maximum size of the queue is determined by the cache size(the total number of available frames). The least recently used pages will be near the rear of the queue whereas the most recently used pages will be towards the head of the queue.
HashMap – Store the page number as the key along with the address of the corresponding queue node as the value.
Algorithm
After a cache miss:
If cache is full, delete the tail of the list and the reference in HashMap.
Add a new element in front of the list.
Add a new entry in HashMap and refer to the head of the list.
After a cache hit:
Remove the hit element and add it in front of the list.
Update HashMap with a new reference to the head of the list.