{"id":28080,"date":"2022-03-16T17:22:03","date_gmt":"2022-03-16T16:22:03","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=28080"},"modified":"2024-11-27T15:12:40","modified_gmt":"2024-11-27T14:12:40","slug":"stack-implementieren","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/stack-implementieren\/","title":{"rendered":"Stack in Java implementieren"},"content":{"rendered":"\n<p>Im vorherigen Teil des Tutorials, \"<a href=\"\/de\/algorithmen\/java-stack\/\">Stack-Klasse in Java<\/a>\", hast du erfahren, warum man Javas <code>Stack<\/code>-Klasse nicht verwenden sollte (unn\u00f6tige Operationen wie <code>insertElementAt()<\/code> und <code>setElementAt()<\/code>, fehlendes Interface, over-synchronized). <\/p>\n\n\n\n<p>Die von den JDK-Entwicklern empfohlene Alternative, <a href=\"\/de\/algorithmen\/java-deque\/\">Deque<\/a>, bietet ebenfalls Methoden an, die eigentlich nicht in einen Stack geh\u00f6ren, z. B. <code>addLast()<\/code> und <code>removeLast()<\/code>.<\/p>\n\n\n\n<p>Die unn\u00f6tigen Operationen stehen im Widerspruch zum <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Interface-Segregation-Prinzip\" target=\"_blank\">Interface-Segregation-Prinzip (ISP)<\/a>, demzufolge eine Schnittstelle nur diejenigen Methoden enthalten sollte, die der Nutzer dieser Schnittstelle ben\u00f6tigt.<\/p>\n\n\n\n<p>Daher zeige ich in diesem und den folgenden Teilen dieses Tutorials, wie man in Java einen Stack selbst implementiert \u2013 und zwar auf vier verschiedene Arten:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Als Wrapper um ein <code>ArrayDeque<\/code> (in diesem Artikel)<\/li><li>Mit einem <a href=\"\/de\/algorithmen\/stack-implementieren-array\/\">Array<\/a><\/li><li>Mit einer <a href=\"\/de\/algorithmen\/stack-implementieren-linked-list\/\">verketteten Liste<\/a><\/li><li>Mit einer (bzw. zwei) <a href=\"\/de\/algorithmen\/stack-implementieren-queue\/\">Queues<\/a><\/li><\/ul>\n\n\n\n<p>Los geht's mit einem Interface...<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stack-interface\">Stack-Interface<\/h2>\n\n\n\n<p>Als erstes legen wir ein <code>Stack<\/code>-Interface an. Dieses enth\u00e4lt nur diejenigen Methoden, die ein Stack anbieten sollte, n\u00e4mlich:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>push()<\/code> \u2013 zum Hinzuf\u00fcgen von Elementen auf den Stack<\/li><li><code>pop()<\/code> \u2013 zum Entnehmen von Elementen von der Oberseite des Stacks<\/li><li><code>peek()<\/code> \u2013 zum Betrachten des obersten Stack-Elements, ohne es zu entnehmen <\/li><li><code>isEmpty()<\/code> \u2013 um zu pr\u00fcfen, ob der Stack leer ist (diese Methode ist optional)<\/li><\/ul>\n\n\n\n<p>Der folgende Code zeigt das Interface (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/stack\/Stack.java\" target=\"_blank\">Stack<\/a> im im GitHub-Repo):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">interface<\/span> <span class=\"hljs-title\">Stack<\/span>&lt;<span class=\"hljs-title\">E<\/span>&gt; <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">push<\/span><span class=\"hljs-params\">(E item)<\/span><\/span>;\n  <span class=\"hljs-function\">E <span class=\"hljs-title\">pop<\/span><span class=\"hljs-params\">()<\/span><\/span>;\n  <span class=\"hljs-function\">E <span class=\"hljs-title\">peek<\/span><span class=\"hljs-params\">()<\/span><\/span>;\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isEmpty<\/span><span class=\"hljs-params\">()<\/span><\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Ich habe mich an dieser Stelle entschieden, dass <code>pop()<\/code> und <code>peek()<\/code> bei einem leeren Stack eine <code>NoSuchElementException<\/code> werfen, so wie es die <code>add<\/code>\/<code>remove<\/code>\/<code>get<\/code>-Methoden von <code>Deque<\/code> tun.<\/p>\n\n\n\n<p>Alternativ k\u00f6nnte man auch <code>Optional&lt;E&gt;<\/code> zur\u00fcckliefern. Die Entscheidung h\u00e4ngt davon ab, inwieweit der Aufruf von <code>pop()<\/code> und <code>peek()<\/code> auf einem leeren Stack eine Ausnahme darstellt (dann sollte man Exceptions werfen) oder einen regul\u00e4ren Control Flow (dann sollte man ein <code>Optional<\/code> zur\u00fcckgeben).<\/p>\n\n\n\n<p>Was man nicht tun sollte, ist bei einem leeren Stack <code>null<\/code> zur\u00fcckzugeben.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stack-implementieren-mit-arraydeque\">Stack implementieren mit ArrayDeque<\/h2>\n\n\n\n<p>Unsere erste Implementierung besteht aus einem <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Adapter_(Entwurfsmuster)\" target=\"_blank\">Adapter<\/a> um die (nicht threadsichere) Deque-Implementierung <a href=\"\/de\/algorithmen\/arraydeque-java\/\">ArrayDeque<\/a>. Der Adapter leitet die Stack-Methoden wie folgt weiter:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>Stack.push()<\/code> \u2192 <code>ArrayDeque.addFirst()<\/code><\/li><li><code>Stack.pop()<\/code> \u2192 <code>ArrayDeque.removeFirst()<\/code><\/li><li><code>Stack.peek()<\/code> \u2192 <code>ArrayDeque.getFirst()<\/code><\/li><li><code>Stack.isEmpty()<\/code> \u2192 <code>ArrayDeque.isEmpty()<\/code><\/li><\/ul>\n\n\n\n<p>Hier zun\u00e4chst ein Klassendiagramm, das das Adapter-Pattern darstellt:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"308\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-800x308.png\" alt=\"ArrayDequeStack als Adapter um ein ArrayDeque\" class=\"wp-image-28228\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-800x308.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-224x86.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-336x129.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-504x194.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-672x259.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-400x154.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-600x231.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-944x363.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram-1200x462.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/ArrayDequeStack-adapter-class-diagram.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption>ArrayDequeStack als Adapter um ein ArrayDeque<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Und hier die Implementierung des Adapters (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/stack\/ArrayDequeStack.java\" target=\"_blank\">ArrayDequeStack<\/a> im GitHub-Repo):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">ArrayDequeStack<\/span>&lt;<span class=\"hljs-title\">E<\/span>&gt; <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">Stack<\/span>&lt;<span class=\"hljs-title\">E<\/span>&gt; <\/span>{\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> Deque&lt;E&gt; deque = <span class=\"hljs-keyword\">new<\/span> ArrayDeque&lt;&gt;();\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">push<\/span><span class=\"hljs-params\">(E item)<\/span> <\/span>{\n    deque.addFirst(item);\n  }\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> E <span class=\"hljs-title\">pop<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> deque.removeFirst();\n  }\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> E <span class=\"hljs-title\">peek<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> deque.getFirst();\n  }\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isEmpty<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> deque.isEmpty();\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Das folgende Beispielprogramm (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/demos\/stack\/StackDemo.java\" target=\"_blank\">StackDemo<\/a> in GitHub) zeigt eine beispielhafte Benutzung der <code>ArrayDequeStack<\/code>-Klasse.<\/p>\n\n\n\n<p>Der Test-Code ist so konzipiert, dass wir ohne gro\u00dfen Aufwand zus\u00e4tzliche <code>Stack<\/code>-Implementierungen testen k\u00f6nnen (indem wir <code>runDemo()<\/code> f\u00fcr Instanzen anderer <code>Stack<\/code>-Klassen aufrufen).<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">StackDemo<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n    runDemo(<span class=\"hljs-keyword\">new<\/span> ArrayDequeStack&lt;&gt;());\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">runDemo<\/span><span class=\"hljs-params\">(Stack&lt;Integer&gt; stack)<\/span> <\/span>{\n    System.out.println(<span class=\"hljs-string\">\"-------- \"<\/span> + stack.getClass().getSimpleName() + <span class=\"hljs-string\">\" --------\"<\/span>);\n\n    stack.push(<span class=\"hljs-number\">1<\/span>);\n    stack.push(<span class=\"hljs-number\">2<\/span>);\n    stack.push(<span class=\"hljs-number\">3<\/span>);\n\n    System.out.println(<span class=\"hljs-string\">\"stack.peek() = \"<\/span> + stack.peek());\n\n    System.out.println(<span class=\"hljs-string\">\"stack.pop() = \"<\/span> + stack.pop());\n    System.out.println(<span class=\"hljs-string\">\"stack.pop() = \"<\/span> + stack.pop());\n    System.out.println(<span class=\"hljs-string\">\"stack.pop() = \"<\/span> + stack.pop());\n\n    <span class=\"hljs-keyword\">try<\/span> {\n      System.out.println(<span class=\"hljs-string\">\"stack.pop() = \"<\/span> + stack.pop());\n    } <span class=\"hljs-keyword\">catch<\/span> (Exception ex) {\n      ex.printStackTrace(System.out);\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>Wir haben mit wenigen Zeilen Code eine eigene (nicht threadsichere) Stack-Klasse implementiert.<\/p>\n\n\n\n<p>Um einen threadsicheren Stack zu implementieren k\u00f6nnen wir analog einen Adapter um ein threadsicheres Deque \u2013 wie <a href=\"\/de\/algorithmen\/concurrentlinkeddeque-java\/\">ConcurrentLinkedDeque<\/a> (nicht blockierend) oder <a href=\"\/de\/algorithmen\/linkedblockingdeque-java\/\">LinkedBlockingDeque<\/a> (blockierend) \u2013 legen.<\/p>\n\n\n\n<p>Im n\u00e4chsten Teil des Tutorials zeige ich dir, wie du einen <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/stack-implementieren-array\/\">Stack mit einem Array<\/a> implementierst.<\/p>\n\n\n\n<p>Wenn du noch Fragen hast, stelle sie gerne \u00fcber die Kommentar-Funktion. M\u00f6chtest du \u00fcber neue Tutorials und Artikel informiert werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders.eu-Newsletter anzumelden.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Tutorial erf\u00e4hrst du, wie man in Java einen Stack implementiert - mit einem ArrayDeque, einem Array, einer LinkedList und einer Queue.<\/p>\n","protected":false},"author":1,"featured_media":28555,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"In diesem Tutorial erf\u00e4hrst du, wie man in Java einen Stack implementiert - mit einem ArrayDeque, einem Array, einer LinkedList und einer Queue.","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":4626,"_post_count":0,"footnotes":""},"categories":[127],"tags":[191],"class_list":["post-28080","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-937659.jpg",1770,996,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.jpg",300,169,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.jpg",768,432,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.jpg",1024,576,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-224x126.jpg",224,126,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-336x189.jpg",336,189,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-504x284.jpg",504,284,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-672x378.jpg",672,378,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-400x225.jpg",400,225,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-600x338.jpg",600,338,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-800x450.jpg",800,450,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-944x531.jpg",944,531,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-1200x675.jpg",1200,675,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.jpg",1536,864,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stones-937659.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":"In diesem Tutorial erf\u00e4hrst du, wie man in Java einen Stack implementiert - mit einem ArrayDeque, einem Array, einer LinkedList und einer Queue.","public_identification_id":"5ce93551513e4c7c82713af167c3dd09","private_identification_id":"a9f70978f5e94955abf3465c873adcb4","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28080","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=28080"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28080\/revisions"}],"predecessor-version":[{"id":31212,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28080\/revisions\/31212"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/28555"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=28080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=28080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=28080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}