Dubbel kö

"Deque" omdirigerar hit. Ej att förväxla med avköning, en köoperation .
Ej att förväxla med dubbeländad prioritetskö .

Inom datavetenskap är en dubbeländad kö (förkortat till deque , uttalas deck , som "check") en abstrakt datatyp som generaliserar en kö , för vilken element kan läggas till eller tas bort från antingen framsidan (huvudet) eller baksidan (svans). Det kallas också ofta för en head-tail-länkad lista , även om detta korrekt hänvisar till en specifik datastrukturimplementering av en deque (se nedan) .

Namnkonventioner

Deque skrivs ibland dequeue , men denna användning förkastas i allmänhet i teknisk litteratur eller teknisk skrift eftersom dequeue också är ett verb som betyder "att ta bort från en kö". Ändå stavar flera bibliotek och vissa författare, som Aho , Hopcroft och Ullman i sin lärobok Data Structures and Algorithms , it dequeue . John Mitchell , författare till Concepts in Programming Languages, använder också denna terminologi.

Distinktioner och undertyper

Detta skiljer sig från köabstraktdatatypen eller först in först ut -listan ( FIFO ), där element bara kan läggas till i ena änden och tas bort från den andra. Denna allmänna dataklass har några möjliga undertyper:

  • En inmatningsbegränsad deque är en där radering kan göras från båda ändarna, men insättning kan endast göras i ena änden.
  • En utmatningsbegränsad deque är en där infogning kan göras i båda ändar, men radering kan endast göras från ena änden.

Både de grundläggande och vanligaste listtyperna inom datoranvändning, köer och stackar kan betraktas som specialiseringar av deques, och kan implementeras med hjälp av deques.

Operationer

De grundläggande operationerna på en deque är enqueue och dequeue i vardera änden. Också generellt implementerade är kikoperationer , som returnerar värdet i den änden utan att köa det.

Namnen varierar mellan språken; viktiga implementeringar inkluderar:

drift vanligt namn Ada C++ Java Perl PHP Pytonorm Rubin Rost JavaScript
insatselement baktill injicera, snoc, push Bifoga trycka tillbaka erbjudandeSist skjuta på array_push bifoga skjuta på trycka tillbaka skjuta på
sätt in element framtill trycka, nackdelar Addera till början push_front erbjuda först avväxling array_unshift appendleft avväxling push_front avväxling
ta bort det sista elementet mata ut Delete_Last pop_back omröstningSista pop array_pop pop pop pop_back pop
ta bort det första elementet pop Delete_First pop_front pollFirst flytta array_shift popleft flytta pop_front flytta
undersöka det sista elementet titt Last_Element tillbaka kikaSista $array[-1] slutet <obj>[-1] sista tillbaka <obj>.at(-1)
undersöka första elementet First_Element främre peekFirst $array[0] återställa <obj>[0] först främre <obj>[0]

Genomföranden

Det finns minst två vanliga sätt att effektivt implementera en deque: med en modifierad dynamisk array eller med en dubbellänkad lista .

Den dynamiska array-metoden använder en variant av en dynamisk array som kan växa från båda ändarna, ibland kallade array-deques . Dessa array-deques har alla egenskaperna hos en dynamisk array, såsom konstant-tid slumpmässig åtkomst , bra referenslokalitet och ineffektiv infogning/borttagning i mitten, med tillägg av amorterad konstanttidsinsättning/borttagning i båda ändar, istället av bara ena änden. Tre vanliga implementeringar inkluderar:

  • Lagra deque-innehåll i en cirkulär buffert och ändra storlek först när bufferten blir full. Detta minskar frekvensen av storleksändringar.
  • Tilldela deque-innehåll från mitten av den underliggande arrayen och ändra storlek på den underliggande arrayen när endera änden nås. Detta tillvägagångssätt kan kräva oftare storleksändringar och slösa mer utrymme, särskilt när element bara sätts in i ena änden.
  • Lagra innehåll i flera mindre arrayer, allokera ytterligare arrayer i början eller slutet efter behov. Indexering implementeras genom att behålla en dynamisk array som innehåller pekare till var och en av de mindre arrayerna.

Rent funktionellt genomförande

Dubbla köer kan också implementeras som en rent funktionell datastruktur . Det finns två versioner av implementeringen. Den första, som kallas ' realtidsdeque' , presenteras nedan. Det gör att kön kan vara ihållande med operationer i O (1) värsta tänkbara tid, men kräver lata listor med memoisering . Den andra, utan lata listor eller memoisering presenteras i slutet av avsnitten. Dess amorterade tid är O (1) om persistensen inte används; men den värsta komplexiteten för en operation är O ( n ) där n är antalet element i den dubbeländade kön.

Låt oss komma ihåg att, för en lista l , |l| anger dess längd, att NIL representerar en tom lista och CONS(h, t) representerar listan vars huvud är h och vars svans är t . Funktionerna drop(i, l) och take(i, l) returnerar listan l utan dess första i -element, respektive de första i- elementen av l . Eller, om |l| < i , de returnerar den tomma listan respektive l .

Deques i realtid via lat ombyggnad och schemaläggning

En dubbeländad kö representeras som en sextuppel (len_front, front, tail_front, len_rear, rear, tail_rear) där front är en länkad lista som innehåller den främre delen av kön med längden len_front . På liknande sätt bak en länkad lista som representerar baksidan av köns baksida, med längden len_rear . Dessutom är det säkerställt att |front| ≤ 2|bakre|+1 och |bakre| ≤ 2|front|+1 - intuitivt betyder det att både fronten och baksidan innehåller mellan en tredjedel minus en och två tredjedelar plus ett av elementen. Slutligen, tail_front och tail_rear är svansar av fram och bak , de tillåter schemaläggning av det ögonblick då vissa lata operationer tvingas fram. Observera att, när en dubbeländad kö innehåller n element i den främre listan och n element i den bakre listan, förblir olikhetsinvarianten uppfylld efter i- insättningar och d- deletioner när (i+d) ≤ n/2 . Det vill säga att högst n/2 operationer kan ske mellan varje ombalansering.

Låt oss först ge en implementering av de olika operationerna som påverkar fronten av deque - nackdelar, huvud och svans. Dessa implementeringar respekterar inte nödvändigtvis det invarianta. Om en andra gång kommer vi att förklara hur man ändrar en deque som inte uppfyller invarianten till en som uppfyller den. Däremot använder de invarianten, i det att om fronten är tom så har den bakre högst ett element. Operationerna som påverkar den bakre delen av listan definieras på liknande sätt av symmetri.

  0   0  
        
          
         
         
        
           
          empty  =  (  ,  NIL  ,  NIL  ,  ,  NIL  ,  NIL  )  fun  insert'  (  x  ,  (  len_front  ,  front  ,  tail_front  ,  len_rear  ,  rear  ,  tail_rear  ))  =  (  len_front+  1  ,  CONS  (  x  ,  front  ),  drop  (  2  ,  tail_front )  ),  len_rear  ,  rear  ,  drop  (  2  ,  tail_rear  ))  fun  head  ((_,  CONS  (  h  ,  _),  _,  _,  _,  _))  =  h  roligt  huvud  ((_,  NIL  ,  _,  _,  CONS  (  h  ,  NIL  ),  _))  =  h  fun  tail'  ((  len_front  ,  CONS  (  head_front  ,  front  ),  tail_front  ,  len_rear  ,  rear  ,  tail_rear  ))  =  (  len_front  -  1  ,  front  ,  drop  (  2  ,  tail_front  ),  len_rear  ,  bak  ,  drop  (  2  ,  tail_rear  ))  fun  tail'  ((_,  NIL  ,  _,  _,  CONS  (  h  ,  NIL  ),  _))  =  tom

Det återstår att förklara hur man definierar en metodbalans som återbalanserar dequen om insert' eller tail bröt invarianten. Metoden insert och tail kan definieras genom att först applicera insert' and tail' och sedan applicera balans . 

         
          
          
      
         
             
          
       
         
             
           rolig  balans  (  q  as  (  len_front  ,  front  ,  tail_front  ,  len_rear  ,  rear  ,  tail_rear  )  )  =  let  floor_half_len  =  (  len_front  +  len_rear  )  /  2  in  let  ceil_half_len  =  len_front  +  len_rear  -  floor_half_rear  in  2  *  len_rear  -  floor_half_rear  >  +  1  front'  =  take  (  ceil_half_len  ,  front  )  val  rear'  =  rotateDrop  (  rear  ,  floor_half_len  ,  front  )  in  (  ceil_half_len  ,  front'  ,  front  '  ,  floor_half_len  ,  rear'  ,  rear  '  )  annars  om  len_front  >  2  *  1  then_rear  rear'  =  take  (  floor_half_len  ,  rear  )  val  front'  =  rotateDrop  (  front  ,  ceil_half_len  ,  rear  )  in  (  ceil_half_len  ,  front'  ,  front  '  ,  floor_half_len  ,  rear'  ,  rear')  annars  q

där rotateDrop(front, i, rear)) returnerar sammansättningen av front och drop(i, rear) . Det vill säga front' = rotateDrop(front, ceil_half_len, rear) sätta in front' innehållet i fronten och innehållet på baksidan som inte redan finns i rear' . Eftersom att släppa n element tar tid, använder vi lathet för att säkerställa att element släpps två och två, med två droppar under varje tail' och varje insert' operation. 

    
          
        
          fun  rotateDrop  (  front  ,  i  ,  rear  )  =  om  i  <  2  sedan  rotateRev  (  front  ,  drop  (  i  ,  rear  ),  $NIL  )  annars  låt  $CONS  (  x  ,  front'  )  =  front  in  $CONS  (  x  ,  rotateDrop  (  front) '  ,  j-  2  ,  drop  (  2  ,  bak  )))

där rotateRev(front, middle, rear) är en funktion som returnerar fronten, följt av mitten omvänd, följt av den bakre. Denna funktion definieras också med hjälp av lättja för att säkerställa att den kan beräknas steg för steg, med ett steg som exekveras under varje insättning och svans och tar konstant tid. Denna funktion använder invarianten som |rear|-2|front| är 2 eller 3. 

   
  
    
         fun  rotateRev  (  NIL  ,  rear  ,  a  )=  reverse  (  rear++a  )  fun  rotateRev  (  CONS  (  x  ,  front  ),  rear  ,  a  )=  CONS  (  x  ,  rotateRev  (  front  ,  drop  (  2  ,  rear  ),  reverse  (  ta  (  2  ,  bak  ))  ++a  ))

där ++ är funktionen som sammanlänkar två listor.

Genomförande utan lättja

Observera att utan den lata delen av implementeringen skulle detta vara en icke-beständig implementering av kö i O (1) amorterad tid . I det här fallet kan listorna tail_front och tail_rear tas bort från representationen av den dubbelsidiga kön.

Språkstöd

Adas behållare tillhandahåller de generiska paketen Ada.Containers.Vectors och Ada.Containers.Doubly_Linked_Lists , för implementeringen av dynamisk array respektive länkad list.

C++:s standardmallbibliotek tillhandahåller klassmallarna std::deque och std::list , för implementeringar av flera arrayer respektive länkade listor.

Från och med Java 6 tillhandahåller Javas Collections Framework ett nytt Deque- gränssnitt som ger funktionen för insättning och borttagning i båda ändar. Det implementeras av klasser som ArrayDeque (också nytt i Java 6) och LinkedList , som tillhandahåller den dynamiska arrayen respektive den länkade listimplementeringen. ArrayDeque , i motsats till dess namn, stöder dock inte slumpmässig åtkomst.

Javascripts Array-prototyp och Perls arrayer har inbyggt stöd för både att ta bort ( shift och pop ) och lägga till ( unshift och push ) element i båda ändar.

Python 2.4 introducerade samlingsmodulen med stöd för deque-objekt . Det är implementerat med hjälp av en dubbelt länkad lista med fast längd subarrayer.

Från och med PHP 5.3 innehåller PHPs SPL-tillägg klassen 'SplDoublyLinkedList' som kan användas för att implementera Deque-datastrukturer. Tidigare för att göra en Deque-struktur behövde arrayfunktionerna array_shift/unshift/pop/push användas istället.

GHC :s Data.Sequence -modul implementerar en effektiv, funktionell deque-struktur i Haskell . Implementeringen använder 2–3 fingerträd kommenterade med storlekar. Det finns andra (snabba) möjligheter att implementera rent funktionella (därmed också beständiga ) dubbla köer (de flesta använder mycket lat utvärdering ). Kaplan och Tarjan var de första att implementera optimala konfluent ihållande catenable deques. Deras implementering var strikt rent funktionell i den meningen att den inte använde lat utvärdering. Okasaki förenklade datastrukturen genom att använda lat utvärdering med en bootstrapped datastruktur och försämrade prestandagränserna från värsta tänkbara till amorterade. Kaplan, Okasaki och Tarjan producerade en enklare, icke-bootstrapped, amorterad version som kan implementeras antingen med lat utvärdering eller mer effektivt med mutation på ett bredare men fortfarande begränsat sätt. Mihaesau och Tarjan skapade en enklare (men fortfarande mycket komplex) strikt rent funktionell implementering av catenable deques, och också en mycket enklare implementering av strikt rent funktionella icke-catenable deques, som båda har optimala worst-case-gränser.

Rusts std::-samlingar inkluderar VecDeque som implementerar en dubbeländad kö med hjälp av en odlingsbar ringbuffert.

Komplexitet

  • I en dubbellänkad listimplementering och förutsatt att ingen allokerings-/deallokeringsoverhead antas, är tidskomplexiteten för alla deque-operationer O(1) . Dessutom är tidskomplexiteten för infogning eller deletion i mitten, givet en iterator, O(1); emellertid är tidskomplexiteten för direktåtkomst genom index O(n).
  • I en växande grupp är den amorterade tidskomplexiteten för alla deque-operationer O(1) . Dessutom är tidskomplexiteten för direktåtkomst per index O(1); men tidskomplexiteten för infogning eller deletion i mitten är O(n) .

Ansökningar

En dubbeländad kö kan användas för att lagra webbhistoriken : nya webbplatser läggs till i slutet av kön, medan de äldsta posterna kommer att raderas när historiken är för stor. När en användare ber att rensa webbhistoriken för den senaste timmen tas de senast tillagda posterna bort.

Ett exempel där en deque kan användas är work stealing-algoritmen . Denna algoritm implementerar uppgiftsschemaläggning för flera processorer. En separat deque med trådar som ska exekveras upprätthålls för varje processor. För att exekvera nästa tråd får processorn det första elementet från dequen (med hjälp av "remove first element"-deque-operationen). Om den nuvarande tråden gafflar sig, läggs den tillbaka till framsidan av dequen ("infoga element framtill") och en ny tråd körs. När en av processorerna avslutar exekveringen av sina egna trådar (dvs. dess deque är tom), kan den "stjäla" en tråd från en annan processor: den hämtar det sista elementet från dequen från en annan processor ("ta bort sista element") och kör Det. Algoritmen för att stjäla arbete används av Intels bibliotek med Threading Building Blocks (TBB) för parallell programmering.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Double-ended_queue&oldid=1102750240 "