Wie implementiere ich eine Warteschlange mit drei Stapeln?

136

Ich bin auf diese Frage in einem Algorithmusbuch gestoßen ( Algorithms, 4th Edition von Robert Sedgewick und Kevin Wayne).

Warteschlange mit drei Stapeln. Implementieren Sie eine Warteschlange mit drei Stapeln, sodass für jede Warteschlangenoperation eine konstante Anzahl von Stapeloperationen (im schlimmsten Fall) erforderlich ist. Warnung: hoher Schwierigkeitsgrad.

Ich weiß, wie man eine Warteschlange mit 2 Stapeln erstellt, aber ich kann die Lösung mit 3 Stapeln nicht finden. Irgendeine Idee ?

(oh und, das sind keine Hausaufgaben :))

DuoSRX
quelle
30
Ich denke, es ist eine Tower of Hanoi- Variante.
Gumbo
14
@Jason: Diese Frage ist kein Duplikat, da sie nach O (1) amortisierter Zeit fragt, während diese nach O (1) Worst-Case für jede Operation fragt. Die Zwei-Stapel-Lösung von DuoSRX hat bereits eine Amortisationszeit von O (1) pro Operation.
Interjay
15
Der Autor machte sicher keine Witze, als er sagte: "Warnung: hoher Schwierigkeitsgrad."
BoltClock
9
@Gumbo Leider ist die zeitliche Komplexität des Turms von Hanoi bei weitem nicht konstant!
Prusswan
12
Hinweis: Die Frage im Text wurde dahingehend aktualisiert: Implementieren Sie eine Warteschlange mit einer konstanten Anzahl von Stapeln [nicht "3"], sodass für jede Warteschlangenoperation eine konstante Anzahl von Stapeloperationen (im schlimmsten Fall) erforderlich ist. Warnung: hoher Schwierigkeitsgrad. ( algs4.cs.princeton.edu/13stacks - Abschnitt 1.3.43). Es scheint, dass Prof. Sedgewick die ursprüngliche Herausforderung eingeräumt hat.
Mark Peters

Antworten:

44

ZUSAMMENFASSUNG

  • Der O (1) -Algorithmus ist für 6 Stapel bekannt
  • Der O (1) -Algorithmus ist für 3 Stapel bekannt, verwendet jedoch eine verzögerte Auswertung, die in der Praxis zusätzlichen internen Datenstrukturen entspricht, sodass er keine Lösung darstellt
  • Menschen in der Nähe von Sedgewick haben bestätigt, dass ihnen eine 3-Stapel-Lösung nicht unter allen Einschränkungen der ursprünglichen Frage bekannt ist

EINZELHEITEN

Hinter diesem Link stehen zwei Implementierungen: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Eines davon ist O (1) mit drei Stapeln, ABER es verwendet eine verzögerte Ausführung, die in der Praxis zusätzliche Zwischendatenstrukturen (Verschlüsse) erzeugt.

Ein anderer von ihnen ist O (1), verwendet jedoch SIX-Stapel. Es funktioniert jedoch ohne verzögerte Ausführung.

UPDATE: Okasakis Artikel ist hier: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps und es scheint, dass er tatsächlich nur 2 Stapel für die O (1) -Version verwendet, die eine verzögerte Bewertung hat. Das Problem ist, dass es wirklich auf einer faulen Bewertung basiert. Die Frage ist, ob es ohne verzögerte Auswertung in einen 3-Stapel-Algorithmus übersetzt werden kann.

UPDATE: Ein weiterer verwandter Algorithmus ist in dem Artikel "Stacks versus Deques" von Holger Petersen beschrieben, der auf der 7. Jahreskonferenz für Computer und Kombinatorik veröffentlicht wurde. Sie finden den Artikel in Google Books. Überprüfen Sie die Seiten 225-226. Der Algorithmus ist jedoch keine Echtzeitsimulation, sondern eine lineare Zeitsimulation einer doppelendigen Warteschlange auf drei Stapeln.

gusbro: "Wie @Leonel vor einigen Tagen sagte, dachte ich, es wäre fair, sich bei Prof. Sedgewick zu erkundigen, ob er eine Lösung kennt oder ob ein Fehler vorliegt. Also habe ich ihm geschrieben. Ich habe gerade eine Antwort erhalten (wenn auch nicht von selbst, aber von einem Kollegen in Princeton), also teile ich es gerne mit Ihnen allen. Er sagte im Grunde, dass er keine Algorithmen mit drei Stapeln UND die anderen auferlegten Einschränkungen (wie die Nichtverwendung einer faulen Auswertung) kenne. Er kannte einen Algorithmus mit 6 Stapel, wie wir bereits wissen, wenn wir uns die Antworten hier ansehen. Ich denke, die Frage ist noch offen, um einen Algorithmus zu finden (oder zu beweisen, dass einer nicht gefunden werden kann). "

antti.huima
quelle
Ich bin gerade über die Papiere und Programme in Ihrem Link geflogen. Aber wenn ich richtig sehe, verwenden sie keine Stapel, sondern Listen als Basistyp. Und insb. in diesen Listen sind mit Header und Rest aufgebaut, so dass es im Grunde meiner Lösung ähnlich sieht (und ich denke, ist nicht richtig).
Flolo
1
Hallo, die Implementierungen sind in einer funktionalen Sprache, in der Listen Stapeln entsprechen, solange Zeiger nicht gemeinsam genutzt werden und dies nicht der Fall ist. Die Sechs-Stapel-Version kann wirklich mit sechs "einfachen" Stapeln implementiert werden. Das Problem bei der Zwei- / Drei-Stapel-Version besteht darin, dass versteckte Datenstrukturen (Closures) verwendet werden.
Antti Huima
Sind Sie sicher, dass die Six-Stack-Lösung keine Zeiger gemeinsam nutzt? In rotatesieht es so aus, als würde die frontListe beiden oldfrontund zugewiesen f, und diese werden dann separat geändert.
Interjay
14
Das Quellmaterial unter algs4.cs.princeton.edu/13stacks wurde geändert: 43. Implementieren Sie eine Warteschlange mit einer konstanten Anzahl von [nicht "3"] Stapeln, sodass für jede Warteschlangenoperation eine konstante Anzahl von Stapeln (im schlimmsten Fall) erforderlich ist Operationen. Warnung: hoher Schwierigkeitsgrad. Der Titel der Herausforderung lautet jedoch weiterhin "Warteschlange mit drei Stapeln" :-).
Mark Peters
3
@AnttiHuima Der Sechs-Stapel-Link ist tot. Weißt du, ob dieser irgendwo existiert?
Quentin Pradet
12

Ok, das ist wirklich schwer, und die einzige Lösung, die ich finden konnte, erinnert mich an Kirks Lösung für den Kobayashi Maru-Test (irgendwie betrogen): Die Idee ist, dass wir Stapel von Stapeln verwenden (und dies verwenden, um eine Liste zu modellieren ). Ich rufe die Operationen en / dequeue und push and pop auf, dann bekommen wir:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY ist kein Kopieren des Inhalts, sondern nur eine Kopie der Referenz. Es dient nur zur einfachen Beschreibung. Sie können auch ein Array von 3 Stapeln verwenden und über den Index darauf zugreifen. Dort würden Sie nur den Wert der Indexvariablen ändern ). Alles ist in O (1) in Bezug auf die Stapeloperation.

Und ja, ich weiß, dass es fraglich ist, weil wir mehr als 3 Stapel impliziert haben, aber vielleicht gibt es anderen von Ihnen gute Ideen.

EDIT: Erklärungsbeispiel:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Ich habe hier mit ein wenig ASCII-Kunst versucht, Stack1 zu zeigen.

Jedes Element wird in einen einzelnen Elementstapel eingeschlossen (wir haben also nur einen typsicheren Stapelstapel).

Sie sehen, um zu entfernen, platzieren wir zuerst das erste Element (den Stapel, der hier Element 1 und 2 enthält). Dann Pop das nächste Element und dort die 1 auspacken. Danach sagen wir, dass der erste Poped Stack jetzt unser neuer Stack1 ist. Um es etwas funktionaler zu sagen: Dies sind Listen, die durch Stapel von 2 Elementen implementiert werden, wobei das oberste Element cdr und das erste / unterste obere Element car ist . Die anderen 2 helfen Stapeln.

Besonders schwierig ist das Einfügen, da Sie irgendwie tief in die verschachtelten Stapel eintauchen müssen, um ein weiteres Element hinzuzufügen. Deshalb ist Stack2 da. Stack2 ist immer der innerste Stack. Beim Hinzufügen wird dann nur ein Element hineingeschoben und dann auf einen neuen Stack2 geschoben (und deshalb dürfen wir Stack2 in unserer Warteschlangenoperation nicht berühren).

flolo
quelle
Möchten Sie erklären, wie es funktioniert? Vielleicht nachverfolgen, wie man 'A', 'B', 'C', 'D' drückt und dann viermal auftaucht?
MAK
1
@Iceman: Kein Stack2 ist richtig. Sie gehen nicht verloren, da sich Stack immer auf den innersten Stack in Stack1 bezieht, sodass sie in Stack1 immer noch impliziert sind.
Flolo
3
Ich bin damit einverstanden, dass es betrügt :-). Das sind nicht 3 Stapel, sondern 3 Stapelreferenzen. Aber eine angenehme Lektüre.
Mark Peters
1
Es ist ein cleveres Schema, aber wenn ich es richtig verstehe, werden am Ende n Stapel benötigt, wenn n Elemente in die Warteschlange gestellt werden. Die Frage fragt nach genau 3 Stapeln.
MAK
2
@MAK: Ich weiß, deshalb habe ich ausdrücklich angegeben, dass es betrogen wurde (ich habe sogar den Ruf für ein Kopfgeld ausgegeben, weil ich auch neugierig auf die wirkliche Lösung bin). Aber zumindest der prusswanische Kommentar kann beantwortet werden: Die Anzahl der Stapel ist wichtig, da meine Lösung tatsächlich gültig ist, wenn Sie so viel verwenden können, wie Sie möchten.
Flolo
4

Ich werde einen Beweis versuchen, um zu zeigen, dass dies nicht möglich ist.


Angenommen, es gibt eine Warteschlange Q, die durch 3 Stapel A, B und C simuliert wird.

Behauptungen

  • ASRT0: = Nehmen wir außerdem an, dass Q Operationen {queue, dequeue} in O (1) simulieren kann. Dies bedeutet, dass für jede zu simulierende Warteschlangen- / Warteschlangenoperation eine bestimmte Folge von Stack-Push / Pops vorhanden ist.

  • Nehmen Sie ohne Verlust der Allgemeinheit an, dass die Warteschlangenoperationen deterministisch sind.

Lassen Sie die in Q in die Warteschlange gestellten Elemente basierend auf ihrer Reihenfolge der Warteschlangen mit 1, 2, ... nummerieren, wobei das erste in Q in die Warteschlange gestellte Element als 1, das zweite als 2 usw. definiert wird.

Definieren

  • Q(0) := Der Zustand von Q, wenn 0 Elemente in Q vorhanden sind (und somit 0 Elemente in A, B und C)
  • Q(1) := Der Zustand von Q (und A, B und C) nach 1 Warteschlangenoperation ein Q(0)
  • Q(n) := Der Zustand von Q (und A, B und C) nach n Warteschlangenoperationen an Q(0)

Definieren

  • |Q(n)| :=die Anzahl der Elemente in Q(n)(daher |Q(n)| = n)
  • A(n) := der Zustand des Stapels A, wenn der Zustand von Q ist Q(n)
  • |A(n)| := die Anzahl der Elemente in A(n)

Und ähnliche Definitionen für die Stapel B und C.

Trivial,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| ist offensichtlich unbegrenzt auf n.

Daher mindestens eines von |A(n)|, |B(n)|oder |C(n)|unbeschränkt auf n.

WLOG1Angenommen, Stapel A ist unbegrenzt und Stapel B und C sind begrenzt.

Definiere * B_u :=eine Obergrenze von B * C_u :=eine Obergrenze von C *K := B_u + C_u + 1

WLOG2Wählen Sie für ein n so aus, dass |A(n)| > KSie K Elemente aus auswählen Q(n). Angenommen, eines dieser Elemente befindet sich A(n + x)für alle x >= 0, dh das Element befindet sich immer im Stapel A, unabhängig davon, wie viele Warteschlangenoperationen ausgeführt werden.

  • X := dieses Element

Dann können wir definieren

  • Abv(n) :=Die Anzahl der Elemente im Stapel A(n)liegt über X.
  • Blo(n) :=Die Anzahl der Elemente im Stapel A(n)liegt unter X.

    | A (n) | = Abv (n) + Blo (n)

ASRT1 :=Die Anzahl der Pops, die erforderlich sind, um X aus der Warteschlange zu entfernen, Q(n)beträgt mindestensAbv(n)

Von ( ASRT0) und ( ASRT1) ASRT2 := Abv(n)muss begrenzt werden.

Wenn Abv(n)es unbegrenzt ist, wenn mindestens 20 Warteschlangen erforderlich sind, um X aus der Warteschlange zu entfernen Q(n), sind mindestens Abv(n)/20Pops erforderlich . Welches ist unbegrenzt. 20 kann eine beliebige Konstante sein.

Deshalb,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

muss unbegrenzt sein.


WLOG3können wir die K-Elemente unten auswählen A(n), und eines davon ist A(n + x)für alle dax >= 0

X(n) := dieses Element für jedes gegebene n

ASRT4 := Abv(n) >= |A(n)| - K

Immer wenn ein Element in die Warteschlange gestellt wird Q(n)...

WLOG4Angenommen, B und C sind bereits bis zu ihren oberen Grenzen gefüllt. Angenommen, die Obergrenze für die obigen Elemente X(n)wurde erreicht. Dann tritt ein neues Element in A ein.

WLOG5Angenommen, das neue Element muss als Ergebnis unten eingegeben werden X(n).

ASRT5 := Die Anzahl der Pops, die erforderlich sind, um ein Element darunter zu platzieren X(n) >= Abv(X(n))

Von (ASRT4), Abv(n)ist unbegrenzt auf n.

Daher ist die Anzahl der Pops, die erforderlich sind, um ein Element darunter zu platzieren, X(n)unbegrenzt.


Dies widerspricht ASRT1daher, dass es nicht möglich ist, eine O(1)Warteschlange mit 3 Stapeln zu simulieren .


Dh

Mindestens 1 Stapel muss unbegrenzt sein.

Für ein Element, das in diesem Stapel verbleibt, muss die Anzahl der darüber liegenden Elemente begrenzt werden. Andernfalls ist die Dequeue-Operation zum Entfernen dieses Elements unbegrenzt.

Wenn jedoch die Anzahl der darüber liegenden Elemente begrenzt ist, erreicht sie eine Grenze. Irgendwann muss ein neues Element darunter eintreten.

Da wir das alte Element immer aus einem der niedrigsten Elemente dieses Stapels auswählen können, kann es eine unbegrenzte Anzahl von Elementen darüber geben (basierend auf der unbegrenzten Größe des unbegrenzten Stapels).

Um ein neues Element darunter einzugeben, ist eine unbegrenzte Anzahl von Elementen erforderlich, um das neue Element darunter zu platzieren, da sich eine unbegrenzte Anzahl von Elementen darüber befindet.

Und damit der Widerspruch.


Es gibt 5 WLOG-Anweisungen (ohne Verlust der Allgemeinheit). In gewissem Sinne können sie intuitiv als wahr verstanden werden (aber wenn sie 5 sind, kann es einige Zeit dauern). Der formale Beweis, dass keine Allgemeinheit verloren geht, kann abgeleitet werden, ist aber äußerst langwierig. Sie werden weggelassen.

Ich gebe zu, dass eine solche Auslassung die fraglichen WLOG-Aussagen belassen könnte. Bei der Paranoia eines Programmierers für Fehler überprüfen Sie bitte die WLOG-Anweisungen, wenn Sie möchten.

Der dritte Stapel ist ebenfalls irrelevant. Was zählt, ist, dass es eine Reihe von begrenzten Stapeln und eine Reihe von unbegrenzten Stapeln gibt. Das für ein Beispiel erforderliche Minimum beträgt 2 Stapel. Die Anzahl der Stapel muss natürlich endlich sein.

Wenn ich recht habe, dass es keinen Beweis gibt, sollte es einen einfacheren induktiven Beweis geben. Wahrscheinlich basierend auf dem, was nach jeder Warteschlange passiert (verfolgen Sie, wie sich dies auf den schlimmsten Fall der Warteschlange auswirkt, wenn alle Elemente in der Warteschlange vorhanden sind).

Dingfeng Quek
quelle
2
Ich denke, dass der Beweis für diese Annahmen funktioniert - aber ich bin nicht sicher, ob alle Stapel leer sein müssen, damit die Warteschlange leer ist, oder ob die Summe der Stapelgrößen der Größe der Warteschlange entsprechen muss.
Mikeb
3
"WLOG1, nehmen wir an, Stapel A ist unbegrenzt und Stapel B und C sind begrenzt." Sie können nicht davon ausgehen, dass einige der Stapel begrenzt sind, da dies sie wertlos machen würde (sie wären mit O (1) zusätzlichem Speicher identisch).
Interjay
3
Manchmal sind die trivialen Dinge nicht so trivial: | Q | = | A | + | B | + | C | ist nur richtig, wenn Sie annehmen, dass Sie für jeden Eintrag in Q genau einen in A, B oder C hinzufügen, aber es kann sein, dass es sich um einen Algorithmus handelt, der ein Element immer zweimal zu zwei Stapeln oder sogar zu allen drei hinzufügt. Und wenn es so funktioniert, hält Ihr WLOG1 nicht mehr (stellen Sie sich C eine Kopie von A vor (nicht, dass es Sinn macht, aber vielleicht gibt es einen Algorithmus mit einer anderen Reihenfolge oder was auch immer ...)
flolo
@flolo und @mikeb: Ihr beide habt recht. | Q (n) | sollte definiert werden als | A (n) | + | B (n) | + | C (n) |. Und dann | Q (n) | > = n. Anschließend würde der Beweis mit n funktionieren und beachten, dass solange | Q (n) | größer gilt die Schlussfolgerung.
Dingfeng Quek
@interjay: Du kannst 3 unbegrenzte Stapel und keine begrenzten Stapel haben. Anstelle von "B_u + C_u + 1" kann der Beweis dann einfach "1" verwenden. Grundsätzlich stellt der Ausdruck "Summe der Obergrenze in begrenzten Stapeln + 1" dar, daher spielt die Anzahl der begrenzten Stapel keine Rolle.
Dingfeng Quek
3

Hinweis: Dies soll ein Kommentar zur funktionalen Implementierung von Echtzeitwarteschlangen (Worst-Case mit konstanter Zeit) mit einfach verknüpften Listen sein. Ich kann aufgrund des guten Rufs keine Kommentare hinzufügen, aber es wäre schön, wenn jemand dies in einen Kommentar ändern könnte, der an die Antwort von antti.huima angehängt ist. Andererseits ist es etwas lang für einen Kommentar.

@ antti.huima: Verknüpfte Listen sind nicht dasselbe wie ein Stapel.

  • s1 = (1 2 3 4) --- eine verknüpfte Liste mit 4 Knoten, die jeweils auf den rechten zeigen und die Werte 1, 2, 3 und 4 enthalten

  • s2 = geknallt (s1) --- s2 ist jetzt (2 3 4)

Zu diesem Zeitpunkt entspricht s2 popped (s1), das sich wie ein Stapel verhält. S1 steht jedoch weiterhin als Referenz zur Verfügung!

  • s3 = geknallt (geknallt (s1)) --- s3 ist (3 4)

Wir können immer noch in s1 schauen, um 1 zu erhalten, während in einer ordnungsgemäßen Stack-Implementierung Element 1 von s1 weg ist!

Was bedeutet das?

  • s1 ist die Referenz auf die Oberseite des Stapels
  • s2 ist die Referenz auf das zweite Element des Stapels
  • s3 ist der Verweis auf den dritten ...

Die jetzt erstellten zusätzlichen verknüpften Listen dienen jeweils als Referenz / Zeiger! Eine endliche Anzahl von Stapeln kann das nicht.

Nach dem, was ich in den Artikeln / im Code sehe, nutzen alle Algorithmen diese Eigenschaft von verknüpften Listen, um Referenzen beizubehalten.

Bearbeiten: Ich beziehe mich nur auf die Algorithmen für verknüpfte Listen 2 und 3, die diese Eigenschaft von verknüpften Listen verwenden, da ich sie zuerst gelesen habe (sie sahen einfacher aus). Dies soll nicht zeigen, dass sie anwendbar sind oder nicht, sondern nur erklären, dass verknüpfte Listen nicht unbedingt identisch sind. Ich werde die mit 6 lesen, wenn ich frei bin. @ Welbog: Danke für die Korrektur.


Faulheit kann auf ähnliche Weise auch Zeigerfunktionen simulieren.


Die Verwendung einer verknüpften Liste löst ein anderes Problem. Diese Strategie kann verwendet werden, um Echtzeitwarteschlangen in Lisp zu implementieren (oder zumindest Lisps, die darauf bestehen, alles aus verknüpften Listen zu erstellen): Siehe "Echtzeitwarteschlangenoperationen in Pure Lisp" (verknüpft über die Links von antti.huima). Es ist auch eine gute Möglichkeit, unveränderliche Listen mit O (1) -Operationszeit und gemeinsam genutzten (unveränderlichen) Strukturen zu entwerfen.

Dingfeng Quek
quelle
1
Ich kann nicht mit den anderen Algorithmen in anttis Antwort sprechen, aber die Sechs-Stapel-Lösung mit konstanter Zeit ( eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml ) verwendet diese Eigenschaft von Listen nicht , da ich es mit java.util.StackObjekten in Java neu implementiert habe . Der einzige Ort, an dem diese Funktion verwendet wird, ist eine Optimierung, die es ermöglicht, unveränderliche Stapel in konstanter Zeit zu "duplizieren", was Basis-Java-Stapel nicht können (aber in Java implementiert werden können), da es sich um veränderbare Strukturen handelt.
Welbog
Wenn es sich um eine Optimierung handelt, die den Rechenaufwand nicht verringert, sollte dies keinen Einfluss auf die Schlussfolgerung haben. Ich bin froh, endlich eine Lösung zu haben, um sie zu überprüfen: Aber ich lese nicht gerne SML. Möchten Sie Ihren Java-Code teilen? (:
Dingfeng Quek
Es ist keine endgültige Lösung, da leider sechs statt drei Stapel verwendet werden. Es könnte jedoch möglich sein zu beweisen, dass sechs Stapel eine minimale Lösung sind ...
Welbog
@ Welbog! Können Sie Ihre 6-Stack-Implementierung freigeben? :) Es wäre cool, es zu sehen :)
Antti Huima
1

Sie können dies in amortisierter konstanter Zeit mit zwei Stapeln tun:

------------- --------------
            | |
------------- --------------

Hinzufügen ist O(1)und Entfernen ist, O(1)wenn die Seite, von der Sie nehmen möchten, nicht leer ist und O(n)ansonsten (teilen Sie den anderen Stapel in zwei Teile).

Der Trick besteht darin, zu sehen, dass die O(n)Operation nur jedes O(n)Mal ausgeführt wird (wenn Sie teilen, z. B. in zwei Hälften). Daher beträgt die durchschnittliche Zeit für eine Operation O(1)+O(n)/O(n) = O(1).

Dies mag zwar problematisch sein, aber wenn Sie eine zwingende Sprache mit einem Array-basierten Stapel (am schnellsten) verwenden, haben Sie ohnehin nur konstante Zeit amortisiert.

Thomas Ahle
quelle
Zur ursprünglichen Frage: Das Teilen eines Stapels erfordert tatsächlich einen zusätzlichen Zwischenstapel. Dies könnte der Grund sein, warum Ihre Aufgabe drei Stapel umfasste.
Thomas Ahle