Implement Queue Using Stacks

+10

Construa uma fila FIFO usando apenas duas pilhas como armazenamento. Uma pilha só pode adicionar um item no topo, remover o item do topo, ler o item do topo e informar se está vazia. A fila oferece push x (adicionar x ao final), pop (remover e retornar o primeiro item), peek (retornar o primeiro item) e empty (a fila está vazia?).

Você recebe as operações em ordem em ops, com args[i] contendo o valor de um push e 0 para todas as outras operações. Execute-as em uma única fila que começa vazia e retorne uma string por operação: "null" para um push, o número como texto para um pop ou peek e "true" ou "false" para empty.

Função

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

opsstring-array: as operações, na ordem em que são executadas
argsinteger-array: o valor de cada push, 0 para todas as outras operações
Retornastring-array: uma resposta por operação, como texto

Restrições

1 ≤ ops.length ≤ 2000
args.length == ops.length
Cada ops[i] é push, pop, peek ou empty.
-10⁹ ≤ args[i] ≤ 10⁹ para uma operação de push, e args[i] == 0 para qualquer outra operação.
pop e peek só são chamados quando a fila contém pelo menos um item.

Exemplos

Entrada: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Saída: ["null", "null", "1", "1", "false"]
Explicação: Depois de inserir 1 e então 2, o primeiro elemento é 1, então peek e pop retornam "1". O 2 ainda está dentro, então empty retorna "false".

Entrada: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Saída: ["null", "null", "4", "null", "7", "9", "true"]
Explicação: O primeiro elemento removido é 4, o item mais antigo. 9 chega enquanto 7 ainda está esperando, e sai depois de 7 porque entrou depois dele. A fila fica vazia, então a última resposta é "true".

Entrada: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Saída: ["true", "null", "-3", "-3", "true"]
Explicação: A fila começa vazia, então a primeira resposta é "true". Um número negativo é armazenado como qualquer outro: peek e pop retornam "-3", e então a fila fica vazia novamente.

+15 testes ocultos ao enviar

Para ir além

Como você adicionaria uma operação back que retorna o item mais recente em O(1), sem prejudicar o limite amortizado das outras?

Solução

Uma pilha devolve os itens na ordem inversa àquela em que chegaram, enquanto uma fila os devolve na mesma ordem. Despejar uma pilha em uma segunda pilha a inverte mais uma vez, transformando a ordem da pilha na ordem da fila. A questão toda é quando despejar: fazer isso a cada operação custa O(n) todas as vezes, enquanto despejar apenas quando a segunda pilha ficar vazia faz com que cada item seja movido apenas uma vez.

Reordene toda a pilha a cada push

Intuição

Mantenha todos os itens em uma única pilha, main, organizados de modo que o item mais antigo fique no topo. Assim, pop, peek e empty são operações de pilha simples.

O trabalho fica por conta de push. Um novo item deve ficar na parte de baixo, sob todos os que já estão aguardando, e uma pilha só pode adicionar itens no topo. Então, mova todos os itens de main para a segunda pilha, helper, empilhe o novo item na main vazia e mova tudo de volta. Cada movimento inverte a ordem; dois movimentos a restauram, e o novo item acaba embaixo.

Isso está correto, mas cada operação de push toca em todos os itens armazenados duas vezes. Empilhar 1.000 itens em sequência custa cerca de 2 × (0 + 1 + ... + 999), quase um milhão de movimentos, enquanto uma fila de verdade precisa de 1.000 etapas.

Algoritmo

Mantenha duas pilhas: main, com o item mais antigo no topo, e uma helper vazia.
Para push x: desempilhe todos os itens de main para helper, empilhe x em main e, em seguida, desempilhe todos os itens de helper de volta para main.
Para pop e peek: desempilhe ou leia o topo de main.
Para empty: informe se main está vazia.
Registre cada resposta como texto e retorne a lista.

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

Pilhas de entrada e saída com transferência preguiçosa

Intuição

Dê funções separadas às pilhas. Cada elemento inserido vai para inbox, em O(1). As operações de remoção e consulta leem de outbox, cujo topo é sempre o elemento mais antigo da fila.

Quando outbox está vazia e chega uma operação de remoção ou consulta, despeje todo o conteúdo de inbox nela. O elemento mais novo sai primeiro de inbox, então fica na base de outbox, e o mais antigo fica no topo. Despeje apenas quando outbox estiver vazia: enquanto ainda houver elementos nela, eles são mais antigos do que qualquer elemento em inbox, então devem sair primeiro. No segundo exemplo, 4 e 7 são despejados para a primeira remoção; 9 então espera em inbox até que 7 saia.

Uma única operação de remoção pode mover muitos elementos, mas conte o trabalho por elemento: cada valor é inserido em inbox uma vez, movido para outbox uma vez e removido uma vez. Portanto, n operações custam O(n) no total, ou O(1) amortizado por operação. A fila está vazia quando ambas as pilhas estão vazias.

Algoritmo

Mantenha duas pilhas vazias, inbox e outbox.
Para push x: empilhe x em inbox.
Para pop ou peek: se outbox estiver vazia, desempilhe cada item de inbox e empilhe-o em outbox. Em seguida, desempilhe ou leia o topo de outbox.
Para empty: informe se as duas pilhas estão vazias.
Registre cada resposta como texto e retorne a lista.

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

Armadilhas e casos extremos

A maioria dos bugs ocorre porque você transfere os itens no momento errado ou verifica apenas uma das pilhas.

Transferir inbox para outbox enquanto outbox ainda contém itens. Os novos itens ficam por cima dos mais antigos e saem primeiro, quebrando a ordem da fila. No segundo exemplo, 9 sairia antes de 7.
Informar que outbox está empty verificando apenas essa pilha. Logo após um push, o novo item fica em inbox, então a fila não está vazia, mesmo que outbox esteja.
Esquecer que peek precisa do mesmo reabastecimento que pop. Um peek logo após os primeiros pushes encontra outbox vazia.
Usar uma fila de biblioteca ou ler o fundo de uma pilha por índice. A ideia é obter a ordem de fila usando apenas operações de pilha.
Retornar números ou valores booleanos em vez de texto. Toda resposta é uma string, incluindo "null" para um push.

Perguntas frequentes4

Qual é a complexidade de tempo de uma fila construída com duas pilhas?

Push é O(1). Pop e peek são O(1) amortizado: uma chamada pode mover todos os itens de uma pilha para a outra, mas cada item é movido no máximo uma vez durante sua vida útil, então n operações custam O(n) no total. As duas pilhas juntas armazenam cada item uma vez, então o espaço é O(n).

O(1) amortizado significa o quê aqui?

Isso significa que o custo médio por operação ao longo de toda a sequência é constante, embora uma única operação possa ser lenta. Um pop que despeja 1.000 itens é compensado pelos 1.000 pushes baratos anteriores, porque esses itens nunca mais serão despejados. Nenhuma sequência de n operações custa mais do que cerca de 4n etapas da pilha.

Por que você precisa de duas pilhas e não de uma?

Uma única pilha expõe apenas seu item mais recente, e uma fila precisa do mais antigo. Para chegar ao fundo de uma pilha, é preciso remover tudo o que está acima dele, e esses itens precisam de um lugar para esperar: a segunda pilha. Mover os itens de uma pilha para outra inverte a ordem deles, e é essa inversão que transforma “mais recente primeiro” em “mais antigo primeiro”.

Você consegue implementar uma pilha usando filas?

Sim, mas os métodos usuais não oferecem economia amortizada. Um método comum usa uma fila: depois de adicionar um novo item, retire cada item mais antigo da frente e adicione-o ao final, para que o novo item acabe na frente. Isso faz com que push seja O(n) e pop seja O(1).

Python

def queueOps(ops, args):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

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