Stack, queue, deque - Introduction to Programming - Python

Stack, queue, deque

Python list as a stack, why lists fail as queues, and how collections.deque solves it with O(1) operations on both ends.

Stack

A stack is a Last In First Out (LIFO) structure — the last element you add is the first one you remove. Think of a stack of plates: you always take from the top.

A Python list works perfectly as a stack. Both operations are O(1):

Operation	List method	Complexity
Push	`append(x)`	O(1)
Pop	`pop()`	O(1)
Peek	`lst[-1]`	O(1)
Size	`len(lst)`	O(1)
Empty check	`len(lst) == 0`	O(1)

Example: Checking Balanced Brackets

A classic stack application — for every opening bracket push it, for every closing bracket pop and verify it matches:

Example: Reversing a List with a Stack

Queue

A queue is a First In First Out (FIFO) structure — the first element added is the first one removed. Think of a line of people: whoever arrives first gets served first.

Up next

Hash based data structures: set, dict, counter

Fast O(1) membership and lookup using set and dict, plus defaultdict and Counter from collections, with common CP patterns.

Operation	Method	Complexity
Add to right	`append(x)`	O(1)
Add to left	`appendleft(x)`	O(1)
Remove from right	`pop()`	O(1)
Remove from left	`popleft()`	O(1)
Peek right	`d[-1]`	O(1)
Peek left	`d[0]`	O(1)
Size	`len(d)`	O(1)
Access by index	`d[i]`	O(n)

Use case	Best choice
Stack (LIFO)	`list` with `append` / `pop`
Queue (FIFO)	`deque` with `append` / `popleft`
Both ends needed	`deque`
Sliding window of size k	`deque` with `maxlen=k` or manual
Random access by index	`list`

stack = []

stack.append(1)     # push
stack.append(2)
stack.append(3)

print(stack[-1])      # peek — view top without removing: 3
print(stack.pop())    # pop: 3
print(stack.pop())    # pop: 2
print(stack)          # [1]

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in ')]}':
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False
print(is_balanced("((())"))    # False

def reverse_with_stack(a):
    stack = []
    for x in a:
        stack.append(x)
    result = []
    while stack:
        result.append(stack.pop())
    return result

print(reverse_with_stack([1, 2, 3, 4, 5]))   # [5, 4, 3, 2, 1]

from collections import deque

d = deque([1, 2, 3])

# Add to either end — both O(1)
d.append(4)        # add to right: deque([1, 2, 3, 4])
d.appendleft(0)    # add to left:  deque([0, 1, 2, 3, 4])

# Remove from either end — both O(1)
d.pop()            # remove from right: returns 4
d.popleft()        # remove from left:  returns 0

print(d)           # deque([1, 2, 3])

from collections import deque

queue = deque()

queue.append(1)     # enqueue
queue.append(2)
queue.append(3)

print(queue.popleft())   # dequeue: 1
print(queue.popleft())   # dequeue: 2
print(queue)             # deque([3])

from collections import deque

d = deque(maxlen=3)
d.append(1)   # [1]
d.append(2)   # [1, 2]
d.append(3)   # [1, 2, 3]
d.append(4)   # [2, 3, 4] — 1 was dropped from the left
print(d)      # deque([2, 3, 4], maxlen=3)

from collections import deque

def sliding_window_max(a, k):
    d = deque()   # stores indices
    result = []

    for i in range(len(a)):
        # Remove indices outside the window
        while d and d[0] < i - k + 1:
            d.popleft()

        # Remove indices of smaller elements from the back
        while d and a[d[-1]] < a[i]:
            d.pop()

        d.append(i)

        if i >= k - 1:
            result.append(a[d[0]])

    return result

a = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(a, 3))   # [3, 3, 5, 5, 6, 7]

Stack, queue, deque

Stack

Example: Checking Balanced Brackets

Example: Reversing a List with a Stack

Queue

`collections.deque`

Basic Operations

Using Deque as a Queue

Using Deque as a Stack

Initializing with a Max Length

Example: Processing Tasks in Order

Example: Sliding Window Maximum (Monotonic Deque)

Summary: Which to Use?