In dit artikel bespreken we de wachtrij met twee uiteinden of deque. We moeten eerst een korte beschrijving van de wachtrij zien.
Wat is een wachtrij?
Een wachtrij is een datastructuur waarin alles wat het eerst komt als eerste eruit gaat, en het volgt het FIFO-beleid (First-In-First-Out). Het invoegen in de wachtrij gebeurt vanaf het ene uiteinde dat bekend staat als de achtereind of de staart, terwijl de verwijdering plaatsvindt vanaf een ander uiteinde dat bekend staat als de voorkant of de hoofd van de wachtrij.
verilog-parameter
Het praktijkvoorbeeld van een wachtrij is de wachtrij voor kaartjes buiten een bioscoopzaal, waarbij de persoon die als eerste in de rij binnenkomt als eerste het kaartje krijgt en de persoon die als laatste in de rij binnenkomt als laatste het kaartje krijgt.
Wat is een Deque (of wachtrij met twee uiteinden)
De deque staat voor Double Ended Queue. Deque is een lineaire datastructuur waarbij de invoeg- en verwijderbewerkingen vanaf beide kanten worden uitgevoerd. We kunnen zeggen dat deque een algemene versie van de wachtrij is.
Hoewel het invoegen en verwijderen in een deque aan beide kanten kan worden uitgevoerd, volgt het niet de FIFO-regel. De weergave van een deque wordt als volgt gegeven:
Soorten deque
Er zijn twee soorten deque -
- Voer beperkte wachtrij in
- Uitvoer beperkte wachtrij
Invoer beperkte wachtrij
In een wachtrij met beperkte invoer kan de invoegbewerking aan slechts één uiteinde worden uitgevoerd, terwijl het verwijderen vanaf beide uiteinden kan worden uitgevoerd.
Uitvoer beperkte wachtrij
In een wachtrij met beperkte uitvoer kan de verwijderingsbewerking slechts aan één uiteinde worden uitgevoerd, terwijl het invoegen vanaf beide uiteinden kan worden uitgevoerd.
Operaties uitgevoerd op deque
Er zijn de volgende bewerkingen die op een deque kunnen worden toegepast:
- Invoeging aan de voorkant
- Insteek aan achterzijde
- Verwijdering aan de voorkant
- Verwijdering aan de achterzijde
Naast de bovengenoemde werkzaamheden kunnen wij ook kijkoperaties in de deque uitvoeren. Door middel van een kijkoperatie kunnen we de voor- en achterelementen van de deque verkrijgen. Dus naast de bovenstaande bewerkingen worden de volgende bewerkingen ook ondersteund in deque -
Java-parseint
- Haal het voorste item uit de deque
- Haal het achterste item uit de deque
- Controleer of de deque vol is of niet
- Controleert of de deque leeg is of niet
Laten we nu de bewerking op deque begrijpen aan de hand van een voorbeeld.
Invoeging aan de voorzijde
Bij deze bewerking wordt het element ingevoegd vanaf de voorkant van de wachtrij. Voordat we de bewerking uitvoeren, moeten we eerst controleren of de wachtrij vol is of niet. Als de wachtrij niet vol is, kan het element vanaf de voorkant worden ingevoegd met behulp van de onderstaande voorwaarden:
Hoe vind ik verborgen apps op Android
- Als de wachtrij leeg is, worden zowel de achterkant als de voorkant geïnitialiseerd met 0. Nu wijzen beide naar het eerste element.
- Controleer anders de positie van de voorkant als de voorkant kleiner is dan 1 (voorkant<1), then reinitialize it by front = n - 1 , d.w.z. de laatste index van de array.
Invoeging aan de achterzijde
Bij deze bewerking wordt het element vanaf de achterkant van de wachtrij ingevoegd. Voordat we de bewerking uitvoeren, moeten we eerst opnieuw controleren of de wachtrij vol is of niet. Als de wachtrij niet vol is, kan het element vanaf de achterkant worden ingevoegd met behulp van de onderstaande voorwaarden:
- Als de wachtrij leeg is, worden zowel de achterkant als de voorkant geïnitialiseerd met 0. Nu wijzen beide naar het eerste element.
- Anders verhoogt u de achterkant met 1. Als de achterkant de laatste index (of maat - 1) heeft, moeten we deze in plaats van deze met 1 te vergroten, gelijk maken aan 0.
Verwijdering aan de voorkant
Bij deze bewerking wordt het element verwijderd uit de voorkant van de wachtrij. Voordat we de bewerking uitvoeren, moeten we eerst controleren of de wachtrij leeg is of niet.
Als de wachtrij leeg is, d.w.z. voorkant = -1, is er sprake van een onderloopconditie en kunnen we de verwijdering niet uitvoeren. Als de wachtrij niet vol is, kan het element vanaf de voorkant worden ingevoegd met behulp van de onderstaande voorwaarden:
Als de deque slechts één element heeft, stel dan achter = -1 en voorzijde = -1 in.
Anders als de voorkant aan het einde is (dat betekent voorkant = maat - 1), stel dan voorkant = 0 in.
verschil tussen twee snaren Python
Anders kunt u de voorkant met 1 verhogen (dat wil zeggen, voorkant = voorkant + 1).
Verwijdering aan de achterzijde
Bij deze bewerking wordt het element verwijderd uit het achterste uiteinde van de wachtrij. Voordat we de bewerking uitvoeren, moeten we eerst controleren of de wachtrij leeg is of niet.
Als de wachtrij leeg is, d.w.z. voorkant = -1, is er sprake van een onderloopconditie en kunnen we de verwijdering niet uitvoeren.
Als de deque slechts één element heeft, stel dan achter = -1 en voorzijde = -1 in.
Als achter = 0 (achter is voor), stel dan achter = n - 1 in.
Anders verlaagt u de achterkant met 1 (of, achterkant = achterkant -1).
Vink leeg aan
Deze bewerking wordt uitgevoerd om te controleren of de deque leeg is of niet. Als voorkant = -1 betekent dit dat de deque leeg is.
Controleer vol
Deze bewerking wordt uitgevoerd om te controleren of de deque vol is of niet. Als voor = achter + 1, of voor = 0 en achter = n - 1, betekent dit dat de deque vol is.
De tijdscomplexiteit van alle bovengenoemde bewerkingen van de deque is O(1), dat wil zeggen constant.
Toepassingen van deque
- Deque kan zowel als stapel als als wachtrij worden gebruikt, omdat het beide bewerkingen ondersteunt.
- Deque kan worden gebruikt als palindroomcontrole, wat betekent dat als we de string van beide kanten lezen, de string hetzelfde zou zijn.
Implementatie van deque
Laten we nu eens kijken naar de implementatie van deque in de programmeertaal C.
verborgen apps
#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 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (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 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (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('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', 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; } Uitgang:
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.