{"id":30218,"date":"2022-06-07T22:00:49","date_gmt":"2022-06-07T20:00:49","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=30218"},"modified":"2024-11-27T15:06:20","modified_gmt":"2024-11-27T14:06:20","slug":"deque-datenstruktur","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/deque-datenstruktur\/","title":{"rendered":"Deque Datenstruktur"},"content":{"rendered":"\n<p>In diesem Tutorial lernst du alles \u00fcber die Datenstruktur \"Deque\" (ausgesprochen \"Deck\"):<\/p>\n\n\n\n<ul class=\"hc-checked-list wp-block-list\"><li>Was ist ein Deque? <\/li><li>Welche Operationen bietet ein Deque an?<\/li><li>Was sind die Anwendungsgebiete f\u00fcr Deques?<\/li><li>Welche Deque-Interfaces und -Klassen liefert das JDK?<\/li><li>Welches Deque-Implementierung sollte man f\u00fcr welche Einsatzzwecke verwenden?<\/li><li>Wie implementiert man ein Deque selbst in Java?<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"was-ist-ein-deque\">Was ist ein Deque?<\/h2>\n\n\n\n<p>Ein Deque ist eine Liste von Elementen, bei der die Elemente sowohl auf der einen als auch auf der anderen Seite eingef\u00fcgt und entnommen werden k\u00f6nnen. Deque steht f\u00fcr \"<strong>D<\/strong>ouble-<strong>e<\/strong>nded <strong>Q<\/strong>ueue\", also f\u00fcr eine Queue mit zwei Enden:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"160\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-800x160.png\" alt=\"Deque-Datenstruktur\" class=\"wp-image-30342\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-800x160.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-224x45.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-336x67.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-504x101.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-672x134.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-400x80.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-600x120.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-944x189.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3-1200x240.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption>Deque-Datenstruktur<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Ein Deque kann sowohl als <a href=\"\/de\/algorithmen\/queue-datenstruktur\/\">Queue<\/a> als auch als <a href=\"\/de\/algorithmen\/stack-datenstruktur\/\">Stack<\/a> eingesetzt werden:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Als Queue (FIFO, first-in-first-out), indem Elemente auf einer Seite eingef\u00fcgt und auf der anderen Seite wieder entnommen werden.<\/li><li>Als Stack (LIFO, last-in-first-out), indem Elemente an derselben Seite eingef\u00fcgt und wieder entnommen werden.<\/li><\/ul>\n\n\n\n<p>Wir m\u00fcssen uns beim Deque aber nicht auf FIFO- oder LIFO-Funktionalit\u00e4t beschr\u00e4nken. Wir k\u00f6nnen die Elemente jederzeit an einer beliebigen Seiten einf\u00fcgen und wieder entnehmen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"deque-operationen\">Deque-Operationen<\/h2>\n\n\n\n<p>Die Operationen des Deques lauten analog zur Queue auf beiden Seiten \"Enqueue\" und \"Dequeue\":<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\"Enqueue at front\": Anh\u00e4ngen von Elementen an den Kopf des Deques<\/li><li>\"Enqueue at back\": Anh\u00e4ngen von Elementen an das Ende des Deques<\/li><li>\"Dequeue at front\": Entnehmen von Elementen vom Kopf des Deques<\/li><li>\"Dequeue at back\": Entnehmen von Elementen vom Ende des Deques<\/li><\/ul>\n\n\n\n<p>(So wie bei der Queue werden auch beim Deque die entsprechenden Methoden der Java-Implementierungen anders bezeichnet; dazu mehr im n\u00e4chsten Teil des Tutorials, \"<a href=\"\/de\/algorithmen\/java-deque\/\">Java Deque-Interface<\/a>\".)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"anwendungsgebiete-fuer-deqeues\">Anwendungsgebiete f\u00fcr Deqeues<\/h2>\n\n\n\n<p>Das klassische Anwendungsgebiet f\u00fcr Deques ist eine Undo-Liste. Jeder ausgef\u00fchrte Bearbeitungsschritt wird auf das Deque gelegt. Beim Aufruf der \"Undo\"-Funktion wird die zuletzt auf das Deque gelegte Bearbeitung entnommen und wieder r\u00fcckg\u00e4ngig gemacht.<\/p>\n\n\n\n<p>Bis hierhin ist das ein klassisches LIFO-Prinzip, k\u00f6nnte also auch mit einem Stack realisiert werden.<\/p>\n\n\n\n<p>Aus Speichergr\u00fcnden sollten wir die Undo-Historie allerdings limitieren, z. B. auf 100 Eintr\u00e4ge. Bei Verwendung eines Stacks w\u00fcrden die \u00e4ltesten Elemente am Boden des Stacks liegen und k\u00f6nnten dort nicht entfernt werden. Bei einem Deque stellt das jedoch kein Problem dar, da Elemente an beiden Seiten entnommen werden k\u00f6nnen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-der-deque-operationen\">Zeitkomplexit\u00e4t der Deque-Operationen<\/h2>\n\n\n\n<p><em>Eine Einf\u00fchrung in das Thema Zeitkomplexit\u00e4t findest du im Artikel \"<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a>\".<\/em><\/p>\n\n\n\n<p>Deques werden in der Regel mit Arrays oder verketteten Listen implementiert. In beiden F\u00e4llen ist der Aufwand f\u00fcr das Einf\u00fcgen und Entnehmen von Elementen auf beiden Seiten unabh\u00e4ngig von der L\u00e4nge des Deques, also konstant.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t dieser Operationen betr\u00e4gt somit: <em>O(1)<\/em> <\/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 lernst du alles \u00fcber den abstrakten Datentyp \"Deque\", welche Deques es in Java gibt und wie man selber Deques implementiert.<\/p>\n","protected":false},"author":1,"featured_media":30221,"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 lernst du alles \u00fcber den abstrakten Datentyp \"Deque\", welche Deques es in Java gibt und wie man selber Deques implementiert.","_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":3078,"_post_count":0,"footnotes":""},"categories":[127],"tags":[195],"class_list":["post-30218","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-deque"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/donut-5331966-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":"In diesem Tutorial lernst du alles \u00fcber den abstrakten Datentyp \"Deque\", welche Deques es in Java gibt und wie man selber Deques implementiert.","public_identification_id":"246e8f601259424e82fa3daadbf98644","private_identification_id":"21cfa2922c184dd7aaabbb31797c18ae","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30218","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=30218"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30218\/revisions"}],"predecessor-version":[{"id":31182,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30218\/revisions\/31182"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30221"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=30218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=30218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=30218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}