logo

TechCodeview

Deque (eller dubbeländad kö)

I den här artikeln kommer vi att diskutera dubbelkön eller deque. Vi bör först se en kort beskrivning av kön.

Vad är en kö?

En kö är en datastruktur där det som kommer först kommer att gå ut först, och den följer FIFO-policyn (First-In-First-Out). Infogning i kön görs från ena änden känd som bakända eller den svans, medan raderingen görs från en annan ände som kallas främre änden eller den huvud av kön.

wumpus värld

Det verkliga exemplet på en kö är biljettkön utanför en biosalong, där den som kommer först i kön får biljetten först och den som kommer sist i kön får biljetten till sist.

Vad är en Deque (eller dubbeländad kö)

Dequen står för Double Ended Queue. Deque är en linjär datastruktur där insättnings- och raderingsoperationerna utförs från båda ändarna. Vi kan säga att deque är en generaliserad version av kön.

Även om infogning och radering i en deque kan utföras i båda ändarna, följer den inte FIFO-regeln. Representationen av en deque ges enligt följande -

Deque (eller dubbeländad kö)

Typer av deque

Det finns två typer av deque -

  • Inmatningsbegränsad kö
  • Utmatningsbegränsad kö

Inmatningsbegränsad kö

I inmatningsbegränsad kö kan insättningsoperationen endast utföras i ena änden, medan radering kan utföras från båda ändarna.

Deque (eller dubbeländad kö)

Utmatningsbegränsad kö

I utmatningsbegränsad kö kan raderingsoperationen endast utföras i ena änden, medan infogning kan utföras från båda ändarna.

Deque (eller dubbeländad kö)

Operationer som utförs på bord

Det finns följande operationer som kan tillämpas på en bordsdäck -

  • Insättning framtill
  • Insättning baktill
  • Radering framtill
  • Radering baktill

Vi kan också utföra tittoperationer i deque tillsammans med operationerna som anges ovan. Genom kikoperation kan vi få dequens främre och bakre delar av dequen. Så, förutom ovanstående operationer, stöds följande operationer också i deque -

typer av mjukvarutestning
  • Få det främre föremålet från deque
  • Hämta den bakre artikeln från deque
  • Kontrollera om dequet är fullt eller inte
  • Kontrollerar om bordet är tomt eller inte

Låt oss nu förstå operationen som utförs på deque med hjälp av ett exempel.

Insättning i framänden

I denna operation infogas elementet från den främre änden av kön. Innan vi implementerar operationen måste vi först kontrollera om kön är full eller inte. Om kön inte är full kan elementet infogas från fronten genom att använda nedanstående villkor -

  • Om kön är tom, initieras både bak och fram med 0. Nu pekar båda på det första elementet.
  • Kontrollera annars frontens position om fronten är mindre än 1 (främre<1), then reinitialize it by front = n - 1, d.v.s. det sista indexet för matrisen.
Deque (eller dubbeländad kö)

Insättning i bakändan

I denna operation infogas elementet från den bakre änden av kön. Innan vi implementerar operationen måste vi först kontrollera igen om kön är full eller inte. Om kön inte är full, kan elementet infogas från den bakre änden genom att använda nedanstående villkor -

  • Om kön är tom, initieras både bak och fram med 0. Nu pekar båda på det första elementet.
  • Öka annars den bakre delen med 1. Om den bakre är vid sista index (eller storlek - 1), måste vi istället för att öka den med 1 göra den lika med 0.
Deque (eller dubbeländad kö)

Radering i fronten

I den här operationen raderas elementet från den främre delen av kön. Innan vi implementerar operationen måste vi först kontrollera om kön är tom eller inte.

Om kön är tom, dvs front = -1, är det underflödesvillkoret och vi kan inte utföra raderingen. Om kön inte är full kan elementet infogas från fronten genom att använda nedanstående villkor -

hitta i kartan c++

Om dequen bara har ett element, ställ in bak = -1 och fram = -1.

Annars om framsidan är i slutet (det betyder framsidan = storlek - 1), ställ in framsidan = 0.

hadoop handledning

Öka annars framsidan med 1, (dvs framsida = framsida + 1).

Deque (eller dubbeländad kö)

Radering på baksidan

I denna operation raderas elementet från den bakre änden av kön. Innan vi implementerar operationen måste vi först kontrollera om kön är tom eller inte.

Om kön är tom, dvs front = -1, är det underflödesvillkoret och vi kan inte utföra raderingen.

Om dequen bara har ett element, ställ in bak = -1 och fram = -1.

Om bak = 0 (bak är fram), ställ in bak = n - 1.

Annars, minska den bakre med 1 (eller, bak = bak -1).

Deque (eller dubbeländad kö)

Markera tom

Denna operation utförs för att kontrollera om dequen är tom eller inte. Om front = -1 betyder det att dequen är tom.

Kontrollera full

Denna operation utförs för att kontrollera om dequen är full eller inte. Om front = bak + 1, eller front = 0 och bak = n - 1 betyder det att dequen är full.

Tidskomplexiteten för alla ovanstående operationer av dequen är O(1), dvs konstant.

Tillämpningar av deque

  • Deque kan användas både som stack och kö, eftersom det stöder båda operationerna.
  • Deque kan användas som en palindromkontroll betyder att om vi läser strängen från båda ändarna, skulle strängen vara densamma.

Genomförande av deque

Låt oss nu se implementeringen av deque i programmeringsspråket C.

hur man använder mysql workbench 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

Produktion:

Deque (eller dubbeländad kö)

Så det handlar om artikeln. Hoppas att artikeln kommer att vara användbar och informativ för dig.