Implement Queue Using Stacks

+10

Создай очередь FIFO (первым пришёл — первым ушёл), используя для хранения только два стека. Стек может только добавлять элемент наверх, удалять верхний элемент, считывать верхний элемент и сообщать, пуст ли он. Очередь поддерживает операции push x (добавить x в конец), pop (удалить и вернуть первый элемент), peek (вернуть первый элемент) и empty (пустая ли очередь?).

Тебе даны операции в порядке выполнения в виде ops, при этом args[i] содержит значение для операции push и 0 для всех остальных операций. Выполни их для одной очереди, изначально пустой, и верни по одной строке для каждой операции: "null" для push, число в виде текста для pop или peek и "true" или "false" для empty.

Функция

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: операции в порядке их выполнения
argsinteger-array: значение для каждого push, 0 для всех остальных операций
Возвращаетstring-array: один ответ на операцию в виде текста

Ограничения

1 ≤ ops.length ≤ 2000
args.length == ops.length
Каждый ops[i] — это push, pop, peek или empty.
-10⁹ ≤ args[i] ≤ 10⁹ для операции добавления в стек и args[i] == 0 для любой другой операции.
pop и peek вызываются только тогда, когда в очереди есть хотя бы один элемент.

Примеры

Ввод: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Вывод: ["null", "null", "1", "1", "false"]
Пояснение: После добавления сначала 1, а затем 2, в начале находится 1, поэтому и peek, и pop возвращают "1". 2 всё ещё находится внутри, поэтому empty возвращает "false".

Ввод: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Вывод: ["null", "null", "4", "null", "7", "9", "true"]
Пояснение: Первый вызов pop возвращает 4 — самый старый элемент. 9 поступает, пока 7 всё ещё ожидает, и выходит после 7, потому что поступил позже него. Затем очередь пуста, поэтому последний ответ — "true".

Ввод: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Вывод: ["true", "null", "-3", "-3", "true"]
Пояснение: Очередь изначально пуста, поэтому первый ответ — "true". Отрицательное число хранится так же, как любое другое: peek и pop возвращают "-3", и затем очередь снова пуста.

Дополнительный вопрос

Как добавить операцию back, которая возвращает самый новый элемент за O(1), не нарушая амортизированную оценку остальных операций?

Решение

Стек возвращает элементы в обратном порядке относительно того, в котором они поступили, а очередь — в том же порядке. Перекладывание элементов из одного стека во второй ещё раз меняет их порядок на обратный, превращая порядок стека в порядок очереди. Весь вопрос в том, когда перекладывать элементы: если делать это при каждой операции, каждый раз это будет стоить O(n), а если перекладывать только тогда, когда второй стек опустеет, каждый элемент переместится всего один раз.

Переупорядочивайте весь стек при каждом добавлении элемента

Идея

Храни каждый элемент в одном стеке, main, так, чтобы самый старый элемент находился сверху. Тогда pop, peek и empty — это операции с одним стеком.

Сложность возникает при выполнении push. Новый элемент нужно поместить внизу, под всеми уже ожидающими элементами, а стек может добавлять элементы только сверху. Поэтому перемести все элементы из main во второй стек, helper, помести новый элемент в пустой main и перемести всё обратно. Каждый перенос меняет порядок на обратный, два переноса восстанавливают его, и новый элемент оказывается внизу.

Это правильно, но при каждом вызове push каждый сохранённый элемент перемещается дважды. Добавление 1,000 элементов подряд требует примерно 2 × (0 + 1 + ... + 999) перемещений — почти миллион, тогда как настоящей очереди нужно 1,000 шагов.

Алгоритм

Используй два стека: main, в котором сверху находится самый старый элемент, и пустой helper.
Для push x: переложи все элементы из main в helper, помести x в main, затем верни все элементы из helper в main.
Для pop и peek: извлеки верхний элемент из main или прочитай его.
Для empty: сообщи, пуст ли main.
Запиши каждый ответ в виде текста и верни список.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Стеки входящих и исходящих элементов с отложенным переносом

Идея

Назначьте стекам разные задачи. Каждый элемент добавляется в inbox за O(1). Операции извлечения и просмотра читают из outbox, верхний элемент которого всегда является самым старым элементом в очереди.

Когда outbox пуст и поступает запрос на извлечение или просмотр, переложите в него все элементы из inbox. Сначала из inbox извлекается самый новый элемент, поэтому он оказывается внизу outbox, а самый старый — наверху. Перекладывайте элементы только тогда, когда outbox пуст: пока в нём остаются элементы, они старше любых элементов в inbox, поэтому сначала должны выйти из очереди. Во втором примере перед первым извлечением в outbox перекладываются 4 и 7; затем 9 остаётся ждать в inbox, пока 7 не выйдет из очереди.

Одна операция извлечения может переместить много элементов, но считайте затраты на каждый элемент отдельно: каждое значение один раз добавляется в inbox, один раз перемещается в outbox и один раз извлекается. Таким образом, n операций требуют в общей сложности O(n) времени, то есть в среднем O(1) на операцию. Очередь пуста, когда оба стека пусты.

Алгоритм

Поддерживайте два пустых стека: inbox и outbox.
Для push x: поместите x в стек inbox.
Для pop или peek: если outbox пуст, извлеките все элементы из inbox и поместите их в outbox. Затем извлеките верхний элемент из outbox или прочитайте его.
Для empty: сообщите, пусты ли оба стека.
Запишите каждый ответ в виде текста и верните список.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Ловушки и крайние случаи

Большинство ошибок возникает из-за того, что элементы перекладывают не вовремя или проверяют только один стек.

Перекладывание элементов из inbox в outbox, пока в outbox ещё есть элементы. Новые элементы оказываются поверх старых и извлекаются первыми, нарушая порядок очереди. Во втором примере 9 выйдет раньше 7.
Сообщение о том, что очередь empty, только на основании содержимого outbox. Сразу после добавления элемент находится в inbox, поэтому очередь не пуста, даже если outbox пуст.
Забывают, что для peek нужно пополнить стек так же, как для pop. При просмотре сразу после первых добавлений outbox окажется пустым.
Использование очереди из библиотеки или чтение нижнего элемента стека по индексу. Смысл в том, чтобы получить порядок очереди, используя только операции со стеком.
Возврат чисел или логических значений вместо текста. Каждый ответ — строка, включая "null" для добавления элемента.

Частые вопросы3

Какова временная сложность очереди, реализованной с помощью двух стеков?

Операция push выполняется за O(1). Операции pop и peek выполняются за амортизированное O(1): за один вызов можно переместить все элементы из одного стека в другой, но каждый элемент перемещается не более одного раза за всё время, поэтому n операций в сумме требуют O(n). Оба стека вместе хранят каждый элемент по одному разу, поэтому объём памяти составляет O(n).

Что здесь означает амортизированное O(1)?

Это означает, что средняя стоимость одной операции по всей последовательности постоянна, хотя отдельная операция может быть медленной. За извлечение, которое высыпает 1 000 элементов, «платят» 1 000 предшествующих дешёвых добавлений, потому что эти элементы больше никогда не будут высыпаться. Последовательность из n операций обходится не более чем примерно в 4n шагов работы со стеком.

Зачем нужны два стека, а не один?

Один стек предоставляет доступ только к самому новому элементу, а очереди нужен самый старый. Чтобы добраться до дна стека, нужно удалить всё, что находится над ним, и этим элементам нужно где-то подождать — для этого и нужен второй стек. При перемещении элементов меняется их порядок, и именно это превращает порядок «сначала самый новый» в порядок «сначала самый старый».

def queueOps(ops, args):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

Ожидаемый вывод

["null", "null", "1", "1", "false"]