# Stacks and Queues with list and deque — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/l-stackqueue

> Implement LIFO and FIFO behaviour efficiently.

## LIFO and FIFO

A **stack** is **last in, first out (LIFO)**: push and pop at the same end. A Python **list** is an excellent stack using `append` and `pop()`, both O(1). Stacks power undo history, expression evaluation, matching brackets, backtracking and depth-first search, and the **call stack** itself. A **queue** is **first in, first out (FIFO)**: add at the back, remove from the front. A list is a poor queue because `pop(0)` is O(n). Use **`collections.deque`** (double-ended queue), implemented as a doubly linked list of fixed-size blocks: `append`, `appendleft`, `pop` and `popleft` are all **O(1)**, and `deque(maxlen=n)` keeps only the last `n` items, perfect for sliding windows and recent-history buffers. Indexing into the middle of a deque is O(n). For **communication between threads**, use **`queue.Queue`** (FIFO), `LifoQueue` or `PriorityQueue`, which add locking and blocking `get`/`put` with timeouts; for asyncio, use `asyncio.Queue`. Queues power breadth-first search, task scheduling, buffering and rate limiting.

## Stack versus queue

A stack adds and removes at the top; a queue adds at the back and removes from the front.

![Left: a vertical pile of plates with arrows in and out at the top. Right: a horizontal line of people with an arrow joining at the back and leaving at the front.](assets/figures/data-structures-python/section-4-map.svg) — Figure 4.1 — LIFO and FIFO.

## Bracket matching with a stack and a recent-items queue

list as a stack, deque as a queue and a bounded buffer.

```python
from collections import deque

def balanced(expression: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expression:
        if ch in "([{":
            stack.append(ch)                  # push
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:   # pop and compare
                return False
    return not stack

print(balanced("{[a + b] * (c - d)}"))        # True
print(balanced("(a + b]"))                    # False

support_queue = deque()
for ticket in ["T1", "T2", "T3"]:
    support_queue.append(ticket)              # enqueue at the back
print(support_queue.popleft())                # T1: first in, first out
support_queue.appendleft("URGENT")            # jump the queue
print(list(support_queue))                    # ['URGENT', 'T2', 'T3']

recent_views = deque(maxlen=3)                # keeps only the last 3
for product in ["pen", "ink", "pad", "stapler"]:
    recent_views.append(product)
print(list(recent_views))                     # ['ink', 'pad', 'stapler']
```

## Use queue.Queue between threads

A `deque`'s individual `append` and `popleft` are thread-safe in CPython, but coordinating producers and consumers (waiting for items, signalling completion) is much easier with `queue.Queue`, which provides blocking `get`, `task_done` and `join`.

**Quiz:** Which structure gives O(1) removal from the front of a sequence?

- [ ] list.pop(0)
- [ ] tuple slicing
- [x] collections.deque.popleft()
- [ ] str.lstrip

*Answer:* collections.deque.popleft(). deque supports O(1) operations at both ends.