Mediumstackqueue
Как реализовать стек через очередь (и наоборот)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 225 / 232. Queue через 2 стека — in_stack и out_stack. push — в in_stack O(1); pop/peek — если out_stack пуст, переносим всё из in_stack (amortized O(1)).
class MyQueue:
def __init__(self):
self.in_stack, self.out_stack = [], []
def push(self, x):
self.in_stack.append(x)
def pop(self):
self.peek() # переносит при необходимости
return self.out_stack.pop()
def peek(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]Амортизированный анализ: каждый элемент push-ится и pop-ится дважды (по разу в каждый стек), поэтому O(1) amortized. Worst case pop — O(n). Стек через 2 очереди: push O(n) (перенос всех в q2, swap), pop/top O(1).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.