{"id":29742,"date":"2022-05-16T17:20:00","date_gmt":"2022-05-16T15:20:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=29742"},"modified":"2024-11-27T15:11:59","modified_gmt":"2024-11-27T14:11:59","slug":"queue-implementieren-stack","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/queue-implementieren-stack\/","title":{"rendered":"Queue mit einem Stack implementieren"},"content":{"rendered":"\n

In diesem Teil der Tutorialserie zeige ich dir, wie man eine Queue mit einem Stack (genauer gesagt: mit zwei Stacks) implementiert.<\/p>\n\n\n\n

Diese Variante hat keinen praktischen Nutzen, sondern ist in erster Linie eine \u00dcbungsaufgabe. Als solche ist sie das Gegenst\u00fcck zur Implementierung eines Stacks mit einer Queue<\/a>.<\/p>\n\n\n\n

Zur Erinnerung: ein Stack ist eine Datenstruktur<\/a>, bei der die Elemente in der umgekehrten Reihenfolge des Einf\u00fcgens abgerufen werden, also eine Last-in-first-out-Datenstruktur (LIFO).<\/p>\n\n\n\n

Wie k\u00f6nnen wir damit eine Queue, also eine First-in<\/em>-first-out-Datenstruktur (FIFO) implementieren?<\/p>\n\n\n\n

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

Das erste Element, dass wir in die Queue einf\u00fcgen, legen wir auf einen Stack (im Beispiel: \"banana\"). Um es aus der Queue zu entnehmen, holen wir es wieder vom Stack:<\/p>\n\n\n

\n
\"Einf\u00fcgen<\/figure>\n<\/div>\n\n\n

Mit dem zweiten Element funktioniert das so schon nicht mehr, denn der Stack arbeitet ja nach dem LIFO-Prinzip. Wenn z. B. \"banana\" und \"cherry\" auf dem Stack liegen, m\u00fcssten wir \"cherry\" als erstes wieder entnehmen:<\/p>\n\n\n

\n
\"Einf\u00fcgen<\/figure>\n<\/div>\n\n\n

Bei einer Queue wollen wir jedoch das zuerst<\/em> eingef\u00fcgte Element (also \"banana\") auch als erstes<\/em> wieder entnehmen.<\/p>\n\n\n\n

Das ist mit einem Stack allein nicht m\u00f6glich.<\/p>\n\n\n\n

Stattdessen gehen wir beim Einf\u00fcgen eines Elements in die Queue wie folgt vor:<\/p>\n\n\n\n

  1. Wir erzeugen einen tempor\u00e4ren Stack (in der Grafik unten orange dargestellt) und verschieben alle Elemente des urspr\u00fcnglichen Stacks auf den tempor\u00e4ren Stack.<\/li>
  2. Wir legen das neue Element auf den urspr\u00fcnglichen Stack.<\/li>
  3. Wir schieben alle Elemente zur\u00fcck vom tempor\u00e4ren Stack auf den urspr\u00fcnglichen Stack. Der tempor\u00e4re Stack wird dann nicht mehr ben\u00f6tigt.<\/li><\/ol>\n\n\n\n

    Die folgende Grafik zeigt die drei Schritte:<\/p>\n\n\n

    \n
    \"Zweites
    Zweites Element \"cherry\" in die Queue einf\u00fcgen<\/figcaption><\/figure>\n<\/div>\n\n\n

    Danach liegen die Elemente so auf dem Stack, dass wir als erstes das zuerst eingef\u00fcgte Element \"banana\" entnehmen k\u00f6nnen und dann das als zweites eingef\u00fcgte Element \"cherry\".<\/p>\n\n\n\n

    Das funktioniert so nicht nur mit zwei Elementen, sondern mit beliebig vielen. Die folgende Grafik zeigt, wie wir ein drittes Element \"grape\" in die Queue einf\u00fcgen:<\/p>\n\n\n

    \n
    \"Drittes
    Drittes Element \"grape\" in die Queue einf\u00fcgen<\/figcaption><\/figure>\n<\/div>\n\n\n

    Danach k\u00f6nnen wir die Elemente in First-in-First-out-Reihenfolge aus der Queue entnehmen, also erst die zuerst eingef\u00fcgte \"banana\", dann die \"cherry\", und dann die zuletzt eingef\u00fcgte \"grape\".<\/p>\n\n\n\n

    Quellcode f\u00fcr die Queue mit Stacks<\/h2>\n\n\n\n

    Der Quellcode f\u00fcr diesen Algorithmus ben\u00f6tigt nur wenige Zeilen Java-Code.<\/p>\n\n\n\n

    Als Stack verwende ich den im Stack-Tutorial vorgestellten ArrayStack<\/a>. Genauso gut k\u00f6nntest du die JDK-Klasse Stack<\/code> oder eine beliebige Deque<\/code>-Implementierung, z. B. ein ArrayDeque<\/a>, verwenden.<\/p>\n\n\n\n

    Du findest den Code in der Klasse StackQueue<\/a> im GitHub-Repository.<\/p>\n\n\n

    public<\/span> class<\/span> StackQueue<\/span><E<\/span>> implements<\/span> Queue<\/span><E<\/span>> <\/span>{\n\n  private<\/span> final<\/span> Stack<E> stack = new<\/span> ArrayStack<>();\n\n  @Override<\/span>\n  public<\/span> void<\/span> enqueue<\/span>(E element)<\/span> <\/span>{\n    \/\/ 1. Move elements from main stack to a temporary stack<\/span>\n    Stack<E> temporaryStack = new<\/span> ArrayStack<>();\n    while<\/span> (!stack.isEmpty()) {\n      temporaryStack.push(stack.pop());\n    }\n\n    \/\/ 2. Push new element on the main stack<\/span>\n    stack.push(element);\n\n    \/\/ 3. Move elements back from temporary stack to main stack<\/span>\n    while<\/span> (!temporaryStack.isEmpty()) {\n      stack.push(temporaryStack.pop());\n    }\n  }\n\n  @Override<\/span>\n  public<\/span> E dequeue<\/span>()<\/span> <\/span>{\n    return<\/span> stack.pop();\n  }\n\n  @Override<\/span>\n  public<\/span> E peek<\/span>()<\/span> <\/span>{\n    return<\/span> stack.peek();\n  }\n\n  @Override<\/span>\n  public<\/span> boolean<\/span> isEmpty<\/span>()<\/span> <\/span>{\n    return<\/span> stack.isEmpty();\n  }\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
    Beachte, dass hier nicht das java.util.Queue<\/code>-Interface implementiert wird. Dieses erbt von java.util.Collection<\/code>, sodass wir wesentlich mehr Methoden implementieren m\u00fcssten.<\/p>\n\n\n\n
    public<\/span> interface<\/span> Queue<\/span><E<\/span>> <\/span>{\n  void<\/span> enqueue<\/span>(E element)<\/span><\/span>;\n  E dequeue<\/span>()<\/span><\/span>;\n  E peek<\/span>()<\/span><\/span>;\n  boolean<\/span> isEmpty<\/span>()<\/span><\/span>;\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
    Ausblick<\/h2>\n\n\n\n
    Im n\u00e4chsten Teil des Tutorials erf\u00e4hrst du, wie man eine Queue mit einer verketteten Liste implementiert<\/a>.<\/p>\n\n\n\n
    Wenn du noch Fragen hast, stelle sie gerne \u00fcber die Kommentar-Funktion. 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 implementiert man eine Queue mit einem Stack (besser gesagt: mit zwei Stacks)? Tutorial mit Grafiken und Java-Code-Beispielen.<\/p>\n","protected":false},"author":1,"featured_media":29749,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie implementiert man eine Queue mit einem Stack (besser gesagt: mit zwei Stacks)? Tutorial mit Grafiken und Java-Code-Beispielen.","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":4271,"_post_count":0,"footnotes":""},"categories":[127],"tags":[192],"class_list":["post-29742","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-queue"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/building-674828-1770x986-1.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Wie implementiert man eine Queue mit einem Stack (besser gesagt: mit zwei Stacks)? Tutorial mit Grafiken und Java-Code-Beispielen.","public_identification_id":"3849b0ba48a5407b9d4ece0459168956","private_identification_id":"7c9e6f723fb9400f86e2910d95477f4e","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29742","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=29742"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29742\/revisions"}],"predecessor-version":[{"id":31210,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29742\/revisions\/31210"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/29749"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=29742"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=29742"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=29742"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
    Zum Einsatz der Queue kannst du dir das Demo-Programm QueueDemo<\/a> ansehen.<\/p>\n\n\n\n
    Stattdessen habe ich f\u00fcr dieses Tutorial ein eigenes Queue-Interface<\/a> geschrieben, das nur die Methoden enqueue()<\/code>, dequeue()<\/code>, peek()<\/code> und isEmpty()<\/code> definiert:<\/p>\n\n\n