ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management. To simplify the problem, assume that a block contains a name and a set of data . ZYB wants to implement the LRU algorithm with an array. His array can hold at most M MMelements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block s ss. ZYB will search for it in his array by brute force. If this block is present in his array , he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array . Seems boring?Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?
ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management. To simplify the problem, assume that a block contains a name (which is a string) and a set of data (which is a number). ZYB wants to implement the LRU algorithm with an array. His array can hold at most M M M elements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block s s s. ZYB will search for it in his array by brute force. If this block is present in his array (which means he can find a block with the same name), he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array (the block at the front of the array). Seems boring? Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?
