logo

TechCodeview

Deque (vagy kétvégű sor)

Ebben a cikkben a kétvégű sorról vagy deque-ről lesz szó. Először egy rövid leírást kell látnunk a sorról.

Mi az a sor?

A várólista egy olyan adatstruktúra, amelyben ami előbb következik, az előbb kimegy, és a FIFO (First-In-First-Out) házirendet követi. A beszúrás a sorba az egyik végétől, a hátsó vége vagy a farok, míg a törlés egy másik végről történik, amely a elülső vége vagy a fej a sorból.

java dátum a karakterlánchoz

A sorban állás valós példája a mozitermen kívüli jegysor, ahol a sorban elsőként belépő kapja meg először a jegyet, és aki utolsóként lép be a sorban, az kapja meg végül a jegyet.

Mi az a deque (vagy kétvégű sor)

A deque a Double Ended Queue rövidítése. A Deque egy lineáris adatstruktúra, amelyben a beillesztési és törlési műveletek mindkét végéről történnek. Azt mondhatjuk, hogy a deque a sor általánosított változata.

Bár a beillesztés és a törlés a deque-ben mindkét oldalon végrehajtható, nem követi a FIFO szabályt. A deque ábrázolása a következő:

Deque (vagy kétvégű sor)

A deque típusai

Kétféle deque létezik -

  • Korlátozott beviteli sor
  • Korlátozott kimeneti sor

Korlátozott beviteli sor

A korlátozott beviteli sorban a beillesztés csak az egyik végén, míg a törlés mindkét végén végrehajtható.

Deque (vagy kétvégű sor)

Kimenet korlátozott sor

A korlátozott kimeneti sorban a törlési művelet csak az egyik végén, míg a beillesztés mindkét végén végrehajtható.

Deque (vagy kétvégű sor)

Deque-n végrehajtott műveletek

A következő műveletek alkalmazhatók a deque-n:

  • Beillesztés elöl
  • Beillesztés hátul
  • Elöl törlés
  • Törlés hátul

A deque-ben a fent felsorolt ​​műveletek mellett betekintési műveleteket is végezhetünk. Peek művelettel megkapjuk a deque elülső és hátsó elemeit. Tehát a fenti műveleteken kívül a következő műveletek is támogatottak deque-ben:

c# oktatóanyag
  • Szerezd meg az első elemet a deque-ből
  • Szerezd meg a hátsó elemet a deque-ből
  • Ellenőrizze, hogy a deque megtelt-e vagy sem
  • Ellenőrzi, hogy a deque üres-e vagy sem

Most értsük meg a deque műveletet egy példa segítségével.

Beillesztés az elülső végén

Ebben a műveletben az elemet a sor elülső végéről illeszti be. A művelet végrehajtása előtt először ellenőriznünk kell, hogy a sor megtelt-e vagy sem. Ha a sor nem tele, akkor az elemet az alábbi feltételekkel lehet beszúrni a kezelőfelületről:

  • Ha a sor üres, a hátsó és az elülső rész is 0-val inicializálódik. Most mindkettő az első elemre mutat.
  • Ellenkező esetben ellenőrizze az elülső rész helyzetét, ha az eleje kisebb, mint 1 (elülső<1), then reinitialize it by front = n - 1, azaz a tömb utolsó indexe.
Deque (vagy kétvégű sor)

Beillesztés a hátsó végén

Ebben a műveletben az elem a sor hátsó végéről kerül beillesztésre. A művelet végrehajtása előtt először újra meg kell vizsgálnunk, hogy a sor megtelt-e vagy sem. Ha a sor nem tele, akkor az elem beszúrható hátulról az alábbi feltételekkel:

  • Ha a sor üres, a hátsó és az elülső rész is 0-val inicializálódik. Most mindkettő az első elemre mutat.
  • Ellenkező esetben növelje a hátulsót 1-gyel. Ha a hátsó rész utolsó indexe (vagy mérete - 1), akkor ahelyett, hogy 1-gyel növelnénk, 0-val kell egyenlővé tenni.
Deque (vagy kétvégű sor)

Törlés az elején

Ebben a műveletben az elem törlődik a sor elejéről. A művelet végrehajtása előtt először ellenőriznünk kell, hogy a sor üres-e vagy sem.

Ha a sor üres, azaz front = -1, akkor ez az alulcsordulás feltétele, és nem tudjuk végrehajtani a törlést. Ha a sor nem tele, akkor az elemet az alábbi feltételekkel lehet beszúrni a kezelőfelületről:

Ha a deque csak egy elemet tartalmaz, állítsa be a hátsó = -1 és front = -1 értéket.

latex lista

Ellenkező esetben, ha az eleje a végén van (ez azt jelenti, hogy eleje = méret - 1), állítsa be az elejét = 0.

python maradék operátor

Ellenkező esetben növelje az elejét 1-gyel (azaz front = front + 1).

Deque (vagy kétvégű sor)

Törlés a hátsó végén

Ebben a műveletben az elem törlődik a sor hátsó végéről. A művelet végrehajtása előtt először ellenőriznünk kell, hogy a sor üres-e vagy sem.

Ha a sor üres, azaz front = -1, akkor ez az alulcsordulás feltétele, és nem tudjuk végrehajtani a törlést.

Ha a deque csak egy elemet tartalmaz, állítsa be a hátsó = -1 és front = -1 értéket.

Ha hátul = 0 (hátsó elöl van), akkor állítsa hátul = n - 1.

Ellenkező esetben csökkentse a hátsót 1-gyel (vagy hátul = hátsó -1).

Deque (vagy kétvégű sor)

Üres ellenőrzés

Ez a művelet annak ellenőrzésére szolgál, hogy a deque üres-e vagy sem. Ha front = -1, az azt jelenti, hogy a deque üres.

Ellenőrizze tele

Ez a művelet annak ellenőrzésére szolgál, hogy a deque megtelt-e vagy sem. Ha elöl = hátul + 1, vagy elöl = 0 és hátul = n - 1, az azt jelenti, hogy a deque megtelt.

A deque összes fenti műveletének időbonyolultsága O(1), azaz állandó.

A deque alkalmazásai

  • A Deque veremként és sorként is használható, mivel mindkét műveletet támogatja.
  • A Deque palindrom ellenőrzőként használható azt jelenti, hogy ha a karakterláncot mindkét végéről olvassuk, akkor a karakterlánc ugyanaz lenne.

Deque megvalósítása

Most pedig lássuk a deque megvalósítását C programozási nyelven.

hogyan kell használni a mysql munkapadot 
 #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; }

Kimenet:

Deque (vagy kétvégű sor)

Szóval ennyi a cikkről. Remélem, a cikk hasznos és informatív lesz az Ön számára.