If you first put the number 3 into a queue, then put the number 5 into a queue, then remove an item from the queue, what will be the first thing out of the queue? Nobody knows! It might be the first thing you put in, but it also might be the first thing that someone else put in! It could be anything! FIFO, FOFI, LIFO, FOLI, FILO and LOFI This interpretation always works for stacks, but it only works for queues if they are initially empty! The interpretation #2 always works for both, but requires the reader to consider the possibly unknown internal state of the data structure. Since data structures are typically considered 'black boxes' that simply do stuff for us without disclosing their inner details, it is tempting to consider using interpretation #1 from the above choices when interpreting the definition of 'FIFO' and 'LIFO'. 2) The first/last one among the set of items that you are about to add to the data structure, unioned with the set of items that are already in the data structure.1) The first/last one among the set of items that you are about to add to the data structure.But an important question is 'first/last one among what set of elements?' The only reasonable choices are the following: The terms 'FIFO' and 'LIFO' make reference to a 'first one' and a 'last one'. Furthermore, if we're going to repeat this thousands of times in textbooks and literature everywhere, why not make it as clear as possible? The First/Last of What Exactly?
Now I know that some of you out there aren't going to agree with me in saying that the use of 'FIFO' and 'LIFO' is a problem, but from a pedagogical perspective, I think it's worth discussing because at some point you have to learn these terms for the first time and we might as well be teaching these things as efficiently as possible. It's quite awful actually since it causes extreme lag every time I try to have a conversation with someone about data structures or algorithms.
#Queue fifo code
In both cases, we can say this happens when the first item is equal to the last item: Stack (LIFO and FIFO)įor whatever reason, this corner case causes my brain power utilization to spike to 100% for a few seconds (probably an n^2 code path somewhere) every time someone mentions the phrase 'FIFO' or 'LIFO'. For queues, the case is quite similar, but with an added restriction that the queue must be empty before the insertion (although this depends on your definition of 'first' discussed later). But are there cases where a stack can exhibit FIFO behaviour, or a queue exhibit LIFO behaviour? The answer is yes: For stacks, this occurs when the sequence of items to be added and then removed is only of size one. The whole point of making these two definitions is to emphasize that the behaviour of a stack is different from a queue. The problem comes about when you consider how mutually exclusive these definitions are. This shows the typical 'Last In First Out' (LIFO) and 'First In First Out' (FIFO) model of stacks and queues. To explain myself, I'll start with a typical model of stacks and queues that are presented in CS classes: Stack (LIFO) Those definitions have always bothered me, and I think I've finally articulated why. FIFO, LIFO Considered Harmful - By Robert Elder The Formal Definition of Stacks and Queues