Implement Queue Using Stacks

+10

Zbuduj kolejkę FIFO, której jedynym miejscem przechowywania danych są dwa stosy. Stos może jedynie dodawać element na wierzchu, usuwać element z wierzchu, odczytywać element z wierzchu i informować, czy jest pusty. Kolejka obsługuje operacje push x (dodaj x na końcu), pop (usuń i zwróć pierwszy element), peek (zwróć pierwszy element) oraz empty (czy kolejka jest pusta?).

Otrzymujesz operacje w kolejności w postaci ops, a args[i] zawiera wartość dla operacji push i 0 dla każdej innej operacji. Wykonaj je na jednej kolejce, która początkowo jest pusta, i zwróć po jednym ciągu znaków dla każdej operacji: "null" dla operacji push, liczbę zapisaną jako tekst dla operacji pop lub peek oraz "true" albo "false" dla operacji empty.

Funkcja

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

opsstring-array: operacje w kolejności ich wykonywania
argsinteger-array: wartość dla każdego push, 0 dla każdej innej operacji
Zwracastring-array: jedna odpowiedź na operację, w postaci tekstu

Ograniczenia

1 ≤ ops.length ≤ 2000
args.length == ops.length
Każde ops[i] to push, pop, peek lub empty.
-10⁹ ≤ args[i] ≤ 10⁹ w przypadku operacji push, a args[i] == 0 w przypadku każdej innej operacji.
pop i peek są wywoływane tylko wtedy, gdy kolejka zawiera co najmniej jeden element.

Przykłady

Wejście: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Wyjście: ["null", "null", "1", "1", "false"]
Wyjaśnienie: Po wstawieniu 1, a następnie 2, na początku znajduje się 1, więc zarówno peek, jak i pop zwracają "1". 2 nadal znajduje się w środku, więc empty zwraca "false".

Wejście: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Wyjście: ["null", "null", "4", "null", "7", "9", "true"]
Wyjaśnienie: Pierwsze usunięcie zwraca 4, najstarszy element. 9 trafia do kolejki, gdy 7 wciąż czeka, i wychodzi po 7, ponieważ trafiło do niej później. Kolejka jest wtedy pusta, więc ostatnią odpowiedzią jest "true".

Wejście: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Wyjście: ["true", "null", "-3", "-3", "true"]
Wyjaśnienie: Kolejka zaczyna się pusta, więc pierwsza odpowiedź to "true". Liczba ujemna jest przechowywana tak jak każda inna: zarówno peek, jak i pop zwracają "-3", a następnie kolejka znów jest pusta.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak dodać operację back, która zwraca najnowszy element w czasie O(1), nie naruszając zamortyzowanej granicy pozostałych operacji?

Rozwiązanie

Stos zwraca elementy w odwrotnej kolejności niż ta, w której zostały dodane, a kolejka — w tej samej kolejności. Przelanie stosu na drugi stos ponownie odwraca kolejność, zamieniając kolejność stosu na kolejność kolejki. Całe pytanie sprowadza się do tego, kiedy przelewać: robienie tego przy każdej operacji kosztuje za każdym razem O(n), natomiast przelewanie tylko wtedy, gdy drugi stos się opróżni, sprawia, że każdy element jest przenoszony tylko raz.

Zmień kolejność całego stosu przy każdym dodaniu elementu

Intuicja

Umieść każdy element na jednym stosie, main, tak aby najstarszy element znajdował się na górze. Wtedy pop, peek i empty są pojedynczymi operacjami na stosie.

Trzeba jeszcze obsłużyć push. Nowy element powinien trafić na dół, pod wszystkimi oczekującymi elementami, a stos pozwala dodawać elementy tylko na górze. Przenieś więc każdy element ze stosu main na drugi stos, helper, umieść nowy element na pustym stosie main, a następnie przenieś wszystko z powrotem. Każde przeniesienie odwraca kolejność, dwa przeniesienia ją przywracają, a nowy element trafia na spód.

To rozwiązanie jest poprawne, ale każde wywołanie push dotyka każdego przechowywanego elementu dwa razy. Wstawienie 1,000 elementów z rzędu wymaga około 2 × (0 + 1 + ... + 999), czyli niemal miliona przeniesień, podczas gdy prawdziwa kolejka potrzebuje 1,000 kroków.

Algorytm

Utrzymuj dwa stosy: main z najstarszym elementem na wierzchu oraz pusty helper.
Dla push x: zdejmij każdy element ze stosu main i umieść go na helper, umieść x na main, a następnie przenieś każdy element ze stosu helper z powrotem na main.
Dla pop i peek: zdejmij element ze stosu main lub odczytaj jego wierzchni element.
Dla empty: zgłoś, czy stos main jest pusty.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

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

Stosy wejściowe i wyjściowe z leniwym transferem

Intuicja

Przypisz stosom osobne zadania. Każde wywołanie push trafia na inbox w czasie O(1). Operacje pop i peek odczytują dane z outbox, którego wierzchołek zawsze zawiera najstarszy element w kolejce.

Gdy outbox jest pusty i pojawi się żądanie pop lub peek, przelej do niego całą zawartość inbox. Najnowszy element schodzi z inbox jako pierwszy, więc trafia na spód outbox, a najstarszy ląduje na wierzchu. Przelewaj elementy tylko wtedy, gdy outbox jest pusty: dopóki znajdują się w nim elementy, są starsze niż wszystko w inbox, więc muszą zostać usunięte jako pierwsze. W drugim przykładzie 4 i 7 zostają przelane przed pierwszym wywołaniem pop; 9 czeka potem w inbox, aż 7 zostanie usunięte.

Pojedyncze wywołanie pop może przenieść wiele elementów, ale licz pracę dla każdego elementu osobno: każda wartość jest raz umieszczana na inbox, raz przenoszona do outbox i raz zdejmowana. n operacji kosztuje zatem łącznie O(n), czyli zamortyzowane O(1) na operację. Kolejka jest pusta, gdy oba stosy są puste.

Algorytm

Utrzymuj dwa puste stosy: inbox i outbox.
Dla push x: umieść x na stosie inbox.
Dla pop lub peek: jeśli outbox jest pusty, przenieś każdy element ze stosu inbox na outbox, zdejmując je po kolei. Następnie zdejmij element ze szczytu outbox lub go odczytaj.
Dla empty: zgłoś, czy oba stosy są puste.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

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

Pułapki i przypadki brzegowe

Większość błędów wynika z przekładania elementów w niewłaściwym momencie albo sprawdzania tylko jednego stosu.

Przekładanie inbox do outbox, gdy outbox wciąż zawiera elementy. Nowe elementy trafiają na starsze i wychodzą jako pierwsze, co zaburza kolejność kolejki. W drugim przykładzie 9 wyszłoby przed 7.
Zwracanie informacji, że outbox jest empty, na podstawie samego stosu outbox. Zaraz po dodaniu elementu nowy element znajduje się w inbox, więc kolejka nie jest pusta, nawet jeśli outbox jest pusty.
Zapominanie, że peek wymaga takiego samego uzupełnienia jak pop. Podgląd zaraz po pierwszych operacjach dodania elementów zastanie pusty outbox.
Korzystanie z kolejki z biblioteki albo odczytywanie dna stosu według indeksu. Chodzi o uzyskanie kolejności kolejki wyłącznie za pomocą operacji na stosie.
Zwracanie liczb lub wartości logicznych zamiast tekstu. Każda odpowiedź jest ciągiem znaków, w tym "null" w przypadku dodania elementu.

Najczęstsze pytania4

Jaka jest złożoność czasowa kolejki zbudowanej z dwóch stosów?

Push działa w czasie O(1). Pop i peek działają w czasie O(1) w sensie amortyzowanym: jedno wywołanie może przenieść każdy element z jednego stosu na drugi, ale każdy element jest przenoszony co najwyżej raz w całym swoim cyklu życia, więc n operacji kosztuje łącznie O(n). Oba stosy razem przechowują każdy element tylko raz, więc złożoność pamięciowa wynosi O(n).

Co oznacza tutaj amortyzowane O(1)?

Oznacza to, że średni koszt operacji w całej sekwencji jest stały, mimo że pojedyncza operacja może być powolna. Zdjęcie ze stosu, które przenosi 1 000 elementów, jest opłacone przez 1 000 tanich operacji dodawania, które je poprzedzają, ponieważ tych elementów nigdy więcej nie będzie trzeba przenosić. Żadna sekwencja n operacji nie kosztuje więcej niż około 4n kroków stosu.

Dlaczego potrzebujesz dwóch stosów, a nie jednego?

Pojedynczy stos udostępnia tylko swój najnowszy element, a kolejka potrzebuje najstarszego. Dotarcie do dna stosu oznacza usunięcie wszystkiego, co znajduje się nad nim, a te elementy muszą gdzieś poczekać — właśnie po to jest drugi stos. Przenoszenie elementów odwraca ich kolejność, a to odwrócenie sprawia, że kolejność od najnowszego staje się kolejnością od najstarszego.

Czy możesz zaimplementować stos przy użyciu kolejek?

Tak, ale typowe sposoby nie zapewniają oszczędności w ujęciu amortyzowanym. Jeden z popularnych sposobów wykorzystuje jedną kolejkę: po dodaniu nowego elementu pobierz każdy starszy element z początku i dodaj go na końcu, tak aby nowy element znalazł się na początku. Dzięki temu push ma złożoność O(n), a pop — O(1).

Python

def queueOps(ops, args):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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