0Pricing
Coding Interview Prep · Урок

Реализация стека и его применение

Реализуйте стек с операциями push/pop/peek, затем решите задачи valid-parentheses, min-stack и вычисления обратной польской записи

«Реализация стека и его применение» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Структура данных «стек»

Стек — это структура данных, работающая по принципу «последним вошёл — первым вышел» (LIFO). Последний элемент, добавленный с помощью push, извлекается с помощью pop первым. Представьте стопку тарелок: добавлять или удалять элементы можно только сверху. Основные операции — push (add — добавить в вершину), pop (удалить с вершины) и peek (прочитать верхний элемент, не удаляя его). Все три операции выполняются за O(1) в корректно реализованном стеке.

В Python список идеально подходит для роли стека: append соответствует push, pop() — pop, а [-1] — peek.

stack = []

# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack)  # [10, 20, 30]

# Peek
print('Top:', stack[-1])       # 30

# Pop
print('Popped:', stack.pop())  # 30
print('After pop:', stack)     # [10, 20]

Класс Stack с операциями push, pop, peek, isEmpty

Обёртка над списком в виде класса предоставляет более понятный интерфейс и предотвращает случайное использование операций, не свойственных стеку, например insert или обращения по индексам, отличным от top. Именно такую реализацию ожидают интервьюеры, когда просят «реализовать стек с нуля».

class Stack:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError('pop from empty stack')
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty stack')
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek())  # 3
print(s.pop())   # 3
print(len(s))    # 2

Корректная расстановка скобок (LeetCode 20)

LeetCode 20 «Корректная расстановка скобок»: определите, сбалансирована ли строка со скобками. Для каждой открывающей скобки выполните push. Для каждой закрывающей скобки проверьте, что top стека — соответствующая открывающая скобка; если это не так или стек пуст, верните ложное значение. Если в конце стек пуст, строка корректна. Это классическое первое применение стека на собеседованиях по программированию.

def isValid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(isValid('()[]{}'))    # True
print(isValid('([)]'))      # False
print(isValid('{[]}'))      # True
print(isValid(']'))         # False

Стек минимума (LeetCode 155)

LeetCode 155 «Стек минимума»: спроектируйте стек, который поддерживает push, pop, peek и getMin — все за O(1). Секрет заключается в поддержании второго стека, который в каждый момент отслеживает минимум. При добавлении элемента также выполните push в стек минимума, если новое значение меньше либо равно текущему минимуму (<=) или стек минимума пуст. При удалении элемента также выполните pop из стека минимума, если удалённое значение равно текущему минимуму.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

Вычисление обратной польской записи

LeetCode 150 «Вычисление обратной польской записи» (постфиксной записи): операнды помещаются в стек; при встрече оператора извлеките два операнда, примените оператор и поместите результат в стек. Порядок важен для вычитания и деления: первый извлечённый операнд является правым, второй — левым.

def evalRPN(tokens):
    stack = []
    ops = set(['+', '-', '*', '/'])
    for tok in tokens:
        if tok not in ops:
            stack.append(int(tok))
        else:
            b = stack.pop()  # right operand
            a = stack.pop()  # left operand
            if tok == '+':
                stack.append(a + b)
            elif tok == '-':
                stack.append(a - b)
            elif tok == '*':
                stack.append(a * b)
            else:             # division truncated toward zero
                stack.append(int(a / b))
    return stack[0]

print(evalRPN(['2','1','+','3','*']))     # 9
print(evalRPN(['4','13','5','/','+']))    # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+']))  # 22

Декодирование строки (LeetCode 394)

LeetCode 394 «Декодирование строки»: для закодированной строки, например 3[a2[c]], разверните её в accaccacc. Используйте два стека: один для количества повторений, другой для накопленных строк. При встрече цифры соберите (build) полное число. При встрече [ поместите в стек текущую строку и количество. При встрече ] извлеките их и повторите текущий фрагмент. При встрече буквы добавьте её к текущей строке.

def decodeString(s):
    count_stack = []
    str_stack   = []
    current_str = ''
    current_num = 0
    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)
        elif ch == '[':
            count_stack.append(current_num)
            str_stack.append(current_str)
            current_str = ''
            current_num = 0
        elif ch == ']':
            repeats = count_stack.pop()
            current_str = str_stack.pop() + current_str * repeats
        else:
            current_str += ch
    return current_str

print(decodeString('3[a]2[bc]'))    # 'aaabcbc'
print(decodeString('3[a2[c]]'))     # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'

Ежедневные температуры (предварительный обзор монотонного стека)

LeetCode 739 «Ежедневные температуры»: для каждого дня найдите, через сколько дней температура станет выше. Полный перебор занимает O(n²). При использовании стека перебирайте температуры; для каждого дня извлекайте все элементы стека (индексы дней), температура которых ниже сегодняшней. Ответ для каждого такого извлечённого дня — разность между текущим днём и извлечённым днём. Поместите текущий день в стек. Для оставшихся элементов стека более тёплый день так и не найден — их ответ равен 0.

def dailyTemperatures(temps):
    result = [0] * len(temps)
    stack  = []  # stores indices
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Стек для обхода DFS

Стек вызовов в рекурсивном DFS можно заменить явным стеком, превратив алгоритм в итеративный. Поместите корень в стек; пока стек не пуст, извлекайте узел, обрабатывайте его и помещайте в стек его дочерние узлы (сначала правый, затем левый, чтобы обрабатывать их слева направо). Такой итеративный DFS ведёт себя так же, как рекурсивный DFS, но позволяет избежать ограничения Python на глубину рекурсии при работе с глубокими деревьями.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)  # push right first
        if node.left:
            stack.append(node.left)   # so left is processed first
    return result

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root))  # [1, 2, 4, 5, 3]

Сложность по времени и памяти

Все операции со стеком (push, pop, peek, isEmpty) выполняются за O(1) амортизированного времени. Построение стека из n элементов занимает O(n). В худшем случае память составляет O(n), когда хранятся все элементы. В задачах с монотонным стеком каждый элемент помещается в стек и извлекается из него не более одного раза, поэтому суммарное время всех итераций составляет O(n) — а не O(n²), как можно предположить при наивном анализе внешнего цикла.

# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total

def count_ops(n):
    pushes = pops = 0
    stack = []
    for i in range(n):
        while stack and stack[-1] < i:  # simulated decreasing condition
            stack.pop()
            pops += 1
        stack.append(i)
        pushes += 1
    return pushes, pops

p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}')  # <= 2000

Наибольший прямоугольник в гистограмме (предварительный обзор)

LeetCode 84 «Наибольший прямоугольник в гистограмме» — самая сложная классическая задача на стек. Для каждого столбца прямоугольник, для которого он может служить опорой, простирается влево до первого более низкого столбца и вправо до первого более низкого столбца. Монотонный стек отслеживает индексы столбцов в порядке возрастания высоты. При обнаружении более низкого столбца извлеките элементы с помощью pop и вычислите прямоугольник с высотой извлечённого столбца. Стек даёт левую и правую границы за O(1) на каждую операцию извлечения.

def largestRectangleArea(heights):
    stack  = []  # indices, increasing heights
    result = 0
    heights = heights + [0]  # sentinel forces all pops
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width  = i if not stack else i - stack[-1] - 1
            result = max(result, height * width)
        stack.append(i)
    return result

print(largestRectangleArea([2,1,5,6,2,3]))  # 10
print(largestRectangleArea([2,4]))           # 4

Стратегия решения задач на стек на собеседовании

Задачи на стек часто маскируются под формулировки «обработать изнутри наружу» или «найти следующий больший/меньший элемент». На то, что может помочь стек, указывают следующие признаки: нужно работать с самым недавно встреченным элементом, требуется сопоставлять пары (скобки, теги) или нужно получить O(n) в задаче, которая при наивном подходе требует вложенных циклов O(n²). В частности, монотонные стеки превращают поиск ближайшего большего или меньшего элемента для каждого элемента из задачи O(n²) в задачу O(n).

На собеседовании чётко сформулируйте инвариант стека: «Я буду поддерживать стек индексов в порядке убывания высоты».

Быстрая проверка

Проверьте понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке Вы узнали, что списки Python реализуют push/pop/peek за O(1), поэтому идеально подходят для стеков, корректная расстановка скобок и стек минимума — две классические задачи на стек с собеседований, а монотонные стеки решают задачи на поиск следующего большего элемента за O(n), помещая и извлекая каждый элемент не более одного раза. Далее Вы создадите очереди с помощью deque в Python и решите задачу о максимуме в скользящем окне.

Часто задаваемые вопросы

Урок «Реализация стека и его применение» бесплатный?

Да — полный текст урока «Реализация стека и его применение» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Реализация стека и его применение»?

Реализуйте стек с операциями push/pop/peek, затем решите задачи valid-parentheses, min-stack и вычисления обратной польской записи Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Реализация стека и его применение»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Реализация стека и его применение
  2. Реализация очереди и дека
  3. Приём с монотонным стеком
  4. Взаимная имитация стека и очереди
← Назад к Coding Interview Prep