Šajā rakstā mēs apspriedīsim dubulto rindu vai deque. Vispirms mums vajadzētu redzēt īsu rindas aprakstu.
Kas ir rinda?
Rinda ir datu struktūra, kurā vispirms tiks izvadīts pirmais, un tā atbilst FIFO (First-In-First-Out) politikai. Ievietošana rindā tiek veikta no viena gala, kas pazīstams kā aizmugures gals vai aste, tā kā dzēšana tiek veikta no cita gala, kas pazīstams kā priekšgals vai galvu no rindas.
java metodes
Reālais rindas piemērs ir biļešu rinda ārpus kinozāles, kur persona, kas rindā ieiet pirmais, saņem biļeti pirmais, un persona, kas rindā ieiet pēdējā, saņem biļeti beidzot.
Kas ir deque (vai dubultā rinda)
Deque apzīmē Double Ended Queue. Deque ir lineāra datu struktūra, kurā ievietošanas un dzēšanas darbības tiek veiktas no abiem galiem. Var teikt, ka deque ir vispārināta rindas versija.
Lai gan ievietošanu un dzēšanu dekvē var veikt abos galos, tas neatbilst FIFO noteikumam. Dekas attēlojums ir sniegts šādi -
Deque veidi
Ir divu veidu deque -
- Ievades ierobežota rinda
- Izvades ierobežota rinda
Ievades ierobežota rinda
Ierobežotā ievades rindā ievietošanas darbību var veikt tikai vienā galā, savukārt dzēšanu var veikt no abiem galiem.
Izvades ierobežota rinda
Ierobežotā izvades rindā dzēšanas darbību var veikt tikai vienā galā, savukārt ievietošanu var veikt no abiem galiem.
Operācijas, kas veiktas uz deque
Dekvē var izmantot šādas darbības:
- Ievietojums priekšpusē
- Ievietošana aizmugurē
- Priekšpusē svītrojums
- Dzēšana aizmugurē
Mēs varam arī veikt ielūkošanās darbības deque kopā ar iepriekš minētajām darbībām. Izmantojot peek operāciju, mēs varam iegūt dekas priekšējos un aizmugurējos elementus. Tātad, papildus iepriekš minētajām darbībām, tiek atbalstītas arī šādas darbības:
git pievienot visu
- Iegūstiet priekšējo priekšmetu no dekas
- Iegūstiet aizmugurējo priekšmetu no dekas
- Pārbaudiet, vai deka ir pilna vai nē
- Pārbauda, vai deka ir tukša vai nav
Tagad, izmantojot piemēru, sapratīsim ar deque veikto darbību.
Ievietošana priekšpusē
Šajā darbībā elements tiek ievietots no rindas priekšpuses. Pirms operācijas ieviešanas mums vispirms ir jāpārbauda, vai rinda ir pilna vai nē. Ja rinda nav pilna, elementu var ievietot no priekšpuses, izmantojot tālāk norādītos nosacījumus -
- Ja rinda ir tukša, gan aizmugurē, gan priekšpuse tiek inicializēta ar 0. Tagad abi norādīs uz pirmo elementu.
- Pretējā gadījumā pārbaudiet priekšpuses pozīciju, ja priekšpuse ir mazāka par 1 (priekšpuse<1), then reinitialize it by front = n - 1, t.i., pēdējais masīva indekss.
Ievietošana aizmugurē
setinterval javascript
Šajā darbībā elements tiek ievietots no rindas aizmugures. Pirms operācijas ieviešanas mums vispirms vēlreiz jāpārbauda, vai rinda ir pilna vai nē. Ja rinda nav pilna, tad elementu var ievietot no aizmugures, izmantojot tālāk norādītos nosacījumus -
- Ja rinda ir tukša, gan aizmugurē, gan priekšpuse tiek inicializēta ar 0. Tagad abi norādīs uz pirmo elementu.
- Pretējā gadījumā palieliniet aizmuguri par 1. Ja aizmugurē ir pēdējais rādītājs (vai izmērs - 1), tad tā vietā, lai palielinātu to par 1, mums tas ir jāpadara vienāds ar 0.
Dzēšana priekšpusē
Šajā darbībā elements tiek dzēsts no rindas priekšpuses. Pirms operācijas ieviešanas mums vispirms ir jāpārbauda, vai rinda ir tukša.
Ja rinda ir tukša, t.i., front = -1, tas ir nepietiekamas plūsmas nosacījums, un mēs nevaram veikt dzēšanu. Ja rinda nav pilna, elementu var ievietot no priekšpuses, izmantojot tālāk norādītos nosacījumus -
Ja deque ir tikai viens elements, iestatiet aizmuguri = -1 un priekšējo = -1.
Ja priekšpuse ir galā (tas nozīmē, ka priekšpuse = izmērs - 1), iestatiet priekšpusi = 0.
kad iznāca Windows 7
Citādi palieliniet priekšpusi par 1 (t.i., priekšpuse = priekšpuse + 1).
Dzēšana aizmugurē
Šajā darbībā elements tiek dzēsts no rindas aizmugures. Pirms operācijas ieviešanas mums vispirms ir jāpārbauda, vai rinda ir tukša.
Ja rinda ir tukša, t.i., front = -1, tas ir nepietiekamas plūsmas nosacījums, un mēs nevaram veikt dzēšanu.
Ja deque ir tikai viens elements, iestatiet aizmuguri = -1 un front = -1.
Ja aizmugurē = 0 (aizmugure ir priekšā), tad iestatiet aizmugurē = n - 1.
Pretējā gadījumā samaziniet aizmuguri par 1 (vai aizmugure = aizmugure -1).
Pārbaudiet tukšu
Šī darbība tiek veikta, lai pārbaudītu, vai deque ir tukša vai nav. Ja front = -1, tas nozīmē, ka deque ir tukšs.
Pārbaudiet pilnu
Šī darbība tiek veikta, lai pārbaudītu, vai deque ir pilna vai nav. Ja priekšā = aizmugure + 1 vai priekšā = 0 un aizmugurē = n - 1, tas nozīmē, ka deque ir pilna.
Visu iepriekšminēto deque operāciju laika sarežģītība ir O(1), t.i., nemainīga.
Deque pielietojumi
- Deque var izmantot gan kā steku, gan rindu, jo tā atbalsta abas darbības.
- Deque var izmantot kā palindromu pārbaudītāju, kas nozīmē, ka, ja mēs nolasītu virkni no abiem galiem, virkne būtu vienāda.
Deque īstenošana
Tagad apskatīsim deque ieviešanu C programmēšanas valodā.
kā pārvērst char par virkni
#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; } Izvade:
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.