logo

TechCodeview

Deque (eller tosidig kø)

I denne artikkelen vil vi diskutere den doble køen eller dequen. Vi bør først se en kort beskrivelse av køen.

Hva er en kø?

En kø er en datastruktur der det som kommer først vil gå ut først, og den følger FIFO-policyen (First-In-First-Out). Innsetting i køen gjøres fra den ene enden kjent som bakenden eller hale, mens slettingen gjøres fra en annen ende kjent som frontenden eller hode av køen.

dynamisk array java

Eksemplet i den virkelige verden på en kø er billettkøen utenfor en kinosal, der personen som kommer først i køen får billetten først, og personen som kommer sist i køen får billetten til slutt.

Hva er en Deque (eller tosidig kø)

Deque står for Double Ended Queue. Deque er en lineær datastruktur der innsettings- og slettingsoperasjonene utføres fra begge ender. Vi kan si at deque er en generalisert versjon av køen.

Selv om innsetting og sletting i en deque kan utføres i begge ender, følger den ikke FIFO-regelen. Representasjonen av en deque er gitt som følger -

Deque (eller tosidig kø)

Typer deque

Det er to typer deque -

  • Inndatabegrenset kø
  • Utgangsbegrenset kø

Inndatabegrenset kø

I inngangsbegrenset kø kan innsettingsoperasjonen utføres i bare den ene enden, mens sletting kan utføres fra begge ender.

Deque (eller tosidig kø)

Utgangsbegrenset kø

I utgangsbegrenset kø kan sletteoperasjonen utføres i bare den ene enden, mens innsetting kan utføres fra begge ender.

Deque (eller tosidig kø)

Operasjoner utført på dekk

Det er følgende operasjoner som kan brukes på et bord -

  • Innsetting foran
  • Innsetting bak
  • Sletting foran
  • Sletting bak

Vi kan også utføre kikkoperasjoner i deque sammen med operasjonene som er oppført ovenfor. Gjennom kikkoperasjon kan vi få dekkets fremre og bakre elementer av dekket. Så, i tillegg til operasjonene ovenfor, støttes følgende operasjoner også i deque -

np.random.rand
  • Få den fremre gjenstanden fra deque
  • Få den bakre varen fra deque
  • Sjekk om dekken er full eller ikke
  • Sjekker om dekken er tom eller ikke

La oss nå forstå operasjonen som utføres ved hjelp av et eksempel.

Innsetting i frontenden

I denne operasjonen settes elementet inn fra frontenden av køen. Før vi implementerer operasjonen, må vi først sjekke om køen er full eller ikke. Hvis køen ikke er full, kan elementet settes inn fra frontenden ved å bruke betingelsene nedenfor -

  • Hvis køen er tom, initialiseres både bak og front med 0. Nå vil begge peke på det første elementet.
  • Ellers kontroller posisjonen til fronten hvis fronten er mindre enn 1 (foran<1), then reinitialize it by front = n - 1, dvs. den siste indeksen til matrisen.
Deque (eller tosidig kø)

Innsetting i bakenden

I denne operasjonen settes elementet inn fra den bakre enden av køen. Før vi implementerer operasjonen, må vi først sjekke på nytt om køen er full eller ikke. Hvis køen ikke er full, kan elementet settes inn fra bakenden ved å bruke betingelsene nedenfor -

vårramme
  • Hvis køen er tom, initialiseres både bak og front med 0. Nå vil begge peke på det første elementet.
  • Ellers øker du baksiden med 1. Hvis den bakre er på siste indeks (eller størrelse - 1), må vi i stedet for å øke den med 1 gjøre den lik 0.
Deque (eller tosidig kø)

Sletting i frontenden

I denne operasjonen slettes elementet fra frontenden av køen. Før vi implementerer operasjonen, må vi først sjekke om køen er tom eller ikke.

Hvis køen er tom, dvs. front = -1, er det underflytbetingelsen, og vi kan ikke utføre slettingen. Hvis køen ikke er full, kan elementet settes inn fra frontenden ved å bruke betingelsene nedenfor -

Hvis dequen bare har ett element, sett bak = -1 og front = -1.

Ellers hvis fronten er på slutten (det betyr at fronten = størrelse - 1), setter du fronten = 0.

størrelsen på python

Ellers øker fronten med 1, (dvs. front = front + 1).

Deque (eller tosidig kø)

Sletting i bakkant

I denne operasjonen slettes elementet fra den bakre enden av køen. Før vi implementerer operasjonen, må vi først sjekke om køen er tom eller ikke.

Hvis køen er tom, dvs. front = -1, er det underflytbetingelsen, og vi kan ikke utføre slettingen.

Hvis dequen bare har ett element, sett bak = -1 og front = -1.

Hvis bak = 0 (bak er foran), sett bak = n - 1.

Ellers reduserer du den bakre med 1 (eller, bak = bak -1).

Deque (eller tosidig kø)

Sjekk tom

Denne operasjonen utføres for å sjekke om dequen er tom eller ikke. Hvis front = -1, betyr det at kartongen er tom.

Sjekk full

Denne operasjonen utføres for å sjekke om dekken er full eller ikke. Hvis front = bak + 1, eller front = 0 og bak = n - 1 betyr det at dequen er full.

Tidskompleksiteten til alle de ovennevnte operasjonene av deksjonen er O(1), dvs. konstant.

Søknader av deque

  • Deque kan brukes som både stabel og kø, da den støtter begge operasjonene.
  • Deque kan brukes som en palindromkontroll betyr at hvis vi leser strengen fra begge ender, vil strengen være den samme.

Gjennomføring av deque

La oss nå se implementeringen av deque i programmeringsspråket C.

klasse vs objekt java 
 #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; }

Produksjon:

Deque (eller tosidig kø)

Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.