data-structuresstackqueuefifolifo

Is FIFO in a queue is equivalent to LILO?

I am a little confused here.

The article said:

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Is it right to say that FIFO (first in, first out) is the same as LILO (last in, last out)?

And for stacks: is it the same as LIFO (last in, first out) and FILO (first in, last out)?

But no one ever uses LILO and FILO.

Solution

  • Yes, in the cases of both stacks and queues, either naming convention is technically accurate.

    Consider a queue of size 4. We enqueue "o", then enqueue "x", and they're put in the queue in that respective order.

         +---+---+---+---+
Back |   |   | x | o | Front
     +---+---+---+---+

    When we dequeue, the element closest to the front is removed from the queue, and the rest of the queue "moves up" to look like:

         +---+---+---+---+
Back |   |   |   | x | Front (o dequeued)
     +---+---+---+---+

    In this abstract example, "o" is the first element to be enqueued (first in), and the first element to be dequeued (first out).

    Then, we can dequeue again, and receive x.

         +---+---+---+---+
Back |   |   |   |   | Front (x dequeued)
     +---+---+---+---+

    Now, it is easy to see from this dequeue that "x" is the last element to be enqueued (last in), and the last element to be dequeued (last out).

    Therefore, FIFO and LILO are equivalent terminology.

    For brevity, I'll condense the example for a stack:

    +---+    +---+    +---+
|   |    |   |    |   |
+---+    +---+    +---+
|   |    |   |    |   |
+---+    +---+    +---+
|   |    | x |    |   |
+---+    +---+    +---+
| o |    | o |    | o |
+---+    +---+    +---+
Push o   Push x   Pop

    In the second step, "x" becomes the last element pushed to the stack (last in). Then, when we pop, the top element of the stack gets removed, which is still "x" (last out).

    If we were to pop a second time, we could be given "o". This element was the first in, and the last element to be removed. Therefore, the behavior can be described by both LIFO and FILO.

    As for why one naming convention is used over the other, -("/)-