The queue: enqueue and dequeue

The FIFO principle

A queue works the opposite way to a stack: the first element added is the first to come out. We speak of FIFO, for « First In, First Out ». It is exactly a checkout line at the supermarket: the first person to arrive is the first served, no matter who arrives afterwards.

The two basic operations

• enqueue: add an element at the back of the queue;
• dequeue: remove and return the element at the front of the queue.

Diagram: how a queue evolves

Empty queue:                 []

enqueue(A)  ->                [A]
enqueue(B)  ->                [A, B]
enqueue(C)  ->                [A, B, C]         (A is at the front, C has just arrived)

dequeue() -> A                [B, C]           (A comes out first, it was the first to arrive)
dequeue() -> B                [C]

horizontal view:
   exit (dequeue)                       entry (enqueue)
        <---   [ A ][ B ][ C ]   <---
             (front, comes out first)   (back, last to arrive)

Stack or queue, do not mix them up

The difference lies entirely in the end where the element is removed: at the same side as the addition for a stack (LIFO), at the opposite side from the addition for a queue (FIFO). An easy way to remember: a stack stacks up like a pile of plates, a queue behaves like a line of people waiting.

Common pitfall

A frequent mistake is to implement a queue thinking « first in, first out » but to mistakenly remove the last element added: you then get a disguised stack, with an output order completely different from the one expected.