MySQL Query Cache - what type of queue is used?
According to the manual, the query cache removes the Least Recently Used (LRU) Query from the Query Cache when the Query Cache is full. Read the general chapter on the MySQL Query Cache for a more detailed description of the logic and architecture of the Query Cache.