Introduction

Yes, many practical algorithms combine stack and queue behavior, and a deque often provides both efficiently. These combinations are not academic tricks. They solve real ordering problems such as graph traversal, window analytics, and expression processing with predictable performance.

Why Combine These Structures

A stack gives last in first out behavior, which is useful for backtracking and deferred work. A queue gives first in first out behavior, which is useful for level order processing and fairness. A deque supports operations at both ends and can emulate both patterns when needed.

The design benefit is that each operation encodes intent. Push and pop at the right end means local reversal. Append at one end and remove at the other means stable arrival order.

Example 1: Reverse Level Order Traversal

A common pattern uses a queue for breadth first exploration and a stack to reverse output order.

1from collections import deque
2
3def reverse_level_order(graph, start):
4    q = deque([start])
5    seen = {start}
6    st = []
7
8    while q:
9        node = q.popleft()
10        st.append(node)
11        for nxt in graph.get(node, []):
12            if nxt not in seen:
13                seen.add(nxt)
14                q.append(nxt)
15
16    result = []
17    while st:
18        result.append(st.pop())
19    return result
20
21if __name__ == "__main__":
22    g = {
23        1: [2, 3],
24        2: [4],
25        3: [5],
26        4: [],
27        5: []
28    }
29    print(reverse_level_order(g, 1))

Queue drives exploration breadth wise. Stack reverses the visitation sequence without costly list insertions at the front.

Example 2: Sliding Window Maximum With Monotonic Deque

This algorithm uses a deque to maintain candidates in descending value order. It acts like a queue for window expiry and like a stack for removing weaker candidates.

1from collections import deque
2
3def sliding_window_max(nums, k):
4    dq = deque()  # stores indexes
5    out = []
6
7    for i, n in enumerate(nums):
8        while dq and dq[0] <= i - k:
9            dq.popleft()
10
11        while dq and nums[dq[-1]] <= n:
12            dq.pop()
13
14        dq.append(i)
15
16        if i >= k - 1:
17            out.append(nums[dq[0]])
18
19    return out
20
21if __name__ == "__main__":
22    print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

This pattern is a strong example of dual behavior in one structure. Front removal preserves window boundaries. Back removal preserves monotonic invariant.

Example 3: 0 1 BFS Uses Both Ends Intentionally

For graphs with edge weights only 0 or 1, a deque gives near Dijkstra behavior with simpler operations.

1from collections import deque
2
3def zero_one_bfs(n, edges, src):
4    graph = [[] for _ in range(n)]
5    for u, v, w in edges:
6        graph[u].append((v, w))
7
8    INF = 10**9
9    dist = [INF] * n
10    dist[src] = 0
11    dq = deque([src])
12
13    while dq:
14        u = dq.popleft()
15        for v, w in graph[u]:
16            nd = dist[u] + w
17            if nd < dist[v]:
18                dist[v] = nd
19                if w == 0:
20                    dq.appendleft(v)
21                else:
22                    dq.append(v)
23
24    return dist
25
26if __name__ == "__main__":
27    e = [(0, 1, 0), (0, 2, 1), (1, 2, 0), (2, 3, 1)]
28    print(zero_one_bfs(4, e, 0))

Appending to the front for zero weight edges and to the back for one weight edges preserves optimal processing order.

Choosing The Right Pattern

When deciding between stack, queue, or deque, start from ordering requirements.

• Need strict arrival order, choose queue semantics.
• Need undo or backtracking behavior, choose stack semantics.
• Need both with constant time ends, choose deque.

Then write down the invariant before coding. For sliding window maximum, invariant is descending values by index in the deque. For 0 1 BFS, invariant is shortest tentative distance order induced by edge weight placement.

Without explicit invariants, mixed end operations become hard to review and easy to break.

Common Pitfalls

• Using a Python list as queue and paying linear cost for front removal.
• Mixing traversal intent, such as stack operations in code expected to be breadth first.
• Forgetting to evict out of window indexes in monotonic deque algorithms.
• Not documenting invariants, which makes maintenance risky.
• Assuming deque automatically improves logic without clear operation rules.

Summary

• Many efficient algorithms combine stack and queue behavior by design.
• deque is the practical tool for constant time operations on both ends.
• Reverse level traversal, sliding window max, and 0 1 BFS are concrete examples.
• Correctness comes from invariants, not from the container alone.
• Start with ordering requirements, then map each operation to that requirement.