Queue Concept and Enqueue/Dequeue | Data Structures

A Queue is a linear Abstract Data Type operating under the First-In, First-Out (FIFO) discipline. The first element inserted into the queue is the first one processed and removed.

Real-World Analogy: The Checkout Line

Think of a queue at a grocery store checkout or a movie theater ticket counter:

Customers join at the back of the line (Enqueue).
The cashier serves customers from the front of the line (Dequeue).
No cutting in line; fairness is mathematically guaranteed.

Enqueue (Back / Tail)                         Dequeue (Front / Head)
       |                                                |
       v                                                v
    [ 40 ] --------> [ 30 ] --------> [ 20 ] --------> [ 10 ]

Core Queue Operations

Operation	Description	Time Complexity
`enqueue(element)`	Adds an item to the rear (tail) of the queue	`O(1)`
`dequeue()`	Removes and returns the item from the front (head)	`O(1)`
`peek()`	Inspects the front item without removing it	`O(1)`
`isEmpty()`	Checks if the queue contains zero elements	`O(1)`

The Pitfall of Implementing a Queue with a Simple Array

If you implement a queue with a naive array:

enqueue: Appending to the end is O(1).
dequeue: Removing index 0 forces you to shift all remaining n - 1 elements left, costing O(n) time!

Naive Array:
Dequeue 10 -> [ 20, 30, 40 ] (Requires shifting 20, 30, 40 left -> O(n) slow!)

To maintain O(1) performance for both enqueue and dequeue, you must use either a Doubly Linked List or a Circular Ring Buffer.

Singly Linked List Queue with Tail Pointer

class LinkedQueue<T> {
    private class Node<T>(val data: T, var next: Node<T>? = null)

    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    // O(1) Enqueue at tail
    fun enqueue(item: T) {
        val newNode = Node(item)
        if (tail == null) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            tail = newNode
        }
    }

    // O(1) Dequeue at head
    fun dequeue(): T {
        val first = head ?: throw NoSuchElementException("Queue is empty")
        head = first.next
        if (head == null) tail = null
        return first.data
    }

    fun peek(): T = head?.data ?: throw NoSuchElementException("Queue is empty")
    fun isEmpty(): Boolean = head == null
}

Summary

Queues follow FIFO (First-In, First-Out).
enqueue inserts at the tail; dequeue removes from the head.
Both operations must run in O(1) time using a linked list with a tail pointer or a circular ring buffer.