Wie und warum auf zwei Stapeln anstehen

Hallo habr

Dieser Beitrag wurde für Anfänger im Bereich der Olympiadenprogrammierung und für unerfahrene Entwickler geschrieben, die sich auf algorithmische Interviews vorbereiten. Am Ende des Bonusrätsels. Bei Interesse bitte ich um eine Katze :)

Erinnern wir uns zunächst an die Grundlagen:

Stapeln

Der Stack implementiert das Prinzip von LIFO (engl. Last in - first out, "last come, first come out").

Der Stapel hat zwei Hauptoperationen:

• push - schiebt einen Gegenstand auf den Stapel
• pop - holt ein Element aus dem Stapel

Der Stack wird normalerweise in einem Array implementiert (in einer verknüpften Liste immer noch möglich). Sie können hier mehr über den Stack und seine Implementierung lesen .

Warteschlange

Eine Warteschlange ist eine Datenstruktur mit Zugriff auf FIFO-Elemente (first in, first out - "Wer zuerst kommt, mahlt zuerst").

Eine Warteschlange hat zwei Hauptmethoden in ihrer Schnittstelle:

• push - Setzt einen Gegenstand an das Ende der Warteschlange
• Pop - Holen Sie sich ein Element von der Vorderseite der Warteschlange

Lesen Sie hier mehr über die reguläre Warteschlange.

Berücksichtigen Sie normalerweise zwei grundlegende Ansätze für die Implementierung der Warteschlange:

1. Auf dem Array
2. Auf einer verknüpften Liste

Warum ist der Stapel kühler als die Linie?

Stellen Sie sich vor, unsere Datenstruktur sollte die folgenden Operationen unterstützen:

• Minimale Unterstützung (min)
• Maximale Unterstützung (max)
• GCD-Unterstützung (Englisch größter gemeinsamer Teiler - größter gemeinsamer Teiler)
• Lcm-Unterstützung (am wenigsten häufig mehrfach)

Alle diese Operationen sind assoziativ (bilden eine Halbgruppe), aber keine von ihnen hat ein inverses Element (bildet keine Gruppe).

Für den Stapel können Sie ganz einfach eine der folgenden Operationen unterstützen: Legen Sie einfach ein Paar oben ab:

$$

$$(Element, operationResult)$$

Dabei ist das zweite Element des Paares das Ergebnis der Operation, die auf alle Elemente des Stapels angewendet wird.

Nachfolgend finden Sie ein Beispiel für eine Implementierung der Mindeststapelunterstützung in Python:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

Überlegen Sie nun, wie Sie den gleichen Trick mit der Warteschlange ausführen können. Wenn Sie es mit einer klassischen Warteschlange versuchen, die in einem Array organisiert ist, ist es unwahrscheinlich, dass etwas funktioniert. Dies ist auf die Tatsache zurückzuführen, dass die Minimaloperation keine inverse Operation aufweist (wie beispielsweise die Additionsoperation eine Subtraktionsoperation). Wie Sie vielleicht erraten haben, werde ich über die nicht so klassische Implementierung einer Warteschlange auf zwei Stapeln sprechen.

Warteschlange mit zwei Stapeln

Die Hauptbedingung, die erfüllt sein muss, ist, dass alle Operationen für amortisiertes O (1) durchgeführt werden müssen.

Nimm zwei Stapel: s1 und s2.

Die Push-Operation wird immer auf dem S1-Stack ausgeführt.

Die Pop-Operation wird wie folgt organisiert: Wenn der S2-Stapel leer ist, übertragen wir alle Elemente von S1 nach S2 durch aufeinanderfolgende Aufrufe von Pop und Push. Jetzt enthält der s2-Stapel Elemente in umgekehrter Reihenfolge (das oberste Element ist das allererste Element, das wir an die Reihe bringen).

Wenn s2 nicht leer ist, holen wir dummerweise die Elemente raus. Sobald s2 wieder leer ist, wiederholen wir den gleichen Vorgang.

Python-Code:

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

Arbeitszeit

Push-Operation : Wir schieben dumm einen Gegenstand auf den S1-Stapel. Betriebszeit O (1).

Pop-Operation : Für jedes Element wird nicht mehr als eine Übertragung von Stapel zu Stapel ausgeführt, daher beträgt die amortisierte Arbeitszeit 0 (1).

Operation get_min : Die Minima sind für die Stacks s1 und s2 bekannt, also nehmen wir nur das Minimum von den Minima. Betriebszeit O (1).

Bonus Challenge

Eine Folge von N Zahlen gegeben. Die Zahl M <N ist gegeben. Es ist in linearer Zeit erforderlich, ein Segment der Länge M zu finden, auf dem das Produkt min * max maximal ist.

Fazit

Vielen Dank für das Lesen bis zum Ende!

Wenn Sie sich für das Thema interessieren, können Sie hier lesen, wie Sie eine dauerhafte Warteschlange auf zwei Stapeln erstellen oder auf die Veröffentlichung meines nächsten Themas warten.

Schreiben Sie in den Kommentaren, welche Aufgaben auf zwei Stapeln Sie in Interviews oder Wettbewerben lösen mussten.