Zum Sortieren eines Stapels mit nur Push, Pop, Top, IsEmpty, IsFull?

Gegeben ein Stapel S, muss Sortieren der Stapel, mit nur Push, Pop, Top, IsEmpty, IsFull.

Auf der Suche für die einfachste Lösung.

Bearbeitet werden: Entfernt im Ort Zustand. Können nicht verwenden Sie einen anderen Stapel oder Warteschlange.

wenn diese Hausaufgaben, bitte markieren Sie Sie als solche
Nein ist es nicht!!!
Einfach. Pop alles in einen Vektor, Sortieren, schieben Sie es alles zurück. Version 2 entledigt sich der stack, weil es die falsche Datenstruktur. Tun es auf andere Weise ist nur interessant für Hausaufgaben.
Können Sie ändern die Datenstruktur?
Nein können wir nicht.
Können Sie mehr als einen stack?
Nein verwenden können ein weiterer stack oder queue.
Einsatz von zusätzlichen Arrays ist nicht erlaubt. Nicht bedienen, SO dass für diese Lösung würde ich..
Das klingt wie eine furchtbar gemeinsame Hausaufgaben-problem. Welche Art von Unternehmen oder Programmieren würde, verbieten Sie von der Nutzung zusätzlicher Speicher? Nicht die änderung der primären Struktur der Daten, sicher, (Teil von jemand anderem interface), aber nicht in der Lage, zum erstellen von sekundären Speicher? Recht. Zugegeben, die Hausaufgaben, die Präsentation ist lösbar, während Ihnen nicht. Wenn es keine Hausaufgaben sind, warum sind Sie platzieren eine solche schwere Einschränkungen auf sich?
das ist einfach nur völliger Unsinn. Der stack besteht kein Zweifel, wurde mit Hilfe eines Arrays, Sortieren Sie die frikkin array. Ich glaube nicht für eine minute, dies ist keine Hausaufgaben Frage, die Abstimmung zu schließen.
gut, wenn Sie call-Vorbereitung für Vorstellungsgespräche, wie Hausaufgaben, dann ist es, dass nur. Wenn Sie nicht über eine Lösung - das ist auch OK so. Nehmen Sie es nicht als einen Fehler. Es gibt viele Helfer, SO dass Benutzer, die versuchen, mir zu helfen. Trotzdem danke.
Nun, wenn Sie Jungs haben, mal schauen link in Anthony ' s Antwort. Es gibt eine Lösung, die nur mit zwei Variablen zu Sortieren eines Stacks.
Bitte rufen Sie nicht an eine Frage, wie 'völliger Quatsch'. Das einzige, was völliger non sense hier ist Ihr Kommentar. Sie besitzen nicht SO OK!!!!
Ankit, Nein, Anthony die Antwort verwendet einen zweiten Stapel.
Vermutlich ist es akzeptabel, zu verwenden, was den Mechanismus Sprache bietet die Verknüpfung der call-frames zusammen. (Ja, dies ist in der Regel, aber nicht immer ein stack) So, schreiben oder zitieren Sie eine rekursive Lösung, und nennen es einen Tag. Es ist sicherlich möglich, zu lösen mit einem halbwegs vernünftigen, wenn nicht allzu strenger Auslegung sogar die ursprünglichen unbearbeiteten Zustand. Ich habe es getan.
Wir sind nicht die Erstellung von neuen Tags für eine Frage, wenn ein geeigneter tag existiert.
Ich denke, eine "zweite Stapel" oder "in-place" bedeutet einfach, dass Sie nicht verwenden können, ein anderes Aggregat-Daten-Struktur, der eine ähnliche Größe. Dies ist eine durchaus vernünftige Frage, und es hat eine ziemlich einfache Antwort.
Wow es gibt eine Menge von kritischen Menschen gibt. Wer kümmert sich, wenn es die Hausaufgaben, interview, aktuelle Arbeit, oder einfach nur someong gelangweilt aus seinem Geist zu entscheiden, um code zu schreiben, als auf ein date gehen? Die Frage ist gestellt. Wenn Sie nicht denken, es lohnt sich Ihre kostbare Zeit, die dann nicht reagieren, aber vergeuden Sie nicht, die gleiche kostbare Zeit, jammern und Klagen, Sie hätten zu nehmen, wertvolle Zeit aus Ihrem Tag zu Lesen, über ein problem, das Sie lösen konnte nicht vor ein paar Jahren.
Ich kann nicht für andere sprechen, aber ich persönlich egal, so oder so. Was mich ärgert ist, wenn Leute Fragen, offensichtliche test-basierte Frage, sei es Hausaufgaben machen oder etwas anderes, dann verweigern Sie jede Art von Befragung oder geben keine ehrliche Antwort. Seien Sie direkt und sagen, dass es Hausaufgaben/interview rezension/etc. nicht schlagen, um es.
Eh. Mein Punkt ist. Wer gibt einen rip? Eine Frage ist eine Frage. Tun Sie wirklich brauchen, zu wissen, warum, um Sie zu beantworten? Ich sehe eine Tonne von Fragen, die beantwortet werden konnten, einfach wenn die person, eingegeben in Google. Was ich nicht mache (in der Regel, aber in diesem Fall scheint die Ausnahme zu sein), ist Verschwendung von Zeit wonking darüber. Ich Ignoriere die Frage und bewegen auf.
I don ' T care, ich war nicht der, der zu Fragen wenn es Hausaufgaben. 😛 Aber einmal war es gefragt, die das Verhalten nervte mich.
Woah!! "Verhalten nervte" ihn. Grandios!! Sehen Sie, ich änderte meinen Griff um 'homeWorkBoy'. Nun, jede Frage, die ich als Hausaufgaben Frage. 😀 - OP (Ankit)
Wäre es nicht toll, wenn @GMan änderte seinen Griff um 'GMan_thePolice'. Helfen, den kleinen wie uns, die sich richtig Verhalten, wenn er Rum 😀 🙂
Deine Reife scheint wie ein fels in eine Höhle.
Jetzt würde der rock glänzen, wenn es war eine Kohle. So sollten Sie haben gesagt, Sie wie ein Diamant in der Höhle. Shine on you crazy diamond kann sein :). Und wer will schon reif zu sein 😉
Einen Punkt gut gemacht.
Keine eigene Anstrengung gezeigt. -1.

InformationsquelleAutor AJ. | 2010-01-30

8

Es kann getan werden...

Ok: sortiert, ähem, "in-place" und nur mit den aufgeführten ops trifft nicht brauchen, Oben() oder IsFull() oder einen anderen stack oder Daten-Struktur, die andere als die call-frames. (Vermutlich der springende Punkt der ~~Hausaufgaben~~ problem war, erfordern eine rekursive Lösung.)

Ruby
```
@a = [3, 2, 1, 6, 5, 4]

class Array
  def empty?
    return size == 0
  end
end

def sort e
  if @a.empty?
    @a.push e
    return
  end
  t = @a.pop
  if e > t
    @a.push(t).push(e)
    return
  end
  sort e
  @a.push t
end

def resort
  return if @a.empty?
  t = @a.pop
  resort
  sort t
end

p ['first ', @a]
resort
p ['final ', @a]
```
- Deshalb werden diese Werke durch die Definition von zwei sort-Funktionen: resort die nicht davon ausgehen, dass der stack ist bereits sortiert und sort die nicht. Beide arbeiten, indem Sie rekursiv knallen ein element ab, bis Ihr Ziel erreicht ist. Im Falle der top-level - resort es das Ziel ist, entfernen Sie alles und bauen es wieder auf, durch den Aufruf sort, und sort Werke von recursing gerade weit genug, um ein einzelnes element. Ich denke, dies war der Sinn der übung.
- Sie sind mit extra-Speicher; sicherlich nicht explizit organisiert als stack (eher versteckt in den call-stack), aber ich bin gespannt, ob die OP ' s zufrieden.
- Sicher, aber ich denke, dass war beabsichtigt. Vielleicht wäre diese Lösung offensichtlich für einige Leute, aber ich hatte ein bisschen denken, um dieses zu erhalten. Es ist ein lustiges problem und ich vermute, dass es entworfen wurde, zu verlangen ziemlich viel für diese Lösung.
InformationsquelleAutor DigitalRoss

Für dieses problem, können wir prüfen, mit dem system-stack? Mehrere rekursive Aufrufe.

public static void sort(Stack<Integer> s) {
    if (!s.isEmpty()) {
        Integer t = s.pop();
        sort(s);
        insert(t, s);
    }
}

private static void insert(Integer x, Stack<Integer> s) {
    if (s.isEmpty()) {
        s.push(x);
        return;
    }

    if (x < s.peek()) {
        Integer t = s.pop();
        insert(x, s);
        s.push(t);
    } else {
        s.push(x);
    }
}

InformationsquelleAutor SiLent SoNG

4

techInterview Diskussion - Sortierung auf Stapel

Mehr pseudo als alles andere, aber es gibt code-Beispiele und mögliche Lösung.
- Ich sehe nicht, wie das in-place. In-place bedeutet, dass Sie nicht erzeugen jede extra Speicher, speichern Sie ein paar Variablen in O(1) Speicherplatz.
- OP entfernt hatte, die anstelle Zustand
- Menschen wirklich brauchen, um wie weit eine interpretation der Bedingungen, die nötig sind, um das problem zu lösen. Natürlich, in diesem Fall, in der-statt, das bedeutet, dass andere ähnlich große Aggregat wurde nicht verwendet werden, so daß eine rekursive Lösung mit einer temporären lokalen variable oder zwei in einem bestimmten frame-Instanz. Nichts wird gewonnen, indem ein literal oder übermäßig pedantisch Blick auf das problem der offensichtlich-das unbeabsichtigte extreme, erlauben keine Lösung.
- Wenn die Frage wollte eine rekursive Antwort, dann IMO macht es mehr Sinn das so zu sagen, statt der Einführung der sehr verwirrenden Zustand "implementieren muss dies in einer Weise, die in einer imperativen Sprache, ist ziemlich sicher noch schlimmer sein, in jedem einzelnen Weg, als mit einem zweiten Daten-Struktur". Natürlich ist das eine Beschwerde über die interview-Teilnehmer im Allgemeinen eher als diese Frage im besonderen 🙂
InformationsquelleAutor Anthony Forloney
3

Nicht möglich.

Das geschieht, weil Sie nicht Durchlaufen, den stack, weil es im Ort (Sie könnten, wenn Sie verwenden würden, extra-Speicher). So wenn Sie nicht Durchlaufen Sie die stack-Sie können nicht einmal vergleichen Sie zwei Elemente auf dem stack. Eine Art ohne Vergleich würde müssen zusätzlichen Speicher, so dass kann nicht verwendet werden, entweder.

Auch im sicher, dass seine Hausaufgaben nicht, weil ich glaube nicht, dass ein Lehrer Ihnen wäre ein problem, dass nicht gelöst werden.

Wenn Sie wirklich müssen tun Sie es nur mit stacks, verwenden Sie einfach 1-2 zusätzliche temporäre Stapel (ich denke, 2 sind gebraucht, aber nicht 100% sicher) und es tun.
- Außer, ich habe es einfach gemacht. Vermutlich eine rekursive Lösung war die beabsichtigte Lösung, auch wenn dies erfordert sicherlich eine Art hinter-den-kulissen-Daten-Struktur. Ich denke, es ist am besten mit dieser Art von problem durch kommen mit irgendeiner Art von Lösung, die in einige Art und Weise die Kriterien erfüllt. Ich bezweifle, dass der prof wird zu sehr von "es ist unmöglich".
- Als Sie sagte, Sie ein "hinter-den-kulissen" - Daten-Struktur, die auf dem Aufruf-stack. Sollte ich vielleicht besser sagen, es ist nicht möglich, mit iteration, aber möglich mit Rekursion 🙂 . Edit: auch meine Antwort, wenn er wollte, eine in-place-Lösung (jetzt hat er das Thema gewechselt), die nicht mit Rekursion, da in-place-der Raum muss eine Konstante sein (was es nicht wird, weil Sie so viel stack-Speicher, den Sie wollen).
InformationsquelleAutor George
3

Was für temporäre Daten-Strukturen können Sie nutzen?
Mit push und pop, und kein temporärer Speicher für n Elemente, Zugriff auf Daten, die in der Nähe der Unterseite des Stapels wäre unmöglich ohne die Speicherung des rest -irgendwo-.

Wenn top (equiv zu {x=pop();push(x);return x}) ersetzt wurde mit shift wäre es perfekt machbar - der Stapel würde sich ändern, in den fifo-Speicher (shift+push, pop würde in Vergessenheit fallen) und es erlauben würde, für eine einfache bubblesort auf den aktuell verfügbaren Elemente.

InformationsquelleAutor SF.
2

Können Sie nicht. Sie können nicht Sortieren Sie die Inhalte von einem Stapel, ohne entfernen von Elementen, per definition. Auch push und pop sind nicht in-place-Operationen, so dass im Grunde Sie Fragen zu Sortieren eines Stacks mit Top, IsEmpty und IsFull. ~~IsEmpty = !IsFull. So Fragen Sie zum Sortieren eines Stacks mit Top und IsEmpty.~~
- Err, dein statement auf IsEmpty und IsFull falsch ist (für die meisten stacks). Wenn der stack nicht leer ist, ist es nicht unbedingt voll (es sei denn, es ist ein one-element-stack). 🙂
- Warum nicht push und pop in-place-Operationen?
- gut, um Zugriff auf das N-te element, das Sie benötigen, um pop-n-1 Elemente. der n hängt von der input-Größe, so ist es nicht Konstante Größe der Speicherzuordnung daher nicht in-place.
- Ich denke, es ist möglich, es zu tun "in-place", für eine bestimmte definition. Siehe meine gepostete Antwort und meinem Kommentar über George ' s Antwort.
InformationsquelleAutor Chris H
2

Schlechten Sie nicht haben konnte beiden anderen Stapel, dann könnte man gespielt haben, die Türme von Hanoi in O(n) Speicherplatz.

InformationsquelleAutor Albin Sunnanbo

//Eine java-version

public static void sort(Stack<Integer> s){
    if(s.size() > 0){
        int tmp = s.pop();
        sort(s);
        sortFromBottom(s, tmp);
    }
}

private static void sortFromBottom(Stack<Integer> s, Integer value){
    if(s.size() == 0){
        s.add(value);
    }else{
        int tmpValue = s.peek();
        if(tmpValue < value){
            s.pop();
            sortFromBottom(s, value);
            s.push(tmpValue);
        }else{
            s.push(value);
        }
    }
}

InformationsquelleAutor Jiaji Li

Bubble-Sort und Insert-Sort in Java
https://github.com/BruceZu/sawdust/blob/82ef4729ee9d2de50fdceab2c8976d00f2fd3ba0/dataStructuresAndAlgorithms/src/main/java/stack/SortStack.java

 /**
  * Sort the stack using only Stack API, without using other data structure
  * Ascending from bottom to top
 */
public class SortStack<T extends Comparable<T>> {
 int sorted;

/**
 * Just Bubble Sort.
 */
private void bubble(Stack<T> s, T max) {
    if (s.empty() || s.size() == sorted) {
        s.push(max);
        sorted++;
        return; //note return
    }

    T currentTop = s.pop();
    if (max.compareTo(currentTop) < 0) {
        T tmp = max;
        max = currentTop;
        currentTop = tmp;
    }

    bubble(s, max);
    s.push(currentTop);
}

public Stack<T> sortAscending(Stack<T> s) {
    sorted = 0;
    if (s == null || s.size() <= 1) {
        return s;
    }

    while (sorted != s.size()) {
        bubble(s, s.pop());
    }
    return s;
}

/**
 * Just Insert Sort.
 */
private void insertSort(Stack<T> s) {
    if (s.empty()) {
        return;
    }
    T currentTop = s.pop();
    insertSort(s);
    insert(s, currentTop);
}

private void insert(Stack<T> s, T insert) {
    if (s.isEmpty() || insert.compareTo(s.peek()) <= 0) {
        s.push(insert);
        return;
    }

    T current = s.pop();
    insert(s, insert);
    s.push(current);
}

public Stack<T> sortAscendingByInsertSort(Stack<T> s) {
    if (s == null || s.size() <= 1) {
        return s;
    }
    insertSort(s);
    return s;
 }
}

InformationsquelleAutor Bruce Zu

Sortieren stapeln ohne zusätzliche Raum ist durchaus nicht eine Möglichkeit .
Zumindest keine, die zu meiner sane mind .
Wir können sicherlich die Verwendung der rekursions-stack als zusätzlichen Platz hier .
Die unter Ansatz könnte helful .

Mein Ansatz ist O(N**2) . Hier bin ich der Iteration über stack-N mal, jedes mal die Befestigung der I-TEN element in den stack .

Erstens fest das element unten durch, knallend aus N Elementen, und drücken min_element und in
Zweiten Versuch behoben, das 2. element von unten durch, knallend aus N-1 Elementen und schob min_element außer das man geschoben, bevor diese
Und so weiter .

Finden Sie den code unten für mehr details .

    stack<int> stk;
    int sort_util(stack<int> &stk,int n,int mn)
    {
        if(n==0)
        {
            stk.push(mn);
            return mn;
        }

        int vl = stk.top();
        stk.pop();

        int fmin = sort_util(stk,n-1,min(mn,vl));

        if(fmin==vl)
            return INT_MAX;
        else
            stk.push(vl);

        return fmin;
    }

    void sort_stack(stack<int> &stk)
    {
        for(int i=stk.size();i>1;i--)
            sort_util(stk,i,stk.top());
    }

InformationsquelleAutor dhruvsharma

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Es kann getan werden...

Ruby