Queues

About

Imagine a line of people waiting to buy tickets at a movie theater or a concert venue. The first person who gets in line is the very first person served, and any newcomer must join at the absolute back of the line.

Because of this, a Queue is known as a FIFO (First In, First Out) data structure. The element that has been waiting the longest is always processed first.

Complexities

• Time Complexity:

  • Enqueue (Insertion at Rear): $O(1)$ (Adding an item to the back takes constant time)

  • Dequeue (Removal from Front): $O(1)$ (Removing from the front must take constant time in an efficient queue)

  • Peek/Front (View front item): $O(1)$

  • Search: $O(n)$ (In the worst case, you have to look through all items from front to back)

• Space Complexity: $O(n)$ (Where $n$ is the total number of elements currently sitting in the queue)

Code Implementations

Python

if __name__ == "__main__":
    q = Queue()
    q.enqueue("Alice")
    q.enqueue("Bob")
    print("Front element (Peek):", q.peek())    # Expected: Alice
    print("Served (Dequeued):", q.dequeue())     # Expected: Alice
    print("Next in line:", q.peek())             # Expected: Bob

C++

int main() {
    Queue q;
    q.enqueue("Alice");
    q.enqueue("Bob");
    
    std::cout << "Front element (Peek): " << q.peek() << std::endl; // Expected: Alice
    q.dequeue();
    std::cout << "Front element after dequeue: " << q.peek() << std::endl; // Expected: Bob
    std::cout << "Queue size: " << q.size() << std::endl; // Expected: 1
    
    return 0;
}

Key Takeaways

• The Core Architecture Twist: Stacks grow and shrink from a single end (top). Queues, on the other hand, require two separate access markers: a front pointer to handle consumption, and a rear pointer to handle addition.
  
  
• Primary Use Cases:
  
  

  • Asynchronous Data Transfers: Managing background print jobs hitting a printer, or network packet serialization hitting a router.

  • CPU Task Scheduling: Operating systems handle incoming program execution processes using a ready queue.

  • Graph Exploration: Used as the central helper structure when performing a Breadth-First Search (BFS) across a network or tree layer-by-layer.