Implement Stack using Queues

+10

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

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

Функция

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

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

Ограничения

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

Примеры

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

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

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

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

Можно ли оставить одну очередь, но перенести работу с операции добавления в операцию извлечения, чтобы добавление выполнялось за O(1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Две очереди: извлеките самый новый элемент при удалении

Идея

Храните элементы в очереди main в порядке поступления, чтобы самый новый находился в конце, а операция push выполняла одно добавление в очередь. Операция pop перемещает все остальные элементы во вторую очередь, spare, пока не останется один элемент: самый новый. Удалите его из очереди и поменяйте очереди местами, поскольку теперь в spare находятся остальные элементы в исходном порядке. Операция top выполняет такой же обход, но также добавляет самый новый элемент в очередь spare.

При каждой операции pop или top каждый сохранённый элемент перемещается один раз: 500 операций push, за каждой из которых следует top, требуют 1 + 2 + ... + 500 перемещений, то есть около 125 000 перемещений.

Алгоритм

Храните две очереди: main с элементами в порядке поступления и пустую spare.
Для push x: добавьте x в очередь main.
Для pop и top: перемещайте элементы из main в spare, пока не останется один, и извлеките его как ответ. Для top также добавьте его в spare. Поменяйте очереди местами.
Для empty: сообщите, пуста ли main.

from collections import deque

class QueueStack:
    def __init__(self):
        self.main = deque()    # the oldest item at the front, the newest at the back
        self.spare = deque()   # empty between operations

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

    def _move_all_but_newest(self):
        # Pass every item except the newest to the spare queue, in order.
        while len(self.main) > 1:
            self.spare.append(self.main.popleft())

    def pop(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.main, self.spare = self.spare, self.main
        return newest

    def top(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.spare.append(newest)   # top keeps the item
        self.main, self.spare = self.spare, self.main
        return newest

    def empty(self):
        return not self.main

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

Одна очередь, поворачивайте после каждого добавления

Идея

Всегда поддерживай в очереди порядок, соответствующий стеку: самый новый элемент находится в начале. Тогда pop — это извлечение из очереди, top считывает первый элемент, а вторая очередь не нужна. Новый элемент x добавляется в конец, за более старыми элементами, которые уже расположены от самых новых к самым старым. Извлеки первый элемент и добавь его в конец size-1 раз: каждый шаг переносит один старый элемент за x, сохраняя их порядок, поэтому x оказывается в начале.

В первом примере добавление 2 в стек поверх [1] дает [1, 2], а один поворот дает [2, 1]. Добавление элемента в очередь из k элементов требует k поворотов, поэтому push выполняется за O(n), а остальные операции — за O(1).

Алгоритм

Используй одну очередь, начало которой всегда соответствует вершине стека.
Для push x: добавь в очередь x, затем повтори size-1 раз: извлеки первый элемент и добавь его снова в очередь.
Для pop: извлеки первый элемент и верни его.
Для top: верни первый элемент, не удаляя его.
Для empty: сообщи, пуста ли очередь.

from collections import deque

class QueueStack:
    def __init__(self):
        self.queue = deque()   # the newest item is always at the front

    def push(self, x):
        self.queue.append(x)
        # Rotate the older items behind x, so x comes out first.
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        return self.queue.popleft()

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

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

Вращение size раз вместо size-1. Полный круг оставляет x в конце, поэтому следующий вызов pop возвращает самый старый элемент.
Вращение до добавления x в очередь. Более старые элементы перемещаются по кругу, а x всё равно оказывается в конце.
При использовании двух очередей — не возвращать элемент обратно в top. Тогда следующий вызов pop возвращает элемент, находящийся под ним.
При использовании двух очередей — не менять их местами. Элементы остаются в spare, а empty слишком рано возвращает "true".
Возвращение чисел или логических значений. Каждый ответ — строка, включая "null" для push.

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

Какова временная сложность стека, реализованного на основе очередей?

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

Почему стек, реализованный на основе очередей, работает медленнее, чем очередь, реализованная на основе стеков?

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

Операция push или pop должна быть затратной?

Пусть более редкая операция требует затрат. Если стек читают с помощью top и pop гораздо чаще, чем увеличивают, выполняй поворот при добавлении, чтобы каждое чтение занимало O(1). Если до нескольких операций pop происходит много добавлений, оставь добавление за O(1), а перемещай элементы при извлечении.

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

["null", "null", "2", "2", "false"]