{"id":28091,"date":"2022-03-16T17:26:49","date_gmt":"2022-03-16T16:26:49","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=28091"},"modified":"2024-11-27T15:13:43","modified_gmt":"2024-11-27T14:13:43","slug":"stack-umkehren-rekursion","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/stack-umkehren-rekursion\/","title":{"rendered":"Umkehrung eines Stacks mit Rekursion"},"content":{"rendered":"\n

In diesem letzten Teil des Stack-Tutorials zeige ich dir, wie man die Reihenfolge der Elemente eines Stacks ausschlie\u00dflich per Rekursion (also ohne Iteration) umkehren kann. <\/p>\n\n\n\n

Genau wie die Implementierung eines Stacks mit Queues<\/a> hat auch der in diesem Artikel gezeigte Algorithmus in erster Linie Schulungs-Character. Von daher: Versuch gerne zuerst einmal selbst auf die L\u00f6sung zu kommen.<\/p>\n\n\n\n

Die L\u00f6sung \u2013 Schritt f\u00fcr Schritt<\/h2>\n\n\n\n

Wir l\u00f6sen die Aufgabe mit zwei Methoden, die ich in den folgenden zwei Abschnitten erkl\u00e4ren werde.<\/p>\n\n\n\n

1. Die reverse()-Methode<\/h3>\n\n\n\n

Wir implementieren zun\u00e4chst eine reverse()<\/code>-Methode, die wie folgt vorgeht:<\/p>\n\n\n\n

Schritt 1:<\/p>\n\n\n\n

Solange Elemente auf dem Eingabe-Stack sind, nehmen wir sie vom Stack und rufen die reverse()<\/code>-Methode rekursiv auf. Dadurch werden alle Elemente vom obersten bis zum untersten Element in den Call Stack verschoben:<\/p>\n\n\n\n

\"Umkehren<\/figure><\/div>\n\n\n\n

Schritt 2:<\/p>\n\n\n\n

Beim Ausstieg aus der Rekursion schieben wir die Elemente vom Call Stack zur\u00fcck auf den Ziel-Stack \u2013 aber in umgekehrter Reihenfolge!<\/p>\n\n\n\n

Dazu erstellen wir eine Methode insertAtBottom()<\/code>, welche ein Element am Boden eines Stacks einf\u00fcgt. (Wie diese Methode funktioniert, siehst du im n\u00e4chsten Abschnitt.)<\/p>\n\n\n\n

\"Umkehren<\/figure><\/div>\n\n\n\n

Fertig! Der Ziel-Stack enth\u00e4lt die Elemente des Eingabe-Stacks in umgekehrter Reihenfolge.<\/p>\n\n\n\n

2. Die insertAtBottom()-Methode<\/h3>\n\n\n\n

Doch wie f\u00fcgen wir Elemente am Boden des Stacks ein?<\/p>\n\n\n\n

Dazu implementieren wir eine zweite Methode \u2013 insertAtBottom()<\/code>. Auch f\u00fcr diese setzen wir ausschlie\u00dflich auf Rekursion.<\/p>\n\n\n\n

Die folgenden Grafiken zeigen den letzten insertAtBottom()<\/code>-Aufruf des vorherigen Diagramms. Also den Aufruf, bei dem das Element \"peach\" am Boden des Ziel-Stacks eingef\u00fcgt wird. Dieser enth\u00e4lt zu dem Zeitpunkt bereits die Elemente \"apple\", \"orange\" und \"pear\".<\/p>\n\n\n\n

Der Einf\u00fcge-Vorgang besteht aus drei Schritten:<\/p>\n\n\n\n

Schritt 1:<\/p>\n\n\n\n

Solange Elemente auf dem Ziel-Stack sind, entnehmen wir diese und rufen insertAtBottom()<\/code> rekursiv auf. Dadurch werden die Elemente des Ziel-Stacks auf den Call Stack verschoben:<\/p>\n\n\n\n

\"insertAtBottom()<\/figure><\/div>\n\n\n\n

Schritt 2:<\/p>\n\n\n\n

Sobald der Ziel-Stack leer ist, wird das Element, das am Boden des Stacks eingef\u00fcgt werden soll, auf den Ziel-Stack gelegt:<\/p>\n\n\n\n

\"insertAtBottom()<\/figure><\/div>\n\n\n\n

Schritt 3:<\/p>\n\n\n\n

Beim Ausstieg aus der Rekursion schieben wir die Elemente vom Call Stack zur\u00fcck in den Ziel-Stack:<\/p>\n\n\n\n

\"insertAtBottom()<\/figure><\/div>\n\n\n\n

Damit hat die insertAtBottom()<\/code>-Methode ihre Aufgabe erledigt: Das Element \"peach\" wurde am Boden des Ziel-Stacks eingef\u00fcgt.<\/p>\n\n\n\n

Quellcode f\u00fcr die Umkehrung eines Stacks per Rekursion<\/h2>\n\n\n\n

Der Java-Quellcode f\u00fcr die Umkehrung des Stacks besteht aus nur wenigen Zeilen f\u00fcr die zwei Methoden. Du findest den Code in der Klasse Stacks<\/a> im GitHub-Repo:<\/p>\n\n\n

public<\/span> class<\/span> Stacks<\/span> <\/span>{\n\n  public<\/span> static<\/span> <E> void<\/span> reverse<\/span>(Stack<E> stack)<\/span> <\/span>{\n    if<\/span> (stack.isEmpty()) {\n      return<\/span>;\n    }\n    E element = stack.pop();\n    reverse(stack);\n    insertAtBottom(stack, element);\n  }\n\n  private<\/span> static<\/span> <E> void<\/span> insertAtBottom<\/span>(Stack<E> stack, E element)<\/span> <\/span>{\n    if<\/span> (stack.isEmpty()) {\n      stack.push(element);\n    } else<\/span> {\n      E top = stack.pop();\n      insertAtBottom(stack, element);\n      stack.push(top);\n    }\n  }\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Den Klassennamen Stacks<\/code> habe ich \u00fcbrigens analog zu Java-Utility-Klassen wie Collections<\/code> und Arrays<\/code> gew\u00e4hlt.<\/p>\n\n\n\n
Umsetzung mit Default-Methode im Interface<\/h3>\n\n\n\n
Moderner ist es die Methoden direkt im Stack<\/code>-Interface zu implementieren:<\/p>\n\n\n
public<\/span> interface<\/span> Stack<\/span><E<\/span>> <\/span>{\n\n  \/\/ ...<\/span>\n\n  default<\/span> void<\/span> reverse<\/span>()<\/span> <\/span>{\n    if<\/span> (isEmpty()) {\n      return<\/span>;\n    }\n    E element = pop();\n    reverse();\n    insertAtBottom(element);\n  }\n\n  private<\/span> void<\/span> insertAtBottom<\/span>(E element)<\/span> <\/span>{\n    if<\/span> (isEmpty()) {\n      push(element);\n    } else<\/span> {\n      E top = pop();\n      insertAtBottom(element);\n      push(top);\n    }\n  }\n}\n\n<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Diese Variante findest du nicht im GitHub-Repository, da ich bei der Vorstellung des Stack<\/code>-Interfaces zu Beginn des Tutorials nicht mit der reverse()<\/code>-Methode verwirren wollte.<\/p>\n\n\n\n
Fazit<\/h2>\n\n\n\n
Damit endet die Tutorial-Serie zum Thema Stack. Wenn du alle Teile gelesen hast, hast du gelernt, wie ein Stack funktioniert, welche Stack-Implementierungen es im JDK gibt, wie man Stacks auf verschiedene Arten selbst implementiert und \u2013 in diesem Artikel \u2013 wie man einen Stack per Rekursion umkehren kann.<\/p>\n\n\n\n
Wenn dir die Serie gefallen hat, hinterlasse mir gerne einen Kommantar oder teile die Artikel \u00fcber die Share-Buttons am Ende. Wenn du noch Fragen hast, kannst du sie gerne \u00fcber die Kommentar-Funktion stellen.<\/p>\n\n\n\n
M\u00f6chtest du \u00fcber neue Tutorials und Artikel informiert werden? Dann klicke hier<\/a>, um dich f\u00fcr den HappyCoders.eu-Newsletter anzumelden.<\/p>\n","protected":false},"excerpt":{"rendered":"
Wie kann man die Reihenfolge der Elemente eines Stacks per Rekursion umkehren (also ohne Iteration)? Tutorial mit Grafiken und Java-Code-Beispielen.<\/p>\n","protected":false},"author":1,"featured_media":28556,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie kann man die Reihenfolge der Elemente eines Stacks per Rekursion umkehren (ohne Iteration)? Tutorial mit Grafiken und Java-Code-Beispielen.","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":4379,"_post_count":0,"footnotes":""},"categories":[127],"tags":[191],"class_list":["post-28091","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-stack"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",1770,996,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",300,169,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",768,432,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",1024,576,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-224x126.jpg",224,126,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-336x189.jpg",336,189,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-504x284.jpg",504,284,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-672x378.jpg",672,378,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-400x225.jpg",400,225,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-600x338.jpg",600,338,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-800x450.jpg",800,450,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-944x531.jpg",944,531,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-1200x675.jpg",1200,675,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",1536,864,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-1694879.jpg",1770,996,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Wie kann man die Reihenfolge der Elemente eines Stacks per Rekursion umkehren (also ohne Iteration)? Tutorial mit Grafiken und Java-Code-Beispielen.","public_identification_id":"58a1f2e9044245138f585fe469cb7739","private_identification_id":"db718b67451842f6a361797cee109a43","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28091","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=28091"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28091\/revisions"}],"predecessor-version":[{"id":28696,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28091\/revisions\/28696"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/28556"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=28091"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=28091"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=28091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}