first-in first-out

algorithm (FIFO, or "queue") A data structure or hardware

buffer from which items are taken out in the same order they

were put in. Also known as a "shelf" from the analogy with

pushing items onto one end of a shelf so that they fall off

the other. A FIFO is useful for buffering a stream of data

between a sender and receiver which are not synchronised -

i.e. not sending and receiving at exactly the same rate.

Obviously if the rates differ by too much in one direction for

too long then the FIFO will become either full (blocking the

sender) or empty (blocking the receiver). A Unix pipe

is a common example of a FIFO.

A FIFO might be (but isn't ever?) called a LILO - last-in

last-out. The opposite of a FIFO is a LIFO (last-in

first-out) or "stack".

(1999-12-06)