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

Im vorherigen Teil dieser Tutorial-Serie ging es darum, wie man einen Stack mit einer verketteten Liste<\/a> implementiert. In diesem Teil zeige ich dir, wie du einen Stack mit einer Queue (besser gesagt: mit zwei Queues) implementieren kannst. <\/p>\n\n\n\n

Diese Variante hat kaum praktischen Nutzen und wird in erster Linie als \u00dcbungsaufgabe verwendet (als Gegenst\u00fcck gibt es \u00fcbrigens auch eine \u00dcbung zur Implementierung einer Queue mit Stacks<\/a>). Von daher: Versuch doch einmal selbst auf die L\u00f6sung zu kommen!<\/p>\n\n\n\n

Zur Erinnerung: Eine Queue ist eine Datenstruktur<\/a>, bei der du Elemente auf einer Seite einf\u00fcgst und auf der anderen Seite wieder entnimmst \u2013 also eine First-in-First-out-Datenstruktur (FIFO).<\/p>\n\n\n\n

Wie k\u00f6nnen wir damit einen Stack, also eine Last-in<\/em>-First-out-Datenstruktur (LIFO) implementieren?<\/p>\n\n\n\n

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

Das erste Element, das wir auf den Stack schieben (im Beispiel: \"apple\"), f\u00fcgen wir in eine Queue ein. Um es vom Stack zu entnehmen, holen wir es wieder aus der Queue:<\/p>\n\n\n

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

Das zweite Element k\u00f6nnen wir nicht einfach auch in diese Queue schreiben. Denn die funktioniert ja nach dem FIFO-Prinzip. Wenn wir \"apple\" und dann \"orange\" in die Queue schieben, m\u00fcssen wir auch \"apple\" zuerst wieder entnehmen:<\/p>\n\n\n

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

Bei einem Stack m\u00fcssen wir jedoch das zuletzt<\/em> auf den Stack geschobene Elemente \"orange\" zuerst<\/em> wieder entnehmen \u2013 und nicht den zuerst eingef\u00fcgten \"apple\".<\/p>\n\n\n\n

Das ist mit einer einzigen Queue nicht m\u00f6glich.<\/p>\n\n\n\n

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

  1. Wir erzeugen eine neue Queue (in der Grafik unten orange dargestellt) und schieben auf diese das einzuf\u00fcgende Element.<\/li>
  2. Wir verschieben das Element aus der ersten Queue in die neu erstellte Queue.<\/li>
  3. Wir ersetzen die bestehende Queue durch die neue Queue.<\/li><\/ol>\n\n\n\n

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

    \n
    \"Stack
    Zweites Element auf den Stack schieben<\/figcaption><\/figure>\n<\/div>\n\n\n

    Danach liegen die Elemente so in der Queue, dass wir als erstes das zuletzt eingef\u00fcgte Element \"orange\" entnehmen k\u00f6nnen und danach das zuerst eingef\u00fcgte Element \"apple\".<\/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 \"pear\" auf den Stack schieben. Der zweite Schritt aus der vorherigen Grafik ist hier in die Schritte 2a und 2b aufgeteilt: Zuerst wird \"orange\" aus der alten Queue in die neue verschoben, danach \"apple\".<\/p>\n\n\n

    \n
    \"Stack
    Drittes Element auf den Stack schieben<\/figcaption><\/figure>\n<\/div>\n\n\n

    Danach k\u00f6nnen wir die Elemente in Last-in-First-out-Reihenfolge aus dem Stack entnehmen, also erst die zuletzt eingef\u00fcgte \"pear\", dann die \"orange\", dann den zuerst eingef\u00fcgten \"apple\".<\/p>\n\n\n\n

    Quellcode f\u00fcr den Stack mit Queues<\/h2>\n\n\n\n

    Im folgenden siehst du, dass der Quellcode f\u00fcr die L\u00f6sung ziemlich einfach ist.<\/p>\n\n\n\n

    Als Queue verwende ich die einfachste Queue-Implementierung, ArrayDeque<\/a>. Dass es sich auch um ein Deque handelt, st\u00f6rt uns nicht, denn wir weisen es ja einer Variablen zu, deren Typ das Queue<\/code>-Interface ist.<\/p>\n\n\n\n

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

    public<\/span> class<\/span> QueueStack<\/span><E<\/span>> implements<\/span> Stack<\/span><E<\/span>> <\/span>{\n\n  private<\/span> Queue<E> queue = new<\/span> ArrayDeque<>();\n\n  @Override<\/span>\n  public<\/span> void<\/span> push<\/span>(E element)<\/span> <\/span>{\n    Queue<E> newQueue = new<\/span> ArrayDeque<>();\n    newQueue.add(element);\n\n    while<\/span> (!queue.isEmpty()) {\n      newQueue.add(queue.remove());\n    }\n\n    queue = newQueue;\n  }\n\n  @Override<\/span>\n  public<\/span> E pop<\/span>()<\/span> <\/span>{\n    return<\/span> queue.remove();\n  }\n\n  @Override<\/span>\n  public<\/span> E peek<\/span>()<\/span> <\/span>{\n    return<\/span> queue.element();\n  }\n\n  @Override<\/span>\n  public<\/span> boolean<\/span> isEmpty<\/span>()<\/span> <\/span>{\n    return<\/span> queue.isEmpty();\n  }\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 und letzten Teil des Tutorials behandeln wir eine weitere \u00dcbungsaufgabe: Wie kann man einen Stack per Rekursion umkehren?<\/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 einen Stack mit einer Queue (besser gesagt: mit zwei Queues)? Tutorial mit Grafiken und Java-Code-Beispielen.<\/p>\n","protected":false},"author":1,"featured_media":28554,"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 einen Stack mit einer Queue (besser gesagt: mit zwei Queues)? Tutorial mit Grafiken und Java-Code-Beispielen.","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":3930,"_post_count":0,"footnotes":""},"categories":[127],"tags":[191],"class_list":["post-28089","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\/paper-1328856.jpg",1770,996,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.jpg",300,169,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.jpg",768,432,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.jpg",1024,576,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-224x126.jpg",224,126,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-336x189.jpg",336,189,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-504x284.jpg",504,284,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-672x378.jpg",672,378,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-400x225.jpg",400,225,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-600x338.jpg",600,338,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-800x450.jpg",800,450,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-944x531.jpg",944,531,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-1200x675.jpg",1200,675,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.jpg",1536,864,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/paper-1328856.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 implementiert man einen Stack mit einer Queue (besser gesagt: mit zwei Queues)? Tutorial mit Grafiken und Java-Code-Beispielen.","public_identification_id":"5b221f6b953649e28c7631f9a1210046","private_identification_id":"da5fdff1d3d6465382e6180d797060ef","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28089","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=28089"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28089\/revisions"}],"predecessor-version":[{"id":31208,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28089\/revisions\/31208"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/28554"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=28089"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=28089"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=28089"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
    Das Demo-Programm StackDemo<\/a> zeigt dir, wie du den QueueStack<\/code> einsetzen kannst.<\/p>\n\n\n\n