Deque Structura datelor

În acest tutorial, veți afla ce este o coadă cu două capete (deque). De asemenea, veți găsi exemple de lucru ale diferitelor operații pe un deque în C, C ++, Java și Python.

Deque sau Double Ended Queue este un tip de coadă în care inserarea și îndepărtarea elementelor pot fi efectuate fie din față, fie din spate. Astfel, nu respectă regula FIFO (First In First Out).

Reprezentarea lui Deque

Tipuri de Deque

  • Deque restricționat de intrare
    În acest deque, intrarea este restricționată la un singur capăt, dar permite ștergerea la ambele capete.
  • Deque Restricted Output
    În acest deque, ieșirea este restricționată la un singur capăt, dar permite inserarea la ambele capete.

Operații pe un Deque

Mai jos este implementarea matricii circulare a deque. Într-o matrice circulară, dacă matricea este plină, începem de la început.

Dar într-o implementare de matrice liniară, dacă matricea este plină, nu mai pot fi inserate mai multe elemente. În fiecare dintre operațiunile de mai jos, dacă matricea este plină, se aruncă „mesaj de depășire”.

Înainte de a efectua următoarele operații, acești pași sunt urmați.

  1. Luați o matrice (deque) de dimensiunea n.
  2. Setați doi indicatori în prima poziție și setați front = -1și rear = 0.
Inițializați o matrice și indicii pentru deque

1. Introduceți în partea din față

Această operație adaugă un element în partea din față.

  1. Verificați poziția frontului. Verificați poziția frontului
  2. Dacă front < 1, reinitializați front = n-1(ultimul index). Mutați fața până la capăt
  3. Altfel, micșorați fața cu 1.
  4. Adăugați noua cheie 5 în array(front). Introduceți elementul în față

2. Introduceți în spate

Această operație adaugă un element în spate.

  1. Verificați dacă matricea este plină. Verificați dacă deque este plin
  2. Dacă deque este plin, reinitializați rear = 0.
  3. Altfel, măriți spatele cu 1. Măriți partea din spate
  4. Adăugați noua cheie 5 în array(rear). Introduceți elementul în spate

3. Ștergeți din partea din față

Operația șterge un element din față.

  1. Verificați dacă deque-ul este gol. Verificați dacă deque este gol
  2. Dacă deque-ul este gol (adică front = -1), ștergerea nu poate fi efectuată ( condiție de scurgere ).
  3. Dacă deque are un singur element (adică front = rear), setați front = -1și rear = -1.
  4. Altfel dacă partea din față este la sfârșit (adică front = n - 1), setați mergi în față front = 0.
  5. Altfel front = front + 1,. Măriți partea din față

4. Ștergeți din spate

Această operație șterge un element din spate.

  1. Verificați dacă deque-ul este gol. Verificați dacă deque este gol
  2. Dacă deque-ul este gol (adică front = -1), ștergerea nu poate fi efectuată ( condiție de scurgere ).
  3. Dacă deque are un singur element (adică front = rear), setați front = -1și rear = -1, altfel urmați pașii de mai jos.
  4. Dacă partea din spate este în față (adică rear = 0), setați mergi în față rear = n - 1.
  5. Altfel rear = rear - 1,. Micșorați partea din spate

5. Verificați Gol

Această operație verifică dacă deque-ul este gol. Dacă front = -1, deque-ul este gol.

6. Verificați complet

Această operație verifică dacă deque-ul este plin. Dacă front = 0și rear = n - 1SAU front = rear + 1, deque este plin.

Implementarea Deque în Python, Java, C și 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; )

Complexitatea timpului

Complexitatea în timp a tuturor operațiunilor de mai sus este constantă, adică O(1).

Aplicații ale structurii de date Deque

  1. În operațiile de anulare a software-ului.
  2. Pentru a stoca istoricul în browsere.
  3. Pentru implementarea ambelor stive și cozi.

Articole interesante...