Как реализовать очередь на двух стеках

Что проверяют

Алгоритмическое мышление и умение объяснить амортизированную сложность. Следом почти всегда спрашивают, сколько стоит один Dequeue в худшем случае и почему в среднем всё равно выходит O(1).

Как отвечать

Заводятся два Stack<T>: _in для добавления и _out для извлечения.

• Enqueue: _in.Push(item), O(1);
• Dequeue: если _out пуст, переложить все элементы из _in в _out. Порядок при этом переворачивается, и самый старый элемент оказывается сверху. Затем _out.Pop(). Если _out не пуст, перекладывать ничего не нужно;
• Peek: то же перекладывание, затем _out.Peek();
• Count: _in.Count + _out.Count.

Ключевое условие: перекладывать только тогда, когда _out пуст. Каждый элемент за свою жизнь один раз попадает в _in, один раз переезжает в _out и один раз оттуда извлекается. На n операций приходится O(n) работы, то есть O(1) амортизированно. При этом отдельный Dequeue в худшем случае стоит O(n), и для кода с жёсткими требованиями к задержке это стоит проговорить.

Сделайте интерфейс похожим на стандартный Queue<T>: на пустой очереди Dequeue бросает InvalidOperationException, а рядом есть TryDequeue(out T result) и TryPeek. Перекладывание вынесите в приватный метод, чтобы не дублировать его в Dequeue и Peek.

В конце скажите, что в рабочем коде берут Queue<T> (кольцевой буфер на массиве) или ConcurrentQueue<T> для многопоточности. Но сама идея живая: ImmutableQueue<T> из System.Collections.Immutable устроена именно на двух неизменяемых стеках.

Где спотыкаются

Перекладывают туда и обратно на каждой операции: всё в _out, достать элемент, всё обратно в _in. Работает, но каждая операция становится O(n).

Перекладывают, когда _out ещё не пуст. Новые элементы ложатся поверх старых, и порядок FIFO ломается на первом же смешанном сценарии.

Говорят «все операции O(1)», не добавляя слово «амортизированно» и не умея объяснить почему. Либо не обрабатывают пустую очередь, и пользователь получает исключение от Stack<T>.Pop с сообщением про пустой стек.