logo

TechCodeview

Deque (o cua de doble final)

En aquest article, parlarem de la cua o deque de doble extrem. Primer hauríem de veure una breu descripció de la cua.

Què és una cua?

Una cua és una estructura de dades en la qual el que vingui primer sortirà primer i segueix la política FIFO (First-In-First-Out). La inserció a la cua es fa des d'un extrem conegut com a extrem posterior o el cua, mentre que l'eliminació es fa des d'un altre extrem conegut com a frontal o el cap de la cua.

L'actor Rekha

L'exemple real d'una cua és la cua d'entrades a l'exterior d'una sala de cinema, on la persona que entra primer a la cua rep l'entrada primer i la persona que entra l'última a la cua l'obté finalment.

Què és un Deque (o cua de doble final)

El deque significa cua de doble final. Deque és una estructura de dades lineal on les operacions d'inserció i supressió es realitzen des dels dos extrems. Podem dir que deque és una versió generalitzada de la cua.

Tot i que la inserció i l'eliminació d'un deque es poden realitzar als dos extrems, no segueix la regla FIFO. La representació d'un deque es dóna de la següent manera:

Deque (o cua de doble final)

Tipus de deque

Hi ha dos tipus de deque -

  • Cua restringida d'entrada
  • Sortida cua restringida

Cua restringida d'entrada

A la cua restringida d'entrada, l'operació d'inserció només es pot realitzar en un extrem, mentre que la supressió es pot realitzar des dels dos extrems.

Deque (o cua de doble final)

Cua de sortida restringida

A la cua restringida de sortida, l'operació d'eliminació només es pot realitzar en un extrem, mentre que la inserció es pot realitzar des dels dos extrems.

Deque (o cua de doble final)

Operacions realitzades en deque

Hi ha les següents operacions que es poden aplicar en un deque:

  • Inserció al davant
  • Inserció a la part posterior
  • Eliminació al davant
  • Eliminació a la part posterior

També podem realitzar operacions de peek al deque juntament amb les operacions enumerades anteriorment. Mitjançant l'operació d'ull, podem obtenir els elements frontals i posteriors del deque. Per tant, a més de les operacions anteriors, també s'admeten les operacions següents a deque -

descomprimir a linux
  • Aconsegueix l'element frontal del deque
  • Aconsegueix l'element posterior del deque
  • Comproveu si el deque està ple o no
  • Comprova si el deque està buit o no

Ara, anem a entendre l'operació realitzada a deque utilitzant un exemple.

Inserció a la part davantera

En aquesta operació, l'element s'insereix des de la part frontal de la cua. Abans d'implementar l'operació, primer hem de comprovar si la cua està plena o no. Si la cua no està plena, l'element es pot inserir des de la part frontal utilitzant les condicions següents:

  • Si la cua està buida, tant la part posterior com la davantera s'inicialitzen amb 0. Ara, totes dues apuntaran al primer element.
  • En cas contrari, comproveu la posició del davant si el davant és inferior a 1 (front<1), then reinitialize it by front = n - 1, és a dir, l'últim índex de la matriu.
Deque (o cua de doble final)

Inserció a l'extrem posterior

En aquesta operació, l'element s'insereix des de la part posterior de la cua. Abans d'implementar l'operació, primer hem de tornar a comprovar si la cua està plena o no. Si la cua no està plena, l'element es pot inserir des de la part posterior utilitzant les condicions següents:

  • Si la cua està buida, tant la part posterior com la davantera s'inicialitzen amb 0. Ara, totes dues apuntaran al primer element.
  • En cas contrari, incrementeu la part posterior en 1. Si la part posterior té l'últim índex (o la mida - 1), aleshores, en lloc d'augmentar-la en 1, haurem de fer-la igual a 0.
Deque (o cua de doble final)

Supressió a la part frontal

En aquesta operació, l'element s'elimina de la part frontal de la cua. Abans d'implementar l'operació, primer hem de comprovar si la cua està buida o no.

tipus de dades seqüeles

Si la cua està buida, és a dir, front = -1, és la condició de desbordament inferior i no podem realitzar la supressió. Si la cua no està plena, l'element es pot inserir des de la part frontal utilitzant les condicions següents:

Si el deque només té un element, establiu el darrere = -1 i el davant = -1.

En cas contrari, si la part davantera està al final (és a dir, davant = mida - 1), poseu davant = 0.

programes d'exemple java

En cas contrari, incrementeu la part davantera en 1, (és a dir, davant = davant + 1).

Deque (o cua de doble final)

Eliminació a la part posterior

En aquesta operació, l'element s'elimina de la part posterior de la cua. Abans d'implementar l'operació, primer hem de comprovar si la cua està buida o no.

Si la cua està buida, és a dir, front = -1, és la condició de desbordament inferior i no podem realitzar la supressió.

Si el deque només té un element, establiu el darrere = -1 i el davant = -1.

Si la part posterior = 0 (la part posterior està al davant), establiu la part posterior = n - 1.

En cas contrari, disminueix la part posterior en 1 (o, darrere = darrere -1).

Deque (o cua de doble final)

Comprovar buit

Aquesta operació es realitza per comprovar si el deque està buit o no. Si front = -1, vol dir que el deque està buit.

Comprova complet

Aquesta operació es realitza per comprovar si el deque està ple o no. Si davant = darrere + 1, o davant = 0 i darrere = n - 1 vol dir que el deque està ple.

La complexitat temporal de totes les operacions anteriors del deque és O(1), és a dir, constant.

Aplicacions de deque

  • Deque es pot utilitzar tant com a pila com com a cua, ja que admet ambdues operacions.
  • Deque es pot utilitzar com a verificador de palíndrom significa que si llegim la cadena des dels dos extrems, la cadena seria la mateixa.

Implementació de deque

Ara, anem a veure la implementació de deque en llenguatge de programació C.

programa de matriu bidimensional en c 
 #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; }

Sortida:

Deque (o cua de doble final)

Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.