Queues: FIFO Data Structure

What is a Queue? The FIFO Principle

A queue is a linear data structure that, unlike a stack, follows the First-In, First-Out (FIFO) rule. This means the first element added to the queue will be the first one to be removed. Think of it as a line of people waiting for a service: the person who arrived first is the first one served.

This "first-come, first-served" behavior is crucial in many computing scenarios. For example, a web server handling incoming requests, a printer managing a queue of print jobs, or a system processing events in a specific sequence all rely on FIFO logic.

The video below from the codebasics channel provides an excellent real-world analogy involving producer-consumer systems, which should be very familiar from your backend development experience.

The core operations of a queue reflect this behavior:

• Enqueue: Adds an element to the rear (or back) of the queue.
• Dequeue: Removes and returns the element from the front of the queue.
• Front (or Peek): Returns the front element without removing it.
• is_empty: Checks if the queue is empty.
• size: Returns the number of elements in the queue.

Just like stacks, these core operations are designed to be highly efficient, ideally running in constant time, $O(1)$.

Implementing a Queue in Python

As with stacks, Python offers several ways to implement a queue. Your ability to discuss the trade-offs between these methods is a key point in technical interviews.

The list approach (and why it's inefficient)

You can use a Python list to simulate a queue. You would use list.append() to enqueue an item and list.pop(0) to dequeue an item.

my_queue = []
my_queue.append('a') # enqueue
my_queue.append('b') # enqueue
print(my_queue.pop(0)) # dequeue 'a'

However, this is highly inefficient. While append() is an amortized $O(1)$ operation, pop(0) is an $O(n)$ operation because removing an element from the beginning of a list requires shifting all subsequent elements one position to the left. For a large queue, this is unacceptably slow.

The collections.deque approach (the right way)

The collections.deque object (pronounced "deck," for double-ended queue) is the correct tool for the job. As you saw in the last lesson, it's built on a doubly-linked list, which provides fast appends and pops from both ends.

To implement a queue with a deque, you use:

• deque.append() to enqueue (add to the right end).
• deque.popleft() to dequeue (remove from the left end).

Both of these operations are guaranteed to have $O(1)$ time complexity.

The following article from Real Python provides an excellent, in-depth guide to using deque for queues.

As a summary of the implementation, the image below shows a complete Python Queue class, its methods, and a visual representation of how a queue object is structured in memory.

Problem-Solving with Queues: Number of Recent Calls

Now, let's tackle a LeetCode problem that perfectly demonstrates the utility of a queue's FIFO nature: Number of Recent Calls (LeetCode 933).

The Problem: You have a RecentCounter class that counts the number of recent requests within a certain time frame. It has one method:

• ping(t): Adds a new request at time t (in milliseconds) and returns the number of requests that have happened in the past 3000 milliseconds (i.e., in the inclusive range [t - 3000, t]).

You are guaranteed that every call to ping will use a strictly larger value of t than the previous call.

Thinking Through the Solution:

The core of this problem is maintaining a "sliding window" of time. We only care about requests that fall within the [t - 3000, t] range.

1. When a new ping arrives at time t, we need to record it.
2. We also need to discard any old pings that are now outside the new time window. For a new ping at time t, any recorded ping with a timestamp less than t - 3000 is no longer relevant.
3. The number of pings remaining is our answer.

Since timestamps t are always increasing, once a ping becomes too old, it will never be recent again. This means we can discard old pings in the same order they arrived. This "add to one end, remove from the other" logic is a perfect fit for a queue.

The algorithm is:

1. Initialize an empty queue (using collections.deque) to store the timestamps of the pings.
2. For each ping(t) call:
   a. Add the new timestamp t to the rear of the queue (enqueue).
   b. While the queue is not empty and the timestamp at the front of thequeue is less than t - 3000, remove it from the front (dequeue).
   c. The current size of the queue is the number of recent calls. Return this size.

This video provides a very clear walkthrough of this exact logic and its implementation.

The beauty of this solution is its efficiency. Because each timestamp is enqueued once and dequeued at most once, the work done for each ping call is amortized constant time.

Conclusion

In this lesson, we moved from the LIFO world of stacks to the FIFO world of queues. You've seen how this simple, fair-minded data structure is the backbone of many ordered processing systems.

Key Takeaways:

• A queue is a linear data structure that operates on a First-In, First-Out (FIFO) principle.
• The primary operations are Enqueue (add to back) and Dequeue (remove from front), which should have an $O(1)$ time complexity.
• In Python, collections.deque is the ideal tool for implementing a queue, using append() for enqueue and popleft() for dequeue. Using a list with pop(0) is inefficient.
• Queues are the natural choice for problems involving ordered processing, task scheduling, or managing a sliding window of recent items, as seen in the "Number of Recent Calls" problem.

In our next lesson, we will revisit stacks to explore a more advanced technique: the monotonic stack. You'll learn how this specialized variant can be used to efficiently solve problems like "Next Greater Element," which are common challenges in coding interviews.