Реализация очереди через два стека

Реализация очереди через два стека

Очередь (Queue) работает по принципу FIFO (First In First Out) — первый вошёл, первый вышел. Стек же работает по принципу LIFO (Last In First Out). Задача требует создать очередь, используя только стеки — отличный пример алгоритмического мышления.

Идея решения

Мы используем два стека:

• input_stack — для добавления элементов (enqueue)
• output_stack — для извлечения элементов (dequeue)

Когда нужно получить элемент из очереди, мы перемещаем все элементы из input_stack в output_stack (это развернёт их порядок). Благодаря этому output_stack будет содержать элементы в порядке FIFO.

Базовая реализация

class MyQueue:
    def __init__(self):
        self.input_stack = []   # Для push-операций
        self.output_stack = []  # Для pop-операций
    
    def enqueue(self, x):
        # Просто добавляем в input_stack
        self.input_stack.append(x)
    
    def dequeue(self):
        # Если output_stack пуст, перемещаем элементы из input_stack
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        
        if not self.output_stack:
            raise IndexError("Queue is empty")
        
        return self.output_stack.pop()
    
    def peek(self):
        # Как dequeue, но без удаления
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        
        if not self.output_stack:
            raise IndexError("Queue is empty")
        
        return self.output_stack[-1]
    
    def is_empty(self):
        return len(self.input_stack) == 0 and len(self.output_stack) == 0

# Пример использования
queue = MyQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.peek())    # 1
print(queue.dequeue()) # 1
print(queue.dequeue()) # 2
queue.enqueue(4)
print(queue.dequeue()) # 3
print(queue.dequeue()) # 4

Пошаговый пример выполнения

Давайте проследим, как работает эта реализация:

Шаг 1: enqueue(1)
input_stack = [1]
output_stack = []

Шаг 2: enqueue(2)
input_stack = [1, 2]
output_stack = []

Шаг 3: enqueue(3)
input_stack = [1, 2, 3]
output_stack = []

Шаг 4: peek()
# output_stack пуст, переносим из input_stack
input_stack = []
output_stack = [3, 2, 1]  # Порядок развёрнут!
Возвращаем: 1

Шаг 5: dequeue()
output_stack = [3, 2]
Возвращаем: 1

Шаг 6: enqueue(4)
input_stack = [4]
output_stack = [3, 2]

Оптимизированная реализация с амортизированным анализом

class OptimizedQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def _balance(self):
        # Переносим элементы только если output_stack пуст
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
    
    def enqueue(self, x):
        self.input_stack.append(x)
    
    def dequeue(self):
        self._balance()
        if not self.output_stack:
            raise IndexError("Queue is empty")
        return self.output_stack.pop()
    
    def peek(self):
        self._balance()
        if not self.output_stack:
            raise IndexError("Queue is empty")
        return self.output_stack[-1]
    
    def is_empty(self):
        return not self.input_stack and not self.output_stack
    
    def size(self):
        return len(self.input_stack) + len(self.output_stack)

Анализ сложности

enqueue(x):

• Временная сложность: O(1) — просто добавляем в стек
• Пространственная сложность: O(1)

dequeue():

• Амортизированная временная сложность: O(1)
• В худшем случае: O(n) — если нужно перенести все n элементов
• Но: каждый элемент переносится из input в output только один раз

peek():

• Амортизированная временная сложность: O(1)
• Аналогично dequeue

Почему это работает? (Интуиция)

Главное понимание:

1. input_stack накапливает новые элементы в порядке добавления: [1, 2, 3]
2. Когда нужно извлечь, мы переносим в output_stack, развёртывая порядок: [3, 2, 1]
3. Теперь output_stack — это обычный стек с правильным порядком: pop() вернёт 1, потом 2, потом 3

Сравнение с прямой реализацией очереди

from collections import deque

# Способ 1: Через два стека (наша реализация)
queue_via_stacks = MyQueue()

# Способ 2: Встроенная deque (оптимальный вариант)
queue = deque()
queue.append(1)   # Эквивалент enqueue
queue.popleft()   # Эквивалент dequeue, O(1)

Расширенная реализация с методами Python

class FullyFeaturedQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def _balance(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
    
    def enqueue(self, x):
        self.input_stack.append(x)
    
    def dequeue(self):
        self._balance()
        if not self.output_stack:
            raise IndexError("dequeue from empty queue")
        return self.output_stack.pop()
    
    def peek(self):
        self._balance()
        if not self.output_stack:
            raise IndexError("peek from empty queue")
        return self.output_stack[-1]
    
    def __len__(self):
        return len(self.input_stack) + len(self.output_stack)
    
    def __bool__(self):
        return len(self) > 0
    
    def __repr__(self):
        return f"MyQueue({self.output_stack[::-1] + self.input_stack})"

Тестирование

def test_queue():
    q = MyQueue()
    
    # Тест 1: Простой случай
    q.enqueue(1)
    q.enqueue(2)
    assert q.peek() == 1
    assert q.dequeue() == 1
    assert q.dequeue() == 2
    
    # Тест 2: Чередование
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    assert q.dequeue() == 1
    q.enqueue(4)
    assert q.dequeue() == 2
    assert q.dequeue() == 3
    assert q.dequeue() == 4
    
    # Тест 3: Пустая очередь
    try:
        q.dequeue()
        assert False, "Should raise IndexError"
    except IndexError:
        pass
    
    print("All tests passed!")

test_queue()

Ключевые выводы

Плюсы подхода:

• Демонстрирует понимание структур данных
• Эффективен благодаря амортизированной O(1) сложности
• Хорошая практика для собеседований

Минусы:

• В реальной работе используй встроенный deque из collections
• Более сложен для понимания, чем простая реализация

Когда это задают на собеседовании:

• Проверяют понимание стеков и очередей
• Оценивают способность решать нестандартные задачи
• Смотрят на качество объяснения алгоритма