CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Double-ended queue - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"72ee2a04-acd0-41d6-916e-a1c4490f2de5","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Double-ended_queue","wgTitle":"Double-ended queue","wgCurRevisionId":1233074336,"wgRevisionId":1233074336,"wgArticleId":8904,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Wikipedia introduction cleanup from April 2022","All pages needing cleanup","Articles covered by WikiProject Wikify from April 2022","All articles covered by WikiProject Wikify","Wikipedia articles that are too technical from April 2022","All articles that are too technical","Webarchive template wayback links","Abstract data types"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en", "wgPageContentModel":"wikitext","wgRelevantPageName":"Double-ended_queue","wgRelevantArticleId":8904,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1192005","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness", "fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js", "ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Double-ended queue - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Double-ended_queue"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Double-ended_queue&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Double-ended_queue"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Double-ended_queue rootpage-Double-ended_queue skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Double-ended+queue" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Double-ended+queue" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Double-ended+queue" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Double-ended+queue" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Naming_conventions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Naming_conventions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Naming conventions</span> </div> </a> <ul id="toc-Naming_conventions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Distinctions_and_sub-types" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Distinctions_and_sub-types"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Distinctions and sub-types</span> </div> </a> <ul id="toc-Distinctions_and_sub-types-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Operations</span> </div> </a> <ul id="toc-Operations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Implementations</span> </div> </a> <button aria-controls="toc-Implementations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Implementations subsection</span> </button> <ul id="toc-Implementations-sublist" class="vector-toc-list"> <li id="toc-Purely_functional_implementation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Purely_functional_implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Purely functional implementation</span> </div> </a> <ul id="toc-Purely_functional_implementation-sublist" class="vector-toc-list"> <li id="toc-Real-time_deques_via_lazy_rebuilding_and_scheduling" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Real-time_deques_via_lazy_rebuilding_and_scheduling"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span>Real-time deques via lazy rebuilding and scheduling</span> </div> </a> <ul id="toc-Real-time_deques_via_lazy_rebuilding_and_scheduling-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation_without_laziness" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Implementation_without_laziness"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.2</span> <span>Implementation without laziness</span> </div> </a> <ul id="toc-Implementation_without_laziness-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Language_support" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Language_support"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Language support</span> </div> </a> <ul id="toc-Language_support-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Complexity</span> </div> </a> <ul id="toc-Complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Double-ended queue</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 18 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-18" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">18 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Deque" title="Deque – German" lang="de" hreflang="de" data-title="Deque" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Cola_doblemente_terminada" title="Cola doblemente terminada – Spanish" lang="es" hreflang="es" data-title="Cola doblemente terminada" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%B5%D9%81_%D8%AF%D9%88%D8%B7%D8%B1%D9%81%D9%87" title="صف دوطرفه – Persian" lang="fa" hreflang="fa" data-title="صف دوطرفه" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/File_d%27attente_%C3%A0_double_extr%C3%A9mit%C3%A9" title="File d'attente à double extrémité – French" lang="fr" hreflang="fr" data-title="File d'attente à double extrémité" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EB%8D%B1_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)" title="덱 (자료 구조) – Korean" lang="ko" hreflang="ko" data-title="덱 (자료 구조)" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Deque" title="Deque – Italian" lang="it" hreflang="it" data-title="Deque" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%93%D7%95-%D7%AA%D7%95%D7%A8" title="דו-תור – Hebrew" lang="he" hreflang="he" data-title="דו-תור" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kk mw-list-item"><a href="https://kk.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA" title="Дек – Kazakh" lang="kk" hreflang="kk" data-title="Дек" data-language-autonym="Қазақша" data-language-local-name="Kazakh" class="interlanguage-link-target"><span>Қазақша</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%B8%A1%E7%AB%AF%E3%82%AD%E3%83%A5%E3%83%BC" title="両端キュー – Japanese" lang="ja" hreflang="ja" data-title="両端キュー" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Deque_(estruturas_de_dados)" title="Deque (estruturas de dados) – Portuguese" lang="pt" hreflang="pt" data-title="Deque (estruturas de dados)" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D1%83%D1%85%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D0%BD%D1%8F%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C" title="Двухсторонняя очередь – Russian" lang="ru" hreflang="ru" data-title="Двухсторонняя очередь" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Red_sa_dva_kraja" title="Red sa dva kraja – Serbian" lang="sr" hreflang="sr" data-title="Red sa dva kraja" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Pakka_(tietorakenne)" title="Pakka (tietorakenne) – Finnish" lang="fi" hreflang="fi" data-title="Pakka (tietorakenne)" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Dalawang_dulong_queue" title="Dalawang dulong queue – Tagalog" lang="tl" hreflang="tl" data-title="Dalawang dulong queue" data-language-autonym="Tagalog" data-language-local-name="Tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%81%E0%B8%96%E0%B8%A7%E0%B8%84%E0%B8%AD%E0%B8%A2%E0%B8%AA%E0%B8%AD%E0%B8%87%E0%B8%AB%E0%B8%99%E0%B9%89%E0%B8%B2" title="แถวคอยสองหน้า – Thai" lang="th" hreflang="th" data-title="แถวคอยสองหน้า" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B1%D1%96%D1%87%D0%BD%D0%B0_%D1%87%D0%B5%D1%80%D0%B3%D0%B0" title="Двобічна черга – Ukrainian" lang="uk" hreflang="uk" data-title="Двобічна черга" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E9%9B%99%E7%AB%AF%E4%BD%87%E5%88%97" title="雙端佇列 – Cantonese" lang="yue" hreflang="yue" data-title="雙端佇列" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97" title="双端队列 – Chinese" lang="zh" hreflang="zh" data-title="双端队列" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1192005#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Double-ended_queue" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Double-ended_queue" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Double-ended_queue"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Double-ended_queue&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Double-ended_queue&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Double-ended_queue"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Double-ended_queue&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Double-ended_queue&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Double-ended_queue" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Double-ended_queue" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Double-ended_queue&oldid=1233074336" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Double-ended_queue&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Double-ended_queue&id=1233074336&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDouble-ended_queue"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDouble-ended_queue"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Double-ended_queue&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Double-ended_queue&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1192005" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Abstract data type</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">"Deque" redirects here. Not to be confused with dequeueing, a <a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">queue</a> operation.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Lead_too_short plainlinks metadata ambox ambox-content ambox-lead_too_short" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/40px-Wiki_letter_w.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/60px-Wiki_letter_w.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/80px-Wiki_letter_w.svg.png 2x" data-file-width="44" data-file-height="44" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article's <a href="/wiki/Wikipedia:Manual_of_Style/Lead_section#Length" title="Wikipedia:Manual of Style/Lead section">lead section</a> <b>may be too short to adequately <a href="/wiki/Wikipedia:Summary_style" title="Wikipedia:Summary style">summarize</a> the key points</b>.<span class="hide-when-compact"> Please consider expanding the lead to <a href="/wiki/Wikipedia:Manual_of_Style/Lead_section#Provide_an_accessible_overview" title="Wikipedia:Manual of Style/Lead section">provide an accessible overview</a> of all important aspects of the article.</span> <span class="date-container"><i>(<span class="date">April 2022</span>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Technical plainlinks metadata ambox ambox-style ambox-technical" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may be too technical for most readers to understand</b>.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Double-ended_queue&action=edit">help improve it</a> to <a href="/wiki/Wikipedia:Make_technical_articles_understandable" title="Wikipedia:Make technical articles understandable">make it understandable to non-experts</a>, without removing the technical details.</span> <span class="date-container"><i>(<span class="date">April 2022</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>double-ended queue</b> (abbreviated to <b>deque</b>, <span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa"><a href="/wiki/Help:IPA/English" title="Help:IPA/English">/<span style="border-bottom:1px dotted"><span title="'d' in 'dye'">d</span><span title="/ɛ/: 'e' in 'dress'">ɛ</span><span title="'k' in 'kind'">k</span></span>/</a></span></span> <a href="/wiki/Help:Pronunciation_respelling_key" title="Help:Pronunciation respelling key"><i title="English pronunciation respelling"><span style="font-size:90%">DEK</span></i></a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>) is an <a href="/wiki/Abstract_data_type" title="Abstract data type">abstract data type</a> that generalizes a <a href="/wiki/Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queue</a>, for which elements can be added to or removed from either the front (head) or back (tail).<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It is also often called a <b>head-tail linked list</b>, though properly this refers to a specific <a href="/wiki/Data_structure" title="Data structure">data structure</a> <i><a href="#Implementations">implementation</a></i> of a deque (see below). </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Naming_conventions">Naming conventions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=1" title="Edit section: Naming conventions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><i>Deque</i> is sometimes written <i>dequeue</i>, but this use is generally deprecated in technical literature or technical writing because <i>dequeue</i> is also a verb meaning "to remove from a queue". Nevertheless, several <a href="/wiki/Library_(computing)" title="Library (computing)">libraries</a> and some writers, such as <a href="/wiki/Alfred_Aho" title="Alfred Aho">Aho</a>, <a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft</a>, and <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman</a> in their textbook <i>Data Structures and Algorithms</i>, spell it <i>dequeue</i>. <a href="/wiki/John_C._Mitchell" title="John C. Mitchell">John Mitchell</a>, author of <i>Concepts in Programming Languages,</i> also uses this terminology. </p> <div class="mw-heading mw-heading2"><h2 id="Distinctions_and_sub-types">Distinctions and sub-types</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=2" title="Edit section: Distinctions and sub-types"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This differs from the queue abstract data type or <i>first in first out</i> list (<a href="/wiki/FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a>), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types: </p> <ul><li>An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.</li> <li>An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.</li></ul> <p>Both the basic and most common list types in computing, <a href="/wiki/Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queues</a> and <a href="/wiki/Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stacks</a> can be considered specializations of deques, and can be implemented using deques. A deque is a data structure that allows users to perform push and pop operations at both ends, providing flexibility in managing the order of elements. </p> <div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=3" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size mw-halign-right" typeof="mw:File"><a href="/wiki/File:UML_deque.svg" class="mw-file-description" title="UML class diagram of a double-ended queue"><img alt="UML class diagram of a double-ended queue" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6d/UML_deque.svg/161px-UML_deque.svg.png" decoding="async" width="161" height="183" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6d/UML_deque.svg/242px-UML_deque.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6d/UML_deque.svg/322px-UML_deque.svg.png 2x" data-file-width="161" data-file-height="183" /></a><figcaption>UML class diagram of a double-ended queue</figcaption></figure> <p>The basic operations on a deque are <i>enqueue</i> and <i>dequeue</i> on either end. Also generally implemented are <i><a href="/wiki/Peek_(data_type_operation)" title="Peek (data type operation)">peek</a></i> operations, which return the value at that end without dequeuing it. </p><p>Names vary between languages; major implementations include: </p> <table class="wikitable"> <tbody><tr> <th>operation</th> <th>common name(s)</th> <th><a href="/wiki/Ada_(programming_language)" title="Ada (programming language)">Ada</a></th> <th><a href="/wiki/C%2B%2B" title="C++">C++</a></th> <th><a href="/wiki/Java_(programming_language)" title="Java (programming language)">Java</a></th> <th><a href="/wiki/Perl" title="Perl">Perl</a></th> <th><a href="/wiki/PHP" title="PHP">PHP</a></th> <th><a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a></th> <th><a href="/wiki/Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a> </th> <th><a href="/wiki/Rust_(programming_language)" title="Rust (programming language)">Rust</a> </th> <th><a href="/wiki/JavaScript" title="JavaScript">JavaScript</a> </th></tr> <tr> <td>insert element at back</td> <td>inject, snoc, push</td> <td><code>Append</code></td> <td><code>push_back</code></td> <td><code>offerLast</code></td> <td><code>push</code></td> <td><code>array_push</code></td> <td><code>append</code></td> <td><code>push</code> </td> <td><code>push_back</code></td> <td><code>push</code> </td></tr> <tr> <td>insert element at front</td> <td>push, cons</td> <td><code>Prepend</code></td> <td><code>push_front</code></td> <td><code>offerFirst</code></td> <td><code>unshift</code></td> <td><code>array_unshift</code></td> <td><code>appendleft</code></td> <td><code>unshift</code> </td> <td><code>push_front</code></td> <td><code>unshift</code> </td></tr> <tr> <td>remove last element</td> <td>eject</td> <td><code>Delete_Last</code></td> <td><code>pop_back</code></td> <td><code>pollLast</code></td> <td><code>pop</code></td> <td><code>array_pop</code></td> <td><code>pop</code></td> <td><code>pop</code> </td> <td><code>pop_back</code></td> <td><code>pop</code> </td></tr> <tr> <td>remove first element</td> <td>pop</td> <td><code>Delete_First</code></td> <td><code>pop_front</code></td> <td><code>pollFirst</code></td> <td><code>shift</code></td> <td><code>array_shift</code></td> <td><code>popleft</code></td> <td><code>shift</code> </td> <td><code>pop_front</code></td> <td><code>shift</code> </td></tr> <tr> <td>examine last element</td> <td>peek </td> <td><code>Last_Element</code></td> <td><code>back</code></td> <td><code>peekLast</code></td> <td><code>$array[-1]</code></td> <td><code>end</code></td> <td><code><obj>[-1]</code></td> <td><code>last</code> </td> <td><code>back</code></td> <td><code><obj>.at(-1)</code> </td></tr> <tr> <td>examine first element</td> <td></td> <td><code>First_Element</code></td> <td><code>front</code></td> <td><code>peekFirst</code></td> <td><code>$array[0]</code></td> <td><code>reset</code></td> <td><code><obj>[0]</code></td> <td><code>first</code> </td> <td><code>front</code></td> <td><code><obj>[0]</code> </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=4" title="Edit section: Implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are at least two common ways to efficiently implement a deque: with a modified <a href="/wiki/Dynamic_array" title="Dynamic array">dynamic array</a> or with a <a href="/wiki/Doubly_linked_list" title="Doubly linked list">doubly linked list</a>. </p><p>The dynamic array approach uses a variant of a <a href="/wiki/Dynamic_array" title="Dynamic array">dynamic array</a> that can grow from both ends, sometimes called <b>array deques</b>. These array deques have all the properties of a dynamic array, such as constant-time <a href="/wiki/Random_access" title="Random access">random access</a>, good <a href="/wiki/Locality_of_reference" title="Locality of reference">locality of reference</a>, and inefficient insertion/removal in the middle, with the addition of amortized constant-time insertion/removal at both ends, instead of just one end. Three common implementations include: </p> <ul><li>Storing deque contents in a <a href="/wiki/Circular_buffer" title="Circular buffer">circular buffer</a>, and only resizing when the buffer becomes full. This decreases the frequency of resizings.</li> <li>Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.</li> <li>Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Purely_functional_implementation">Purely functional implementation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=5" title="Edit section: Purely functional implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Double-ended queues can also be implemented as a <a href="/wiki/Purely_functional_data_structure" title="Purely functional data structure">purely functional data structure</a>.<sup id="cite_ref-functional_3-0" class="reference"><a href="#cite_note-functional-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 115">: 115 </span></sup> Two versions of the implementation exist. The first one, called '<i>real-time deque</i>, is presented below. It allows the queue to be <a href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent</a> with operations in <span class="texhtml"><i>O</i>(1)</span> worst-case time, but requires <a href="/wiki/Lazy_evaluation" title="Lazy evaluation">lazy</a> lists with <a href="/wiki/Memoization" title="Memoization">memoization</a>. The second one, with no lazy lists nor memoization is presented at the end of the sections. Its <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized</a> time is <span class="texhtml"><i>O</i>(1)</span> if the persistency is not used; but the worst-time complexity of an operation is <span class="texhtml"><i>O</i>(<i>n</i>)</span> where <span class="texhtml mvar" style="font-style:italic;">n</span> is the number of elements in the double-ended queue. </p><p>Let us recall that, for a list <code>l</code>, <code>|l|</code> denotes its length, that <code>NIL</code> represents an empty list and <code>CONS(h, t)</code> represents the list whose head is <code>h</code> and whose tail is <code>t</code>. The functions <code>drop(i, l)</code> and <code>take(i, l)</code> return the list <code>l</code> without its first <code>i</code> elements, and the first <code>i</code> elements of <code>l</code>, respectively. Or, if <code>|l| < i</code>, they return the empty list and <code>l</code> respectively. </p> <div class="mw-heading mw-heading4"><h4 id="Real-time_deques_via_lazy_rebuilding_and_scheduling">Real-time deques via lazy rebuilding and scheduling</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=6" title="Edit section: Real-time deques via lazy rebuilding and scheduling"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A double-ended queue is represented as a sextuple <code>(len_front, front, tail_front, len_rear, rear, tail_rear)</code> where <code>front</code> is a <a href="/wiki/Linked_list" title="Linked list">linked list</a> which contains the front of the queue of length <code>len_front</code>. Similarly, <code>rear</code> is a linked list which represents the reverse of the rear of the queue, of length <code>len_rear</code>. Furthermore, it is assured that <code>|front| ≤ 2|rear|+1</code> and <code>|rear| ≤ 2|front|+1</code> - intuitively, it means that both the front and the rear contains between a third minus one and two thirds plus one of the elements. Finally, <code>tail_front</code> and <code>tail_rear</code> are tails of <code>front</code> and of <code>rear</code>, they allow scheduling the moment where some lazy operations are forced. Note that, when a double-ended queue contains <code>n</code> elements in the front list and <code>n</code> elements in the rear list, then the inequality invariant remains satisfied after <code>i</code> insertions and <code>d</code> deletions when <code>(i+d) ≤ n/2</code>. That is, at most <code>n/2</code> operations can happen between each rebalancing. </p><p>Let us first give an implementation of the various operations that affect the front of the deque - cons, head and tail. Those implementations do not necessarily respect the invariant. In a second time we'll explain how to modify a deque which does not satisfy the invariant into one which satisfies it. However, they use the invariant, in that if the front is empty then the rear has at most one element. The operations affecting the rear of the list are defined similarly by symmetry. </p> <div class="mw-highlight mw-highlight-lang-sml mw-content-ltr" dir="ltr"><pre><span></span><span class="n">empty</span> <span class="p">=</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">NIL</span><span class="p">,</span> <span class="n">NIL</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">NIL</span><span class="p">,</span> <span class="n">NIL</span><span class="p">)</span> <span class="kr">fun</span> <span class="nf">insert'</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">len_front</span><span class="p">,</span> <span class="n">front</span><span class="p">,</span> <span class="n">tail_front</span><span class="p">,</span> <span class="n">len_rear</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">tail_rear</span><span class="p">))</span> <span class="p">=</span> <span class="p">(</span><span class="n">len_front+</span><span class="mi">1</span><span class="p">,</span> <span class="n">CONS</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">front</span><span class="p">),</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">tail_front</span><span class="p">),</span> <span class="n">len_rear</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">tail_rear</span><span class="p">))</span> <span class="kr">fun</span> <span class="nf">head</span><span class="p">((_,</span> <span class="n">CONS</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="p">_),</span> <span class="p">_,</span> <span class="p">_,</span> <span class="p">_,</span> <span class="p">_))</span> <span class="p">=</span> <span class="n">h</span> <span class="kr">fun</span> <span class="nf">head</span><span class="p">((_,</span> <span class="n">NIL</span><span class="p">,</span> <span class="p">_,</span> <span class="p">_,</span> <span class="n">CONS</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="n">NIL</span><span class="p">),</span> <span class="p">_))</span> <span class="p">=</span> <span class="n">h</span> <span class="kr">fun</span> <span class="nf">tail'</span><span class="p">((</span><span class="n">len_front</span><span class="p">,</span> <span class="n">CONS</span><span class="p">(</span><span class="n">head_front</span><span class="p">,</span> <span class="n">front</span><span class="p">),</span> <span class="n">tail_front</span><span class="p">,</span> <span class="n">len_rear</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">tail_rear</span><span class="p">))</span> <span class="p">=</span> <span class="p">(</span><span class="n">len_front</span> <span class="n">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">front</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">tail_front</span><span class="p">),</span> <span class="n">len_rear</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">tail_rear</span><span class="p">))</span> <span class="kr">fun</span> <span class="nf">tail'</span><span class="p">((_,</span> <span class="n">NIL</span><span class="p">,</span> <span class="p">_,</span> <span class="p">_,</span> <span class="n">CONS</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="n">NIL</span><span class="p">),</span> <span class="p">_))</span> <span class="p">=</span> <span class="n">empty</span> </pre></div> <p>It remains to explain how to define a method <code>balance</code> that rebalance the deque if <code>insert'</code> or <code>tail</code> broke the invariant. The method <code>insert</code> and <code>tail</code> can be defined by first applying <code>insert'</code> and <code>tail'</code> and then applying <code>balance</code>. </p> <div class="mw-highlight mw-highlight-lang-sml mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">fun</span> <span class="nf">balance</span><span class="p">(</span><span class="n">q</span> <span class="kr">as</span> <span class="p">(</span><span class="n">len_front</span><span class="p">,</span> <span class="n">front</span><span class="p">,</span> <span class="n">tail_front</span><span class="p">,</span> <span class="n">len_rear</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">tail_rear</span><span class="p">))</span> <span class="p">=</span> <span class="kr">let</span> <span class="n">floor_half_len</span> <span class="p">=</span> <span class="p">(</span><span class="n">len_front</span> <span class="n">+</span> <span class="n">len_rear</span><span class="p">)</span> <span class="n">/</span> <span class="mi">2</span> <span class="kr">in</span> <span class="kr">let</span> <span class="n">ceil_half_len</span> <span class="p">=</span> <span class="n">len_front</span> <span class="n">+</span> <span class="n">len_rear</span> <span class="n">-</span> <span class="n">floor_half_len</span> <span class="kr">in</span> <span class="kr">if</span> <span class="n">len_front</span> <span class="n">></span> <span class="mi">2</span><span class="n">*len_rear+</span><span class="mi">1</span> <span class="kr">then</span> <span class="kr">let</span> <span class="kr">val</span> <span class="nv">front'</span> <span class="p">=</span> <span class="n">take</span><span class="p">(</span><span class="n">ceil_half_len</span><span class="p">,</span> <span class="n">front</span><span class="p">)</span> <span class="kr">val</span> <span class="nv">rear'</span> <span class="p">=</span> <span class="n">rotateDrop</span><span class="p">(</span><span class="n">rear</span><span class="p">,</span> <span class="n">floor_half_len</span><span class="p">,</span> <span class="n">front</span><span class="p">)</span> <span class="kr">in</span> <span class="p">(</span><span class="n">ceil_half_len</span><span class="p">,</span> <span class="n">front'</span><span class="p">,</span> <span class="n">front'</span><span class="p">,</span> <span class="n">floor_half_len</span><span class="p">,</span> <span class="n">rear'</span><span class="p">,</span> <span class="n">rear'</span><span class="p">)</span> <span class="kr">else</span> <span class="kr">if</span> <span class="n">len_front</span> <span class="n">></span> <span class="mi">2</span><span class="n">*len_rear+</span><span class="mi">1</span> <span class="kr">then</span> <span class="kr">let</span> <span class="kr">val</span> <span class="nv">rear'</span> <span class="p">=</span> <span class="n">take</span><span class="p">(</span><span class="n">floor_half_len</span><span class="p">,</span> <span class="n">rear</span><span class="p">)</span> <span class="kr">val</span> <span class="nv">front'</span> <span class="p">=</span> <span class="n">rotateDrop</span><span class="p">(</span><span class="n">front</span><span class="p">,</span> <span class="n">ceil_half_len</span><span class="p">,</span> <span class="n">rear</span><span class="p">)</span> <span class="kr">in</span> <span class="p">(</span><span class="n">ceil_half_len</span><span class="p">,</span> <span class="n">front'</span><span class="p">,</span> <span class="n">front'</span><span class="p">,</span> <span class="n">floor_half_len</span><span class="p">,</span> <span class="n">rear'</span><span class="p">,</span> <span class="n">rear'</span><span class="p">)</span> <span class="kr">else</span> <span class="n">q</span> </pre></div> <p>where <code>rotateDrop(front, i, rear))</code> return the concatenation of <code>front</code> and of <code>drop(i, rear)</code>. That is<code>front' = rotateDrop(front, ceil_half_len, rear)</code> put into <code>front'</code> the content of <code>front</code> and the content of <code>rear</code> that is not already in <code>rear'</code>. Since dropping <code>n</code> elements takes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"></span> time, we use laziness to ensure that elements are dropped two by two, with two drops being done during each <code>tail'</code> and each <code>insert'</code> operation. </p> <div class="mw-highlight mw-highlight-lang-sml mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">fun</span> <span class="nf">rotateDrop</span><span class="p">(</span><span class="n">front</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">rear</span><span class="p">)</span> <span class="p">=</span> <span class="kr">if</span> <span class="n">i</span> <span class="n"><</span> <span class="mi">2</span> <span class="kr">then</span> <span class="n">rotateRev</span><span class="p">(</span><span class="n">front</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">rear</span><span class="p">),</span> <span class="n">NIL</span><span class="p">)</span> <span class="kr">else</span> <span class="kr">let</span> <span class="n">CONS</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">front'</span><span class="p">)</span> <span class="p">=</span> <span class="n">front</span> <span class="kr">in</span> <span class="n">CONS</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">rotateDrop</span><span class="p">(</span><span class="n">front'</span><span class="p">,</span> <span class="n">j-</span><span class="mi">2</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">rear</span><span class="p">)))</span> </pre></div> <p>where <code>rotateRev(front, middle, rear)</code> is a function that returns the front, followed by the middle reversed, followed by the rear. This function is also defined using laziness to ensure that it can be computed step by step, with one step executed during each <code>insert'</code> and <code>tail'</code> and taking a constant time. This function uses the invariant that <code>|rear|-2|front|</code> is 2 or 3. </p> <div class="mw-highlight mw-highlight-lang-sml mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">fun</span> <span class="nf">rotateRev</span><span class="p">(</span><span class="n">NIL</span><span class="p">,</span> <span class="n">rear</span><span class="p">,</span> <span class="n">a</span><span class="p">)</span> <span class="p">=</span> <span class="n">reverse</span><span class="p">(</span><span class="n">rear</span><span class="p">)</span><span class="n">++a</span> <span class="kr">fun</span> <span class="nf">rotateRev</span><span class="p">(</span><span class="n">CONS</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">front</span><span class="p">),</span> <span class="n">rear</span><span class="p">,</span> <span class="n">a</span><span class="p">)</span> <span class="p">=</span> <span class="n">CONS</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">rotateRev</span><span class="p">(</span><span class="n">front</span><span class="p">,</span> <span class="n">drop</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">rear</span><span class="p">),</span> <span class="n">reverse</span><span class="p">(</span><span class="n">take</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">rear</span><span class="p">))</span><span class="n">++a</span><span class="p">))</span> </pre></div> <p>where <code>++</code> is the function concatenating two lists. </p> <div class="mw-heading mw-heading4"><h4 id="Implementation_without_laziness">Implementation without laziness</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=7" title="Edit section: Implementation without laziness"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Note that, without the lazy part of the implementation, this would be a non-persistent implementation of queue in <span class="texhtml"><i>O</i>(1)</span> <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized time</a>. In this case, the lists <code>tail_front</code> and <code>tail_rear</code> could be removed from the representation of the double-ended queue. </p> <div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=8" title="Edit section: Language support"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Ada_(programming_language)" title="Ada (programming language)">Ada</a>'s containers provides the generic packages <code>Ada.Containers.Vectors</code> and <code>Ada.Containers.Doubly_Linked_Lists</code>, for the dynamic array and linked list implementations, respectively. </p><p>C++'s <a href="/wiki/Standard_Template_Library" title="Standard Template Library">Standard Template Library</a> provides the class templates <code>std::deque</code> and <code>std::list</code>, for the multiple array and linked list implementations, respectively. </p><p>As of Java 6, Java's Collections Framework provides a new <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/Deque.html">Deque</a></code> interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/ArrayDeque.html">ArrayDeque</a></code> (also new in Java 6) and <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/LinkedList.html">LinkedList</a></code>, providing the dynamic array and linked list implementations, respectively. However, the <code>ArrayDeque</code>, contrary to its name, does not support random access. </p><p>Javascript's <a rel="nofollow" class="external text" href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array">Array prototype</a> & <a href="/wiki/Perl" title="Perl">Perl</a>'s arrays have native support for both removing (<a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/shift.html">shift</a> and <a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/pop.html">pop</a>) and adding (<a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/unshift.html">unshift</a> and <a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/push.html">push</a>) elements on both ends. </p><p>Python 2.4 introduced the <code>collections</code> module with support for <a rel="nofollow" class="external text" href="https://docs.python.org/3/library/collections.html#deque-objects">deque objects</a>. It is implemented using a doubly linked list of fixed-length subarrays. </p><p>As of PHP 5.3, PHP's SPL extension contains the 'SplDoublyLinkedList' class that can be used to implement Deque datastructures. Previously to make a Deque structure the array functions array_shift/unshift/pop/push had to be used instead. </p><p><a href="/wiki/Glasgow_Haskell_Compiler" title="Glasgow Haskell Compiler">GHC</a>'s <a rel="nofollow" class="external text" href="http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html">Data.Sequence</a> module implements an efficient, functional deque structure in <a href="/wiki/Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a>. The implementation uses <a href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3 finger trees</a> annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also <a href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent</a>) double queues (most using heavily <a href="/wiki/Lazy_evaluation" title="Lazy evaluation">lazy evaluation</a>).<sup id="cite_ref-functional_3-1" class="reference"><a href="#cite_note-functional-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Kaplan and Tarjan were the first to implement optimal confluently persistent catenable deques.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Their implementation was strictly purely functional in the sense that it did not use lazy evaluation. Okasaki simplified the data structure by using lazy evaluation with a bootstrapped data structure and degrading the performance bounds from worst-case to amortized.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Kaplan, Okasaki, and Tarjan produced a simpler, non-bootstrapped, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in a broader but still restricted fashion.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Mihaescu and Tarjan created a simpler (but still highly complex) strictly purely functional implementation of catenable deques, and also a much simpler implementation of strictly purely functional non-catenable deques, both of which have optimal worst-case bounds.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>Rust's <code>std::collections</code> includes <a rel="nofollow" class="external text" href="https://doc.rust-lang.org/std/collections/struct.VecDeque.html">VecDeque</a> which implements a double-ended queue using a growable ring buffer. </p> <div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=9" title="Edit section: Complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>In a doubly-linked list implementation and assuming no allocation/deallocation overhead, the <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">time complexity</a> of all deque operations is <a href="/wiki/Big_O_notation" title="Big O notation">O(1)</a>. Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).</li> <li>In a growing array, the <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized</a> time complexity of all deque operations is <a href="/wiki/Big_O_notation" title="Big O notation">O(1)</a>. Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is <a href="/wiki/Big_O_notation" title="Big O notation">O(n)</a>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=10" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Back_button_history_(Ecosia_browser_-_Google_Pixel_4a)_-_Google_Android_12_(cropped).png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png/220px-Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png" decoding="async" width="220" height="285" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png/330px-Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/74/Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png/440px-Back_button_history_%28Ecosia_browser_-_Google_Pixel_4a%29_-_Google_Android_12_%28cropped%29.png 2x" data-file-width="1080" data-file-height="1401" /></a><figcaption>A double-ended queue can be used to store the <a href="/wiki/Web_browsing_history" title="Web browsing history">browsing history</a>: new websites are added to the end of the queue, while the oldest entries will be deleted when the history is too large. When a user asks to clear the browsing history for the past hour, the most recently added entries are removed.</figcaption></figure> <p>One example where a deque can be used is the <a href="/wiki/Work_stealing" title="Work stealing">work stealing algorithm</a>.<sup id="cite_ref-jacm_9-0" class="reference"><a href="#cite_note-jacm-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it. The work stealing algorithm is used by Intel's Threading Building Blocks (TBB) library for parallel programming. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Pipeline_(Unix)#pipe_character" title="Pipeline (Unix)">Pipe</a></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=12" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Jesse Liberty; Siddhartha Rao; Bradley Jones. <i>C++ in One Hour a Day, Sams Teach Yourself</i>, Sixth Edition. Sams Publishing, 2009. <style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-672-32941-7" title="Special:BookSources/0-672-32941-7">0-672-32941-7</a>. Lesson 18: STL Dynamic Array Classes, pp. 486.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>. <i><a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a></i>, Volume 1: <i>Fundamental Algorithms</i>, Third Edition. Addison-Wesley, 1997. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-201-89683-4" title="Special:BookSources/0-201-89683-4">0-201-89683-4</a>. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.</span> </li> <li id="cite_note-functional-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-functional_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-functional_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOkasaki1996" class="citation thesis cs1">Okasaki, Chris (September 1996). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~rwh/students/okasaki.pdf"><i>Purely Functional Data Structures</i></a> <span class="cs1-format">(PDF)</span> (Ph.D. thesis). Carnegie Mellon University. CMU-CS-96-177.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Purely+Functional+Data+Structures&rft.inst=Carnegie+Mellon+University&rft.date=1996-09&rft.aulast=Okasaki&rft.aufirst=Chris&rft_id=https%3A%2F%2Fwww.cs.cmu.edu%2F~rwh%2Fstudents%2Fokasaki.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADouble-ended+queue" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. In ACM Symposium on Theory of Computing, pages 202–211, May 1996. (pp. 4, 82, 84, 124)</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Chris Okasaki (Aug. 1997), <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/258949.258956">Catenable double-ended queues</a>, ACM SIGPLAN Notices Volume 32 Issue 8</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"> Haim Kaplan, Chris Okasaki, and Robert E. Tarjan (2000), <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/S0097539798339430">Simple Confluently Persistent Catenable Lists</a>, SIAM Journal on Computing Vol. 30, Iss. 3</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Radu Mihaescu and Robert Tarjan (Aug. 2003), <a rel="nofollow" class="external text" href="https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc">Notes on Catenable Deques in Pure Lisp</a>, Princetown University, COS 528, Fall 03</span> </li> <li id="cite_note-jacm-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-jacm_9-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBlumofeLeiserson1999" class="citation journal cs1">Blumofe, Robert D.; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a> (1999). <a rel="nofollow" class="external text" href="http://supertech.csail.mit.edu/papers/ft_gateway.pdf">"Scheduling multithreaded computations by work stealing"</a> <span class="cs1-format">(PDF)</span>. <i>J ACM</i>. <b>46</b> (5): 720–748. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F324133.324234">10.1145/324133.324234</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5428476">5428476</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J+ACM&rft.atitle=Scheduling+multithreaded+computations+by+work+stealing&rft.volume=46&rft.issue=5&rft.pages=720-748&rft.date=1999&rft_id=info%3Adoi%2F10.1145%2F324133.324234&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A5428476%23id-name%3DS2CID&rft.aulast=Blumofe&rft.aufirst=Robert+D.&rft.au=Leiserson%2C+Charles+E.&rft_id=http%3A%2F%2Fsupertech.csail.mit.edu%2Fpapers%2Fft_gateway.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADouble-ended+queue" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Double-ended_queue&action=edit&section=13" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://ccodearchive.net/info/deque.html">Type-safe open source deque implementation at Comprehensive C Archive Network</a></li> <li><a rel="nofollow" class="external text" href="http://www.sgi.com/tech/stl/Deque.html">SGI STL Documentation: deque<T, Alloc></a></li> <li><a rel="nofollow" class="external text" href="http://www.codeproject.com/KB/stl/vector_vs_deque.aspx">Code Project: An In-Depth Study of the STL Deque Container</a></li> <li><a rel="nofollow" class="external text" href="http://www.martinbroadhurst.com/articles/deque.html">Deque implementation in C</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140306145414/http://www.martinbroadhurst.com/articles/deque.html">Archived</a> 2014-03-06 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110714000645/http://www.ludvikjerabek.com/downloads.html">VBScript implementation of stack, queue, deque, and Red-Black Tree</a></li> <li><a rel="nofollow" class="external text" href="https://code.google.com/p/deques/source/browse/">Multiple implementations of non-catenable deques in Haskell</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a class="mw-selflink selflink">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Double-ended_queue&oldid=1233074336">https://en.wikipedia.org/w/index.php?title=Double-ended_queue&oldid=1233074336</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Abstract_data_types" title="Category:Abstract data types">Abstract data types</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_introduction_cleanup_from_April_2022" title="Category:Wikipedia introduction cleanup from April 2022">Wikipedia introduction cleanup from April 2022</a></li><li><a href="/wiki/Category:All_pages_needing_cleanup" title="Category:All pages needing cleanup">All pages needing cleanup</a></li><li><a href="/wiki/Category:Articles_covered_by_WikiProject_Wikify_from_April_2022" title="Category:Articles covered by WikiProject Wikify from April 2022">Articles covered by WikiProject Wikify from April 2022</a></li><li><a href="/wiki/Category:All_articles_covered_by_WikiProject_Wikify" title="Category:All articles covered by WikiProject Wikify">All articles covered by WikiProject Wikify</a></li><li><a href="/wiki/Category:Wikipedia_articles_that_are_too_technical_from_April_2022" title="Category:Wikipedia articles that are too technical from April 2022">Wikipedia articles that are too technical from April 2022</a></li><li><a href="/wiki/Category:All_articles_that_are_too_technical" title="Category:All articles that are too technical">All articles that are too technical</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 7 July 2024, at 04:04<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Double-ended_queue&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-7c4dcdbb87-qz2zd","wgBackendResponseTime":217,"wgPageParseReport":{"limitreport":{"cputime":"0.409","walltime":"0.843","ppvisitednodes":{"value":1731,"limit":1000000},"postexpandincludesize":{"value":30271,"limit":2097152},"templateargumentsize":{"value":1286,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":10,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":40026,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 754.939 1 -total"," 16.02% 120.943 1 Template:Reflist"," 10.04% 75.795 1 Template:Short_description"," 9.38% 70.790 1 Template:Tooshort"," 8.78% 66.297 1 Template:Data_structures"," 8.60% 64.925 1 Template:Navbox"," 8.44% 63.705 2 Template:Ambox"," 8.01% 60.499 1 Template:Cite_thesis"," 6.24% 47.118 2 Template:Pagetype"," 5.13% 38.754 2 Template:ISBN"]},"scribunto":{"limitreport-timeusage":{"value":"0.221","limit":"10.000"},"limitreport-memusage":{"value":5608470,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-5857dfdcd6-55pvz","timestamp":"20241203070403","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Double-ended queue","url":"https:\/\/en.wikipedia.org\/wiki\/Double-ended_queue","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1192005","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1192005","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2002-02-25T15:43:11Z","dateModified":"2024-07-07T04:04:49Z","headline":"abstract data type for which elements can be added to or removed from either the front or back"}</script> </body> </html>