Deque Data Structure

In questo tutorial imparerai cos'è una coda a doppia estremità (deque). Inoltre, troverai esempi funzionanti di diverse operazioni su una deque in C, C ++, Java e Python.

Deque o Double Ended Queue è un tipo di coda in cui l'inserimento e la rimozione di elementi possono essere eseguiti sia dal davanti che dal retro. Pertanto, non segue la regola FIFO (First In First Out).

Rappresentanza di Deque

Tipi di Deque

  • Input Restricted Deque
    In questo deque, l'input è limitato a una singola estremità ma consente l'eliminazione a entrambe le estremità.
  • Restringimento dell'output
    In questo deque, l'uscita è limitata a una singola estremità ma consente l'inserimento a entrambe le estremità.

Operazioni su un Deque

Di seguito è riportata l'implementazione dell'array circolare di deque. In un array circolare, se l'array è pieno, partiamo dall'inizio.

Ma in un'implementazione di array lineare, se l'array è pieno, non è possibile inserire altri elementi. In ciascuna delle operazioni seguenti, se l'array è pieno, viene generato un "messaggio di overflow".

Prima di eseguire le seguenti operazioni, seguire questi passaggi.

  1. Prendi un array (deque) di dimensione n.
  2. Impostare due puntatori nella prima posizione e impostare front = -1e rear = 0.
Inizializza un array e puntatori per deque

1. Inserire nella parte anteriore

Questa operazione aggiunge un elemento in primo piano.

  1. Verificare la posizione della parte anteriore. Verificare la posizione della parte anteriore
  2. Se front < 1, reinizializza front = n-1(ultimo indice). Spostati in avanti fino alla fine
  3. Altrimenti, diminuire il fronte di 1.
  4. Aggiungi la nuova chiave 5 in array(front). Inserisci l'elemento nella parte anteriore

2. Inserire nella parte posteriore

Questa operazione aggiunge un elemento alla parte posteriore.

  1. Controlla se l'array è pieno. Controlla se il deque è pieno
  2. Se la deque è piena, reinizializza rear = 0.
  3. Altrimenti, aumentare la parte posteriore di 1. Aumentare la parte posteriore
  4. Aggiungi la nuova chiave 5 in array(rear). Inserire l'elemento sul retro

3. Elimina dalla parte anteriore

L'operazione cancella un elemento dal fronte.

  1. Controlla se il deque è vuoto. Controlla se il deque è vuoto
  2. Se il deque è vuoto (cioè front = -1), la cancellazione non può essere eseguita ( condizione di underflow ).
  3. Se il deque ha un solo elemento (cioè front = rear), imposta front = -1e rear = -1.
  4. Altrimenti se il fronte è alla fine (cioè front = n - 1), il set va in primo piano front = 0.
  5. Altrimenti, front = front + 1. Aumenta la parte anteriore

4. Elimina dal retro

Questa operazione cancella un elemento dal retro.

  1. Controlla se il deque è vuoto. Controlla se il deque è vuoto
  2. Se il deque è vuoto (cioè front = -1), la cancellazione non può essere eseguita ( condizione di underflow ).
  3. Se il deque ha un solo elemento (cioè front = rear), imposta front = -1e rear = -1, altrimenti segui i passaggi seguenti.
  4. Se la parte posteriore è nella parte anteriore (cioè rear = 0), impostare vai in avanti rear = n - 1.
  5. Altrimenti, rear = rear - 1. Diminuire la parte posteriore

5. Selezionare Vuoto

Questa operazione controlla se il deque è vuoto. Se front = -1, il deque è vuoto.

6. Seleziona Full

Questa operazione controlla se il deque è pieno. Se front = 0e rear = n - 1OR front = rear + 1, il deque è pieno.

Deque implementazione in Python, Java, C e C ++

Python Java C C ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Complessità temporale

La complessità temporale di tutte le operazioni di cui sopra è costante, ad es O(1).

Applicazioni della struttura dei dati Deque

  1. Nelle operazioni di annullamento sul software.
  2. Per memorizzare la cronologia nei browser.
  3. Per implementare sia gli stack che le code.

Articoli interessanti...