FIFO算法_fifo算法详细解释

FIFO（First in First out），即先进先出算法，比如在超市购物之后会提着我们满满的购物车来到收银台排在结账队伍的最后，眼睁睁地看着前面的客户一个个离开，这就是一种先进先出机制，先排队的客户先行结账离开。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度机制，采用先来先服务的原则，为什么这个原则在很多地方都会用到呢？因为这个原则简单，符合人们的惯性思维，具备公平性，并且实现起来简单，通过直接使用数据结构中的队列即可实现。

FIFO是队列机制中最简单的，每个接口上都存在FIFO队列，表面上看FIFO队列并没有提供什么QoS（Quality of Service，服务质量）保证，甚至很多人认为FIFO严格意义上不算做一种队列技术，实则不然，FIFO是其他队列的基础，FIFO也会影响到衡量QoS的关键指标：报文的丢弃、延时、抖动。既然只有一个队列，自然不需要考虑如何对报文进行复杂的流量分类，也不用考虑下一个报文怎么拿、拿多少的问题，而且因为按顺序取报文，FIFO无需对报文重新排序。简化了这些实现其实也就提高了对报文时延的保证。

在FIFO Cache设计中，核心原则就是，如果一个数据最先进入缓存中，则应该最早被淘汰。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在设计一个基于FIFO算法的Cache（缓存）组件时应该支持以下操作：

n get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；

n set(key,value)：如