Standard Bar Stack and Queues · Implementation O(1) per operation · O(capacity)
An archive circulates a fixed number of tapes. Every checkout or re-shelve makes a tape the freshest item; when the shelves are full and a new tape arrives, the least recently requested one is pulled from circulation. Readers want instant answers: is a tape on the shelf, and what is its catalog number?
Input: A capacity integer and a list of operations: ["put", key, value] or ["get", key].
Output: Return the list of values produced by every get operation, in order; a miss returns -1.
1 <= capacity <= 30000 <= key, value <= 10^4At most 2 * 10^4 calls total; each must run in O(1)Input: {"capacity":2,"operations":[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]}
Output: [1,-1,-1,3,4]
Putting 3 evicts the stale key 2; putting 4 evicts key 1 since reading it made 3 fresher.
Input: {"capacity":1,"operations":[["put",5,50],["get",5],["put",6,60],["get",5],["get",6]]}
Output: [50,-1,60]
A capacity-1 cache forgets the old key the moment a new one arrives.