`deque` for Stacks and Queues

The Problem: Why list Is Not a Queue

Before diving into deque, let's clarify the data structures we aim to build:

• Queue (FIFO - First-In, First-Out): Think of a line at a grocery store. The first person to get in line is the first person to be served. New items are added to one end (the back) and removed from the other (the front).
• Stack (LIFO - Last-In, First-Out): Imagine a stack of plates. You add new plates to the top and also remove them from the top. The last item added is the first one removed.

A common but non-Pythonic approach is to use a standard list to implement these.

• Stack with a list: This works reasonably well. You use list.append() to add an item to the top and list.pop() to remove an item from the top. Both are efficient operations.
• Queue with a list: This is where the problem lies. You might use list.append() to add an item to the back of the queue, but to remove an item from the front, you must use list.pop(0).

This pop(0) operation is highly inefficient. To remove the first element, a Python list must shift every other element one position to the left. For a list with thousands or millions of items, this is a significant performance bottleneck.

The Pythonic Solution: collections.deque

The deque object is specifically designed to solve this problem. It is implemented as a doubly-linked list, which means that adding or removing elements from either end is an extremely fast, constant-time O(1) operation, regardless of the deque's size.

Let's watch a video that demonstrates the basic mechanics of a deque and contrasts its performance with a list.

As you saw, the difference is not minor; deque is orders of magnitude faster for these operations. Now, let's formalize how to use it for our target data structures:

• To implement a Queue (FIFO):

  • Enqueue: my_deque.append(item) (add to the right)
  • Dequeue: my_deque.popleft() (remove from the left)

• To implement a Stack (LIFO):

  • Push: my_deque.append(item) (add to the right)
  • Pop: my_deque.pop() (remove from the right)

Key Features and Use Cases of deque

Beyond simple appends and pops, deque has other features that make it a versatile tool. For a deep dive, we'll turn to a comprehensive article from Real Python.

Let's summarize the key points from the reading.

Bounded Deques with maxlen

You can create a deque with a fixed size using the maxlen argument. When a maxlen deque is full, adding a new item to one end automatically discards an item from the other end.

This is incredibly useful for things like:

• Keeping a history of the last N actions.
• Tracking the last N lines from a log file (emulating the tail command).
• Storing the last N sensor readings.

from collections import deque




# Keep a history of the last 3 visited pages
last_visited = deque(maxlen=3)

last_visited.append('home.html')
last_visited.append('products.html')
last_visited.append('about.html')
print(last_visited)  # deque(['home.html', 'products.html', 'about.html'], maxlen=3)




# A new page is visited
last_visited.append('contact.html')
print(last_visited)  # deque(['products.html', 'about.html', 'contact.html'], maxlen=3)



# 'home.html' was automatically discarded from the left

Thread Safety

As the Real Python article highlighted, the core append and pop operations on a deque are atomic in CPython. This means you can have multiple threads adding and removing items from a shared deque without needing explicit locks, which prevents data corruption. This makes deque a simple and effective tool for basic producer-consumer problems.

Exercise: Implement a Real-Time Log Monitor

Your task is to implement a simplified real-time log monitor. It will have two components:

1. A "producer" that simulates new log entries being generated.
2. A "consumer" that keeps track of the 5 most recent "ERROR" messages.

You must use a deque with maxlen to efficiently store the recent errors.

import time
import random
from collections import deque

LOG_LEVELS = ['INFO', 'INFO', 'INFO', 'DEBUG', 'WARNING', 'ERROR']
MESSAGES = [
    "User logged in",
    "Data processed successfully",
    "Database connection timeout",
    "File not found",
    "Invalid input received",
    "System memory low",
]

def log_producer(error_deque: deque):
    """
    Simulates a stream of log messages and adds ERROR messages to the deque.
    """
    for i in range(20):
        level = random.choice(LOG_LEVELS)
        message = random.choice(MESSAGES)
        log_entry = f"[{level}] - {message}"
        print(f"PRODUCER: Generated log: {log_entry}")

        if level == 'ERROR':



            # Your code here: Append the log_entry to the error_deque.
            # Because of maxlen, this will automatically handle keeping only the last 5.
            error_deque.append(log_entry)
            print(f"PRODUCER: Added to error queue. Current errors: {list(error_deque)}")

        time.sleep(random.uniform(0.1, 0.3))

def main():
    """
    Sets up the deque and runs the log producer.
    """



    # 1. Initialize a deque named 'recent_errors' that can hold a maximum of 5 items.
    recent_errors = deque(maxlen=5)

    print("--- Starting Log Monitor ---")
    log_producer(recent_errors)
    print("\n--- Log Monitor Finished ---")




    # 2. After the producer is done, print the final list of recent errors.
    print(f"\nFinal {recent_errors.maxlen} most recent errors:")
    if not recent_errors:
        print("No errors were reported.")
    else:
        for error in recent_errors:
            print(f"  - {error}")




# --- Run the simulation ---
if __name__ == "__main__":
    main()

To complete the exercise, fill in the two commented sections in the code above. The logic is straightforward; the goal is to correctly use the deque API as discussed. A correct implementation will show the producer generating various logs and the error_deque correctly updating to hold only the last 5 error messages.

Conclusion

You've now seen how collections.deque is the correct, Pythonic tool for jobs requiring fast additions and removals from both ends of a sequence. It is superior to a list for these tasks in both performance and thread safety.

Key Takeaways:

• list is inefficient for queues: Using list.pop(0) or list.insert(0, ...) is an O(n) operation and should be avoided in performance-sensitive code.
• deque is O(1): Appending or popping from either end of a deque is a constant-time operation, making it ideal for stacks and queues.
• Use deque for FIFO/LIFO: For queues (FIFO), use append() and popleft(). For stacks (LIFO), use append() and pop().
• maxlen is for bounded history: Create fixed-size deques with maxlen to automatically maintain a sliding window of recent items.
• deque is thread-safe: Its core operations are atomic, making it a reliable choice for simple multi-threaded data exchange without manual locking.

In the next lesson, we will shift our focus from containers with specialized behavior (Counter, defaultdict, deque) to a tool for creating containers with a specialized structure: @dataclass. You'll learn how to replace boilerplate __init__, __repr__, and other dunder methods to create clean, readable, and robust data-holding classes.