差别
这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
fifo [2016/05/26 21:40] gongyu |
fifo [2016/05/26 21:42] (当前版本) gongyu |
||
---|---|---|---|
行 1: | 行 1: | ||
- | {{ :fifo_queue.png|}} | ||
FIFO is an acronym for first in, first out, a method for organizing and manipulating a data buffer, where the oldest (first) entry, or 'head' of the queue, is processed first. It is analogous to processing a queue with first-come, first-served (FCFS) behaviour: where the people leave the queue in the order in which they arrive. | FIFO is an acronym for first in, first out, a method for organizing and manipulating a data buffer, where the oldest (first) entry, or 'head' of the queue, is processed first. It is analogous to processing a queue with first-come, first-served (FCFS) behaviour: where the people leave the queue in the order in which they arrive. | ||
行 7: | 行 6: | ||
A priority queue is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default. | A priority queue is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default. | ||
- | |||
Queueing theory encompasses these methods for processing data structures, as well as interactions between strict-FIFO queues. | Queueing theory encompasses these methods for processing data structures, as well as interactions between strict-FIFO queues. | ||
+ | |||
+ | {{ :fifo_queue.png |}} | ||
====Data structure==== | ====Data structure==== | ||
Representation of a FIFO (first in, first out) queue | Representation of a FIFO (first in, first out) queue | ||
Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically a circular buffer or a kind of List. For information on the abstract data structure, see Queue (data structure). | Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically a circular buffer or a kind of List. For information on the abstract data structure, see Queue (data structure). | ||
- | {{ :600px-data_queue.svg.png|}} | + | {{ :600px-data_queue.svg.png |}} |
====Code==== | ====Code==== | ||
The following code shows a linked list FIFO C++ language implementation. In practice, a number of list implementations exist, including popular Unix systems C sys/queue.h macros or the C++ standard library std::list template, avoiding the need for implementing the data structure from scratch. | The following code shows a linked list FIFO C++ language implementation. In practice, a number of list implementations exist, including popular Unix systems C sys/queue.h macros or the C++ standard library std::list template, avoiding the need for implementing the data structure from scratch. |