Data Structures: Queues

Overview of the Queue Abstract Data Type (ADT)

• Definition: The Queue ADT stores arbitrary objects where insertions and deletions follow the First-In First-Out (FIFO) scheme.

• Conceptual Analogy: The operations are similar to a queue at a bank or a shop, where the first person in line is the first person served.

• Structural Mechanics:     * Insertions: Occur at the rear (back) of the queue.     * Removals: Occur at the front of the queue.

Queue Operations and Exceptions

• Main Operations:     * enqueue(object): Inserts an element at the end of the queue.     * object dequeue(): Removes and returns the element at the front of the queue.

• Auxiliary Operations:     * object first(): Returns the element at the front without removing it.     * integer len(): Returns the number of elements currently stored.     * boolean is_empty(): Indicates whether the queue contains any elements.

• Exceptions:     * EmptyQueueException: This error is thrown when attempting to execute dequeue or front (also referred to as first) on a queue that contains no elements.

Operational Example Trace

Applications of Queues

• Direct Applications:     * Waiting lists.     * Customer service centers.     * Access to shared resources (e.g., a network printer).     * Multiprogramming environments.

• Indirect Applications:     * As an auxiliary data structure for broader algorithms.     * As a component within other complex data structures.

Array-Based Queue implementation

• Underlying Structure: A Python list is utilized as the internal storage structure.

• Circular Fashion Logic:     * The implementation uses an array of a fixed size $N$ in a circular manner.     * This approach avoids the need to shift elements up when an item is removed from position $0$, which would otherwise lead to $O(n)$ time complexity.

• State Variables:     * f: An integer representing the index of the front element.     * size: An integer representing the total number of elements currently in the queue.     * r: A conceptual pointer representing the first element available after the end of the queue.

• Configurations:     * Normal Configuration: The front index f precedes the rear index r linearly.     * Wrapped-Around Configuration: The queue elements start near the end of the array and wrap back to the beginning, meaning r < f.

Deep Dive: Queue Algorithmic Logic

• Algorithm isEmpty():     * Returns the result of the boolean check (size == 0).

• Algorithm first():     * Returns the element located at index f of the array Q.

• Algorithm len():     * Returns the value of the size variable.

• Algorithm enqueue(o):     * Check capacity: if size() == len(Q), then call resize(2 * len(Q)).     * Calculate insert position: r = (f + size) mod len(Q). The modulo operator is necessary to calculate the insert position correctly within a circular array, allowing the index to wrap back to $0$ after reaching the end of the physical list.     * Placement: Q[r] = o.     * Update: size = size + 1.

• Algorithm dequeue():     * Empty Check: if isEmpty(), throw EmptyQueueException.     * Retrieval: o = Q[f].     * Cleanup: Q[f] = null (helpful for garbage collection).     * Update index: f = (f + 1) mod len(Q).     * Update count: size = size - 1.     * Return retrieved object o.

• Algorithm resize(n):     * Trigger: Occurs when size == len(Q).     * Process:         1. Store the existing data in a temporary variable oldQ.         2. Initialize the main list Q to a new size n filled with null values.         3. Set a pointer walk = f (the old front index).         4. Loop x from $0$ to size - 1:             * Assign Q[x] = oldQ[walk].             * Update walk = (walk + 1) mod len(oldQ) to traverse the old circular array.         5. Reset the front index f = 0 to realign the queue with the start of the new array.

Python Implementation Details (ArrayQueue Class)

• Instance Variables:     * self._data: A reference to a list instance with a fixed capacity.     * self._size: An integer representing the current number of elements stored (distinct from the list's capacity).     * self._front: An integer index of the first element in the queue.

• Default Settings:     * DEFAULT_CAPACITY = 10 is used for all new queue instances.

• Implementation of Key Methods:     * __init__(self): Creates an empty queue where self._data is initialized to [None] multiplied by the default capacity, and both self._size and self._front are set to $0$.     * first(self): Raises an Empty exception if the queue is empty; otherwise, returns self._data[self._front].     * dequeue(self):         * Raises Empty exception if needed.         * Captures answer = self._data[self._front].         * Explicitly sets self._data[self._front] = None to assist the garbage collector.         * Calculates new front: self._front = (self._front + 1) % len(self._data).         * Decrements self._size by 1.         * Returns answer.     * enqueue(self, e):         * If the internal list is full (self._size == len(self._data)), it doubles the array size via self._resize(2 * len(self._data)).         * Calculates available index: avail = (self._front + self._size) % len(self._data).         * Sets self._data[avail] = e and increments self._size by 1.     * _resize(self, cap):         * Maintains a reference to the old list.         * Allocates a new self._data list of the specified cap length.         * Iterates through existing elements only (for k in range(self._size)).         * Intentionally shifts indices so the new self._front becomes $0$.

Time Complexity and Extended Types

• Efficiency: All standard queue operations execute in constant time $O(1)$, including:     * Q.enqueue(e) (amortized, due to resizing).     * Q.dequeue().     * Q.first().     * Q.is_empty().     * len(Q).

• Double-Ended Queues (Deques): An ADT that allows elements to be added and deleted from both the front and the back of the queue. While the standard queue is FIFO, the deque offers broader flexibility.