DSA Queue

Queue Data Structure

In the previous tutorial, we learned about Stacks (LIFO). Now, let's look at its sibling data structure: the Queue.

A Queue is exactly like waiting in line in real life. The rules are simple and fair!

1. What is a Queue?

A Queue operates on the First In, First Out (FIFO) principle.

Think of a line of people waiting to buy movie tickets. The person who arrives first gets their ticket first. When a new person arrives, they must join the back of the line.

Real-Life Examples of Queues:

• Printer Tasks: If you send 3 documents to a printer, it prints the first one you sent before starting the second one.
• Customer Service Call Centers: "Your call is important to us. You are currently 3rd in line."
• Web Servers: Handling thousands of incoming requests fairly in the exact order they arrive.

2. Core Queue Operations

Just like a Stack, a proper Queue restricts how you can access the data.

Here are the standard terms used in DSA for Queue operations:

1. Enqueue: Add a new element to the Rear (Back) of the queue.
2. Dequeue: Remove and return the element at the Front of the queue.
3. Peek (or Front): Look at the front element without removing it.
4. isEmpty: Check if the queue has no elements.

3. Time Complexity of a Queue

A well-implemented Queue is incredibly fast.

• Enqueue: O(1) Constant Time.
• Dequeue: O(1) Constant Time.
• Peek: O(1) Constant Time.
• Search: O(n) Linear Time. (You have to dequeue elements one-by-one to find an item in the middle).

Important Note: If you use a standard Array/List to build a Queue, removing the front item forces you to shift all the other items over, which drops the Dequeue speed to O(n). To get O(1) speed, Queues are usually built using Linked Lists under the hood!

4. Queue Code Example (Python)

In Python, standard lists are very slow for queues because inserting or deleting at index 0 requires shifting all the other elements.

Instead, Python developers use collections.deque (Double-Ended Queue) which is optimized for fast O(1) enqueues and dequeues!

from collections import deque
# Create an empty queue
queue = deque()
# 1. ENQUEUE (Add to the back)
print("Enqueueing elements...")
queue.append("A")
queue.append("B")
queue.append("C")
print("Current Queue:", list(queue))
# 2. PEEK at the front element
# Index 0 is always the front of the queue
front_element = queue[0]
print("Front element is:", front_element)
# 3. DEQUEUE (Remove from the front)
print("Dequeueing element...")
removed_item = queue.popleft()

print("Removed:", removed_item)
print("Queue after Dequeue:", list(queue))