Stack, queue, deque - Язык программирования Python для спортивного программирования

Stack, queue, deque

Understanding of special sequenced data structures: stack, queue, deque

Sequences: Stack, Queue, and Deque

We already know Python lists well. In this lesson we look at how lists can be used as stacks and queues, why that sometimes causes performance problems, and how collections.deque solves them.

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

Up next

Hash based data structures: set, dict, counter

Learn how set and dict works. Counter data structure

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

Sequences: Stack, Queue, and 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?