Ok: sortiert, ähem, "in-place" mit nur den aufgelisteten Ops, brauchte nicht Top () oder IsFull () oder einen anderen Stack oder eine andere Datenstruktur als die Callframes. (Vermutlich war der Hauptpunkt des Problems
Können wir bei diesem Problem den Systemstack in Betracht ziehen? Mache mehrere rekursive Aufrufe.
%Vor%techInterview-Diskussion - Sortieren nach Stack
Mehr Pseudo als alles andere, aber es gibt Codebeispiele und mögliche Lösungen.
Es ist nicht möglich.
Das passiert, weil Sie nicht durch den Stack iterieren können, weil es an Ort und Stelle sein muss (Sie könnten, wenn Sie zusätzlichen Speicher verwenden würden). Wenn Sie also nicht durch den Stapel iterieren können, können Sie sogar zwei Elemente des Stapels miteinander vergleichen. Eine Sortierung ohne Vergleich würde zusätzlichen Speicher benötigen, so dass auch keiner verwendet werden kann.
Ich bin mir auch sicher, dass es keine Hausaufgaben sind, weil ich nicht glaube, dass ein Lehrer Ihnen ein Problem geben würde, das nicht gelöst werden kann.
Wenn du es wirklich nur mit Stapeln machen musst, verwende einfach 1-2 zusätzliche temporäre Stapel (ich denke, dass 2 benötigt werden, aber nicht 100% sicher) und tu es.
Welche temporären Datenstrukturen können Sie verwenden? Mit Push und Pop und keinem temporären Speicher für n Elemente wäre der Zugriff auf Daten in der Nähe des unteren Teils des Stacks unmöglich, ohne den Rest - irgendwo - zu speichern.
Wenn top (äquivalent zu {x=pop();push(x);return x} ) durch shift ersetzt wurde, wäre es perfekt machbar - der Stapel würde sich in fifo ändern (shift + push; pop würde nicht mehr gebraucht) und es würde ein einfacher bubblesort auf aktuell verfügbaren Elementen.
Sie können nicht. Sie können den Inhalt eines Stapels nicht umdefinieren, ohne Elemente per Definition zu entfernen. Auch Push und Pop sind keine In-Place-Operationen, daher werden Sie im Grunde gebeten, einen Stack mit Top, IsEmpty und IsFull zu sortieren. IsEmpty =! IsFull. Sie möchten also einen Stapel mit Top und IsEmpty sortieren.
Zu schade, dass du nicht zwei andere Stapel haben könntest, dann hättest du die Türme von Hanoi in O spielen können ( n) Platz.
Das Sortieren eines Stapels ohne zusätzlichen Platz ist nicht möglich. Zumindest nicht in meinen gesunden Verstand kommen. Wir können den Rekursionsstapel sicherlich als zusätzlichen Raum hier verwenden. Der folgende Ansatz könnte hilfreich sein.
Mein Ansatz ist O (N ** 2). Hier wiederhole ich den Stack N-mal, jedes Mal, wenn ich das i-te Element im Stack fixiere.
Fixiere zuerst das untere Element, indem du N Elemente heraushebst und min_element und hinein drückst Zweiter Versuch, das 2. Element von unten zu fixieren, indem N-1 Elemente herausgedrückt werden und min_element mit Ausnahme des zuvor gedrückten gedrückt wird Und so weiter.
Weitere Informationen finden Sie im folgenden Code.
%Vor%Tags und Links algorithm c data-structures