Python Data Structures: deque, set, and stack Explained

Python gives you the right tool for many jobs right in its standard library, but three data structures stand out for solving specific performance problems that a plain list handles poorly: the deque, the set, and the stack pattern. When a Python deque is the right call over a list, when sets beat loops for membership testing, and how stacks enforce order — this article covers all three with the trade-offs you need to make the correct choice.

Python deque: When List Performance Falls Apart

The deque (double-ended queue, pronounced “deck”) lives in Python’s collections module. Its purpose is narrow but important: fast access to both ends of a sequence. With a regular Python list, removing the first element — list.pop(0) — is an O(n) operation. Python shifts every remaining element one slot to the left to fill the gap. That shift is invisible in small lists but becomes a bottleneck at scale.

deque.popleft() is always O(1), regardless of how many elements the deque holds. The same holds for appendleft(). This makes deque the correct choice for any queue-like structure where you consume from the front and produce at the back.

The Python documentation for collections.deque covers the full API with additional usage examples.

from collections import deque

task_queue = deque()

task_queue.append("render_image")
task_queue.appendleft("urgent_alert")

print(task_queue.popleft())
print(task_queue.popleft())

The first popleft() returns "urgent_alert" — it jumped the queue via appendleft. The second returns "render_image". Both calls complete in O(1) time.

Beyond basic queue operations, deque accepts a maxlen parameter that caps the size and turns it into a sliding window. When the buffer is full, new items pushed onto one end automatically drop the oldest item from the opposite end:

from collections import deque

response_times = deque(maxlen=5)
for ms in [120, 95, 140, 88, 102, 77, 134]:
    response_times.append(ms)

print(list(response_times))

The output is [140, 88, 102, 77, 134] — the five most recent values. This sliding-window pattern appears in monitoring dashboards, rate limiters, moving-average calculators, and log rotation buffers.

One trade-off to keep in mind: random access in a deque is O(n), not O(1). The CPython implementation stores elements in a doubly-linked list of fixed-size blocks. Indexing into the middle — my_deque[500] — requires walking from one end. If you need frequent indexed access, a plain list is the better choice.

Python Sets: Membership Testing and Deduplication

A Python set is an unordered collection of unique, hashable values. Two operations make it useful in practice: fast membership testing and removing duplicates.

Membership testing in a list is O(n): Python scans every element until it finds a match or exhausts the list. A set uses a hash table internally, so in runs in O(1) on average — it hashes the value, jumps to the right bucket, and either finds the element or does not. For validating against a known collection such as valid status codes, allowed commands, or approved email domains, a set is the right data structure.

The Python documentation on set types covers frozenset and the full set API in detail.

raw_tags = ["python", "backend", "python", "api", "backend", "python"]
unique_tags = list(set(raw_tags))
print(unique_tags)

valid_statuses = {"active", "paused", "archived"}
user_status = "active"
if user_status in valid_statuses:
    print("Status is valid")

The first block deduplicates raw_tags — order is not preserved. The second block demonstrates O(1) membership testing: checking user_status in valid_statuses hashes the string once and returns immediately, rather than scanning a list.

Sets also support mathematical set operations that are worth knowing for data processing:

team_a = {"alice", "bob", "carol"}
team_b = {"bob", "carol", "dave"}

both_teams  = team_a & team_b
either_team = team_a | team_b
only_in_a   = team_a - team_b
in_one_only = team_a ^ team_b

Intersection (&) returns elements in both sets; union (|) returns all unique elements; difference (-) returns elements only in the left set; symmetric difference (^) returns elements in exactly one set.

One hard constraint: every set element must be hashable. Lists, dicts, and plain sets cannot be set elements. Tuples can be set elements if all their contents are hashable. If you need a set of sets, use frozenset.

When you need unique elements in insertion order, dict.fromkeys(sequence) is the idiomatic pattern — Python dict has preserved insertion order since version 3.7. For more advanced dict-building patterns alongside set operations, Python dictionary comprehension covers the idiomatic approaches for building filtered and transformed dicts.

Stacks in Python: LIFO Without a Dedicated Type

A stack is last-in, first-out (LIFO). The last item pushed onto the stack is the first one popped off. Python does not ship a dedicated Stack class, but a plain list works well for stack semantics: append() pushes to the right end, pop() pulls from the right end. Both are amortized O(1).

history = []

history.append("opened_file")
history.append("edited_line_5")
history.append("saved_draft")

last_action = history.pop()
print(f"Undoing: {last_action}")

last_action = history.pop()
print(f"Undoing: {last_action}")

The first pop() returns "saved_draft", the second returns "edited_line_5" — last in, first out. This undo-history pattern maps directly to how text editors, compilers, and expression parsers use stacks internally.

The classic stack use case is bracket or expression validation — checking that parentheses in a string are balanced. Here is a depth-counter version for parentheses:

def parens_balanced(s):
    depth = 0
    for ch in s:
        if ch == "(":
            depth += 1
        elif ch == ")":
            if depth == 0:
                return False
            depth -= 1
    return depth == 0

print(parens_balanced("(())"))
print(parens_balanced("(()"))
print(parens_balanced(""))

The three calls return True, False, and True respectively. The depth counter acts as a minimal stack — every ( increments it, every ) decrements it, and a negative depth signals a mismatch. Production parsers extend this to handle multiple bracket types by using a full stack of characters.

When would you choose a deque as a stack over a list? When you need a bounded stack — pass maxlen to cap the depth and automatically discard old items. Or when the same structure also serves as a queue elsewhere in the code. For a pure stack, a list is simpler and more idiomatic Python.

Comparing deque, list, and set

Choosing the right data structure comes down to which operation needs to be fast:

The practical rule: lists win for general-purpose sequencing and indexed access. Deques win when both ends need to be fast. Sets win for membership testing and deduplication. If you have if item not in some_list inside a hot loop, that list should probably be a set.

When working with numeric data alongside these structures — counters, sums, statistics over deque windows — Python math and numbers covers the numeric types and operators that pair naturally with collections.

Things That Will Trip You Up

Trap 1: deque does not support slicing.

A deque looks like a sequence but is not a full list substitute. The following raises a TypeError:

from collections import deque
d = deque([10, 20, 30, 40, 50])
result = d[1:4]

That last line raises TypeError: sequence index must be integer, not 'slice'. To slice a deque, convert to a list first — but at that point the O(n) copy likely negates whatever advantage the deque gave you. If you slice frequently, a list is probably the better structure.

Trap 2: sets are unordered, and that matters at runtime.

A set’s iteration order is implementation-defined and not guaranteed to remain the same between runs or Python versions. Code that implicitly relies on a particular order will behave unexpectedly. If order matters, sort explicitly with sorted(my_set) before iterating.

Trap 3: mutable default arguments.

Python evaluates default argument values once, at function definition time. A mutable structure as a default argument is shared across every call:

from collections import deque

def process_batch(items, buffer=deque()):
    buffer.extend(items)
    return list(buffer)

print(process_batch([1, 2]))
print(process_batch([3, 4]))

The second call returns [1, 2, 3, 4] — the buffer accumulates across calls. Fix this by using None as the default and creating the deque inside the function body. This bug class is common enough that many teams prefer list comprehension in Python patterns to build fresh collections on each call rather than mutating shared defaults.

Frequently Asked Questions

When should I use deque instead of a list in Python?

Use a deque when you need to append or pop from both ends of a sequence frequently. Python’s list.pop(0) is O(n) because every remaining element shifts left to fill the gap. deque.popleft() is always O(1). For queue structures, sliding windows, and bounded buffers, deque is the correct tool. For pure stacks and random-access sequences where you only touch the right end, a list is simpler and equally fast.

Is a Python set ordered?

No. Python sets are unordered — the iteration order is not guaranteed and can vary between Python versions and between runs. Sets use a hash table internally, and the storage position of each element depends on its hash value. If you need a unique collection that preserves insertion order, use dict.fromkeys(sequence) instead; Python dicts have maintained insertion order since version 3.7.

Can I use a Python deque as a stack?

Yes. deque.append() pushes an item onto the right end and deque.pop() removes from the right end — both in O(1) time. That gives valid stack semantics. For most use cases, a plain list with append() and pop() is equally fast and more idiomatic Python. Choose a deque as a stack only when you need a bounded depth via maxlen, or when the same structure also serves as a queue elsewhere in your code.

Conclusion

Python deque, set, and stack each solve a distinct problem that a plain list handles poorly. A deque gives you O(1) operations on both ends — the right tool for queues, sliding windows, and bounded buffers. A set gives you O(1) membership testing and O(n) deduplication. The stack pattern, built on a plain list or deque, enforces LIFO order without any additional import. Knowing which operation matters most in a given context makes the choice straightforward.

From here, list comprehension in Python is the most practical next topic — you can build sets, filtered lists, and mapped sequences in a single expression without writing a loop. For numeric data that travels alongside your collections, Python math and numbers covers the operators and functions you will reach for most often. When your data has consistent structure, Python dataclasses reduce boilerplate significantly. And when you need to validate JSON produced from Python collections, the JSON formatter tool makes it easy to verify that serialized structures are well-formed.