Queue

The essentials

A queue is a linear data structure in which items are added at one end, the rear, and removed from the other end, the front. The item that has waited longest leaves first, so a queue follows FIFO (First In, First Out). A line at a ticket counter is the everyday example.

Key points

• ENQUEUE: inserts an element at the rear.
• DEQUEUE: removes and returns the element at the front.
• PEEK (front): looks at the front element without removing it.
• isEmpty: checks whether the queue is empty. Dequeuing from an empty queue is underflow; adding to a full queue of fixed size is overflow.
• In Python, a list can implement a queue: queue.append(x) enqueues at the rear, queue.pop(0) dequeues from the front, queue[0] peeks at the front and len(queue) gives the size.
• Applications: printer job queues, CPU scheduling of processes, call-centre waiting lines, ticket booking requests and messages being sent in order.

Exam tips

• Trace the list after each step. Example: enqueue A, B, C; dequeue; enqueue D gives ['B', 'C', 'D'] with B at the front.
• Compare with the stack: stack uses pop() at the end; queue uses pop(0) at the front.

Common mistakes

• Using pop() without an index for a queue, which removes the newest item instead of the oldest.
• Mixing up front and rear in a list-based queue; with append() the rear is the end of the list.