Umkehren von Stack mit Python

Stornieren stack:

Machte ich einen leeren temporären stack
Ich verwendet tempstack.push(stack.pop())
und dann umbenannt zu stack = tempstack

aber es scheint nicht zu funktionieren. Irgendeine Idee warum?

Diesen Aufruf, den ich gerade nutzen will reverse(stack), nicht stack = reverse(stack).

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack = new_stack

stack = new_stack wird nur machen einen Unterschied in der Funktion, was auch immer Objekt, das Sie übergeben wird, bleibt davon unberührt. Betrachten return new_stack dann tun stack = reverse(stack) außerhalb.
gut, was andere Wege der Umbenennung oder mutierend new_stack in Stapel?
Haben Sie in Betracht gezogen, Lesen Sie in der Dokumentation für die Daten-Struktur, die Sie verwenden?
was ich sagen kann, Ihr eine Liste mit FIFO. Alles, was im fehlt? Ich möchte wirklich nicht, etwas zurückzugeben. Ich möchte nur die Reihenfolge der Werte in den stack. Aber es gibt keine Möglichkeit, dies zu tun, als zu speichern, die pop-Werte in eine temp-Daten-Struktur, die dann das umbenennen der temp-Daten-Struktur in das original meiner Meinung nach.
Ich denke, Sie sind fehlt @jonrsharpe Punkt. Sie sind nicht die Rückgabe der rückgängig-Stapel. Beim Aufruf von reverse (), die Sie einstellen sollte, gleich zu stapeln und im inneren reverse() liefert den modifizierten stack
Wenn Sie absolut nicht wollen, um einen Wert zurückzugeben, sollten Sie einen Blick auf dieser Frage.

InformationsquelleAutor | 2015-10-06

python stack

1

Als andere wies darauf hin, den letzten Auftrag macht nichts. Jedoch, die Idee hinter der übung ist hier wahrscheinlich nur die standard-stack-primitive push, pop, und is_empty, ohne sich auf die genaue stack-Implementierung zu nutzen list.reverse und so.

Der Schlüssel Punkt zu beachten ist, dass der stack ist ein last-in-first-out-Struktur, so dass das Lesen der Inhalt automatisch erzeugt Sie in umgekehrter Reihenfolge. Dies ist der Grund, warum eine Lösung mit einem anderen Stapel für die temporäre Speicherung funktioniert nicht:
```
def reverse(stack):
    # Doesn't work
    temp = Stack()
    while not stack.is_empty():
        temp.push(stack.pop())
    while not temp.is_empty():
        stack.push(temp.pop())
```
Hier die stack-Inhalte bekommen Umgekehrt zweimal: einmal, wenn Sie zu Lesen aus der original-stack, und einmal, wenn Sie Lesen, die Sie aus der temporären stack, so dass Sie am Ende mit stack-Inhalt in original-Reihenfolge. Tatsächlich reverse einem Stapel, müssen Sie extrahieren die Elemente in eine Liste und dann durchqueren Sie um (von Anfang bis Ende), schieben Sie die Elemente auf die ursprünglichen Stapel, wie Sie kommen:
```
def reverse(stack):
    items = []
    while not stack.is_empty():
        items.append(stack.pop())
    for item in items:
        stack.push(item)
```
Edit: inspiriert von BrianO ' s Antwort, hier ist eine version, die nicht die Verwendung einer Liste an alle (aber nicht instanziieren zwei temporäre Stapel):
```
def reverse(stack):
    tmp1 = Stack()
    while not stack.is_empty():
        tmp1.push(stack.pop())
    tmp2 = Stack()
    while not tmp1.is_empty():
        tmp2.push(tmp1.pop())
    while not tmp2.is_empty():
        stack.push(tmp2.pop())
```
Hier die Idee ist, machen sich die Tatsache zu nutze, dass das kopieren der stack ist Umgekehrt, die Inhalte nur zu kopieren zurück kehrt es wieder. So haben wir nur kopieren Sie Sie dreimal, zuerst aus dem original-stack, um eine temporäre stack, dann von einem temporären stack zu anderen temporären stack, und schließlich von den anderen temporären stapeln auf den ursprünglichen Stapel. Die Umkehrung der Inhalt drei mal endet mit den ursprünglichen Inhalten rückgängig gemacht, was erforderlich war.
- ahh das macht am meisten Sinn aus all den Antworten! Ich kann nicht glauben, ich coudlnt denke, dass dieser früher
- So können Sie Hilfs - lists, nachdem alle? Die Beschränkungen, die das problem wirklich nicht klar waren.
- Ich denke, die OP ' s Punkt war, dass er nicht einfach anrufen stack._items.reverse() (oder stack.reverse() wenn der stack implementiert wurden, wie eine Liste sich selbst). Diese Antwort gar nicht anmaßen, etwas über die Umsetzung von Stack. Noch, wie ich deine Antwort besser, weil es sich nicht auf eine externe Datenstruktur an alle, es tut seine Magie mit reiner Rekursion.
- Danke. Ja, irgendwann bekam ich es, dass die Stack Umsetzung soll undurchsichtig sein. Ich davon ausgegangen, dass ähnlich würde es "schummeln" (wie in, zu einfach) kopieren Sie die Elemente, um eine zwei-Wege-Struktur wie in einer Liste oder deque. Wenn die Frage ist eine Klasse Zuweisung, die OP werden es früh genug erfahren 😉 PS -- keine "Rekursion" beteiligt.
- PPS re "Rekursion" -- nahm mir einen moment Zeit, um zu sehen, was Sie bedeutete: die verschachtelte Aufrufe derselben Funktion. Da die Funktion nicht aufrufen selbst (vom eigenen Körper), streng genommen Rekursion ist nicht beteiligt. Aber ja, das ist, wo alle Klugheit wohnt.
- Eigentlich war ich verlesen der code, weil ich dachte der Rekursion durch, die versucht haben, das problem zu lösen mit rekursiven Aufrufe für die temporäre Speicherung. Ich habe nun enthalten eine Variante Ihrer Lösung in meiner Antwort, natürlich, das hinzufügen einer Erklärung in meinen eigenen Worten.
- Cool, und danke für die "ack".
InformationsquelleAutor user4815162342
3

Wenn Sie mit den tatsächlichen lists zu implementieren stacks (das ist, wenn Stack erbt von list oder im Grunde ist eine Liste), dann einfach in umgekehrter list im Ort:
```
def reverse_stack(stack):
    stack.reverse()
```
Umbenannt habe ich die Funktion reverse_stack nur um Verwirrung zu vermeiden; Sie könnte es immer noch reverse. Beispiel:
```
>>> stack = [1, 2, 3]
>>> reverse_stack(stack)
>>> stack
[3, 2, 1]
```
Jedoch, es scheint, dass Ihre Stack Klasse Erben nicht von list aber hält die zugrunde liegenden list in einem privaten Attribut, so können Sie nicht direkt verwenden Sie eine der MutableSequence - API auf eine Stack. Daher

Version2, nur is_empty, push und pop Methoden der Stack

und mit nur Stacks, nicht lists oder deques usw. Zuerst ein paar Hilfsfunktionen:
```
def reverse_copy_stack(stack, rev_stack=None):
    '''Return a reversed copy of stack, which is emptied.
    rev_stack receives the reversed copy if it's not None
    '''
    if rev_stack is None:
        rev_stack = Stack()
    while not stack.is_empty():
        rev_stack.push(stack.pop())
    return rev_stack

def copy_stack(stack):
    '''Return a copy of stack, which is emptied.'''
    return reverse_copy_stack( reverse_copy_stack(stack))
```
Nun können wir umsetzen reverse_stack:
```
def reverse_stack(stack):
    '''Reverse stack in-place'''
    new_stack = copy_stack(stack)
    # Empty stack
    while not stack.is_empty():
        stack.pop()
    # put reversed copy of new_stack in stack
    reverse_copy_stack(new_stack, stack)
```
- im Versuch, es rückgängig zu machen, ohne mit dem umkehren von Listen.
- Dann verstehe ich nicht, was Sie können und können nicht tun (wie pro Hausaufgabe, vielleicht). Sie können Methoden der Stack aber wir wissen nicht, was diese sind. Können Sie append oder extend von der zugrunde liegenden Liste Klasse?
- für append, es ist im Grunde 'push', die sich nur selbst._items.append(item).
- Zwei Fragen: (1) Sie kopieren ein stack? mit einer einzigen Methode oder mit dem Konstruktor?, und (2) Können Sie leer ist, wird ein stack mit einer einzigen Methode?
- Ich bin im Grunde beschränkt sich auf die Verwendung von 3-Methoden der Stack-Klasse. 1. is_empty (selbsterklärend) 2. push-3. pop
- OK, das ist es, was ich wissen musste. Dann @Robert Jacobs, die Antwort ist fast richtig (jetzt). Nicht ganz, denn er verwendet die list API zum kopieren der Daten-Struktur, die möglicherweise oder möglicherweise nicht auf deinem Stack Objekte. In der Tat, ist es wahrscheinlich, nicht die Arbeit: von Ihrem früheren Kommentar, es sieht aus wie die zugrunde liegende Liste gespeichert ist, in ein Attribut self._items, so Stack wahrscheinlich ist nicht Erben von list und schneiden eine Stack ist wohl nicht definiert.
InformationsquelleAutor BrianO
1

Fügen Sie eine return-Wert
```
def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    return new_stack
```
und beim aufrufen der Funktion dazu:
```
stack = reverse(stack)
```
Zuweisung Wert auf stack innerhalb der Funktion aber nicht von wo Sie es nannte. Probleme mit Umfang.
- was ist, wenn ich nicht wollen, es zu nennen wie stack=reverse(stack). Ich möchte es nennen wie Sie einfach in umgekehrter Reihenfolge(der stack)
InformationsquelleAutor Xoul
0

Sieht es aus wie Sie geschrieben haben soll while not stack.is_empty():

(Nach dem edit) Ok, jetzt statt stack = new_stack es sagen sollte return new_stack. Die Funktion sollte aufgerufen werden, mit stack = reverse(stack).

(Antwort auf Kommentare), Wenn die Rückgabe ein Wert ist nicht eine option, dann müssen wir wissen, welche Methoden es gibt, um zu ändern, Stack-Objekte. Sagen stack = new_stack oder stack = Stack() wird sich nicht ändern, es außerhalb der Funktion.

Etwas wie dies funktionieren sollte:
```
def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack._items = new_stack._items
```
Aber es ist wahrscheinlich eine schlechte Idee da der Unterstrich vor _items zeigt, dass wer schrieb die Stack-Klasse gar nicht wollen, es zu sein verwendet auf diese Weise.

Plus @user4815162342 wies darauf hin, das vermutlich kehrt der Stapel doppelt, also anstelle der Verwendung einer temporären new_stack = Stack() sollten wir einfach die Verwendung einer temporären Liste. Wirklich @user4815162342 s Antwort ist die beste.
- oh ja. ich habe dass. Ich vergaß zu hinzufügen es. Bearbeitung von op nun.
- Oder vielleicht einfach nur while stack:, wenn die Umsetzung sinnvoll ist.
- Das funktioniert nicht. Egal, ich glaube nicht, dass das das problem ist der code atm.
- Was ist, wenn im engen zu verwenden reverse(stack) anstelle von Aufruf es mit stack = Umgekehrt(stack)
- dann müssen Sie explizit mutieren das argument (in dem Fall der Rückkehr None geeignet ist), aber ohne Kenntnis der Implementierung können wir Ihnen nicht sagen, wie.
- über welche Methoden, was Stack hat 1. is_empty das ist nur ein bool, die true zurückgibt, wenn len(self._items) gleich 0 ist. 2. die üblichen pop-3. und die üblichen push
- ja, da die _items darauf hingewiesen, dass es eine private variable. ich wollte nicht, es zu benutzen.
InformationsquelleAutor Jim K
0

Wenn der Stack-Klasse wird Ihre eigenen oder Sie können Sie zu erweitern, dann ist ein anderer Weg, die Umkehrung der Stapel wäre, um alle die Daten zu erhalten, und verfolgen Sie die Art und Weise, bis Ihr stack (wächst nach oben oder unten) und entweder push/pop auf der Ober-oder der Unterseite des Stapels abhängig von der stack-Richtung. Ihr stack-Methode "reverse" ist dann einfach ein Fall der änderung des flag bestimmt, ob der stack wächst nach oben oder unten.

Habe ich keinen code noch, aber wenn Ihr stack groß ist dann die änderung ein flag kann gut sein, viel einfacher, als die Umkehrung einer großen Liste von Daten.

InformationsquelleAutor Tony Suffolk 66
-1

Kopieren Sie den Stapel zuerst leeren Sie den original-stack, dann Folgen Sie Ihrer Methode.
```
def reverse(stack):
    old_stack = stack[:]
    while not stack.is_empty():
        stack.pop()
    while not old_stack.is_empty():
        stack.push(old_stack.pop())
```
- old_stack = stack nicht eine Kopie erstellen
- Glücklicherweise old_stack = stack[:] tut.
- auf seine Umsetzung
- Yyyeah-es Kopien, Listen, Ordnung, aber vielleicht nicht Stacks. Es entsteht in der Tat, dass es wohl nicht kopieren Sie diese auf alle. Die Klasse wohl nicht Erben aus list ab, lässt aber die zugrunde liegende Liste in einem privaten Attribut. Ich Sprach in meiner Antwort & Kommentare im Vorfeld der Version2 gibt.
InformationsquelleAutor Robert Jacobs

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Version2, nur is_empty, push und pop Methoden der Stack

Version2, nur `is_empty`, `push` und `pop` Methoden der `Stack`