logo

TechCodeview

Deque (ili dvostruki red čekanja)

U ovom ćemo članku raspravljati o dvostrukom redu čekanja ili dequeu. Prvo bismo trebali vidjeti kratak opis reda čekanja.

Što je red čekanja?

Red čekanja je struktura podataka u kojoj sve što prvo dođe prvo će izaći i slijedi FIFO (First-In-First-Out) politiku. Umetanje u red čekanja vrši se s jednog kraja poznatog kao stražnji kraj ili rep, dok se brisanje vrši s drugog kraja poznatog kao prednji kraj ili glava reda čekanja.

kada počinje q2

Primjer reda iz stvarnog svijeta je red za ulaznice ispred kino dvorane, gdje osoba koja uđe prva u redu prva dobiva kartu, a osoba koja ulazi posljednja u redu dobiva kartu na kraju.

Što je Deque (ili dvostruki red čekanja)

Deque je kratica za Double Ended Queue. Deque je linearna struktura podataka gdje se operacije umetanja i brisanja izvode s oba kraja. Možemo reći da je deque generalizirana verzija reda čekanja.

Iako se umetanje i brisanje u dequeu može izvesti na oba kraja, to ne slijedi FIFO pravilo. Prikaz deque-a dan je na sljedeći način -

Deque (ili dvostruki red čekanja)

Vrste deque

Postoje dvije vrste dequea -

  • Red čekanja ograničenog unosa
  • Red čekanja s ograničenim izlazom

Red čekanja s ograničenim unosom

U redu čekanja s ograničenim ulazom, operacija umetanja može se izvesti samo na jednom kraju, dok se brisanje može izvesti s oba kraja.

Deque (ili dvostruki red čekanja)

Red čekanja s ograničenim izlazom

U redu čekanja s ograničenim izlazom, operacija brisanja može se izvesti samo na jednom kraju, dok se umetanje može izvesti s oba kraja.

Deque (ili dvostruki red čekanja)

Operacije koje se izvode na deque

Postoje sljedeće operacije koje se mogu primijeniti na deque -

  • Umetak sprijeda
  • Umetanje straga
  • Brisanje sprijeda
  • Brisanje na stražnjoj strani

Također možemo izvesti peek operacije u deque zajedno s gore navedenim operacijama. Operacijom zavirivanja možemo dobiti prednje i stražnje elemente dequea. Dakle, uz gore navedene operacije, sljedeće operacije također su podržane u dequeu -

baci u sql
  • Uzmite prednju stavku iz dequea
  • Uzmi stražnji predmet iz dequea
  • Provjerite je li deque pun ili ne
  • Provjerava je li deque prazan ili ne

Razmotrimo sada operaciju koja se izvodi na deque koristeći primjer.

Umetak na prednjem kraju

U ovoj operaciji element se umeće s prednjeg kraja reda čekanja. Prije implementacije operacije prvo moramo provjeriti je li red čekanja pun ili ne. Ako red čekanja nije pun, tada se element može umetnuti s prednjeg kraja korištenjem donjih uvjeta -

  • Ako je red čekanja prazan, i stražnji i prednji dio se inicijaliziraju s 0. Sada će oba pokazivati ​​na prvi element.
  • Inače, provjerite položaj prednje strane ako je prednja strana manja od 1 (prednja<1), then reinitialize it by front = n - 1, tj. posljednji indeks niza.
Deque (ili dvostruki red čekanja)

Umetak na stražnjem kraju

U ovoj operaciji element se umeće sa stražnjeg kraja reda čekanja. Prije provedbe operacije prvo moramo ponovno provjeriti je li red pun ili ne. Ako red čekanja nije pun, tada se element može umetnuti sa stražnje strane korištenjem donjih uvjeta -

  • Ako je red prazan, i stražnji i prednji dio se inicijaliziraju s 0. Sada će oba pokazivati ​​na prvi element.
  • U suprotnom, povećajte stražnji dio za 1. Ako stražnji dio ima zadnji indeks (ili veličinu - 1), tada umjesto povećanja za 1, moramo ga postaviti jednakim 0.
Deque (ili dvostruki red čekanja)

Brisanje na prednjem kraju

U ovoj operaciji, element se briše s prednjeg kraja reda čekanja. Prije implementacije operacije prvo moramo provjeriti je li red čekanja prazan ili ne.

pronađi moj iphone s androida

Ako je red čekanja prazan, tj. front = -1, to je uvjet underflowa i ne možemo izvršiti brisanje. Ako red čekanja nije pun, tada se element može umetnuti s prednjeg kraja korištenjem donjih uvjeta -

Ako deque ima samo jedan element, postavite stražnji = -1 i prednji = -1.

Inače, ako je prednja strana na kraju (to znači prednja strana = veličina - 1), postavite prednju stranu = 0.

primitivni tipovi podataka u Javi

Inače povećajte prednji dio za 1, (tj. prednji dio = prednji dio + 1).

Deque (ili dvostruki red čekanja)

Brisanje na stražnjem kraju

U ovoj operaciji, element se briše sa stražnjeg kraja reda čekanja. Prije implementacije operacije prvo moramo provjeriti je li red čekanja prazan ili ne.

Ako je red čekanja prazan, tj. front = -1, to je uvjet underflowa i ne možemo izvršiti brisanje.

Ako deque ima samo jedan element, postavite stražnji = -1 i prednji = -1.

Ako je stražnji = 0 (stražnji je sprijeda), tada postavite stražnji = n - 1.

Inače, smanjite stražnji dio za 1 (ili stražnji = stražnji -1).

Deque (ili dvostruki red čekanja)

Ček prazan

Ova se operacija izvodi kako bi se provjerilo je li deque prazan ili ne. Ako je front = -1, to znači da je deque prazan.

Provjerite puni

Ova se operacija izvodi kako bi se provjerilo je li deque pun ili ne. Ako je prednji = stražnji + 1, ili prednji = 0 i stražnji = n - 1, to znači da je deque pun.

Vremenska složenost svih gore navedenih operacija deque je O(1), tj. konstantna.

Primjene deque

  • Deque se može koristiti i kao stog i kao red čekanja jer podržava obje operacije.
  • Deque se može koristiti kao palindrom za provjeru znači da ako čitamo niz s oba kraja, niz će biti isti.

Implementacija deque

Sada, da vidimo implementaciju deque u C programskom jeziku.

koliko gradova SAD 
 #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; }

Izlaz:

Deque (ili dvostruki red čekanja)

Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.