Deque struktura podataka

U ovom vodiču naučit ćete što je red s dvostrukim završetkom (deque). Također ćete naći radne primjere različitih operacija na dequeu u C, C ++, Java i Python.

Deque ili Double Ended Queue je vrsta reda u kojem se umetanje i uklanjanje elemenata može izvesti sprijeda ili sa stražnje strane. Dakle, ne slijedi FIFO pravilo (First In First Out).

Predstavljanje Dequea

Vrste Dequea

  • Ulaz Ograničeni deque
    U ovom dequeu ulaz je ograničen na jednom kraju, ali omogućuje brisanje na oba kraja.
  • Izlazni ograničeni deque
    U ovom dequeu izlaz je ograničen na jednom kraju, ali omogućuje umetanje na oba kraja.

Operacije na Dequeu

Ispod je implementacija kružnog niza deque. U kružnom nizu, ako je niz pun, započinjemo od početka.

Ali u implementaciji linearnog niza, ako je niz pun, ne mogu se više umetnuti elementi. U svakoj od dolje navedenih operacija, ako je niz pun, baca se "poruka prelijevanja".

Prije izvođenja sljedećih operacija slijede se ovi koraci.

  1. Uzmi niz (deque) veličine n.
  2. Postavite dva pokazivača na prvo mjesto i postavite front = -1i rear = 0.
Inicijalizirajte niz i pokazivače za deque

1. Umetnite sprijeda

Ova operacija dodaje element sprijeda.

  1. Provjerite položaj prednjeg dijela. Provjerite položaj prednjeg dijela
  2. Ako front < 1, ponovno inicijalizirajte front = n-1(zadnji indeks). Pomaknite prednji kraj do kraja
  3. Inače, smanji prednji za 1.
  4. Dodajte novi ključ 5 u array(front). Umetnite element sprijeda

2. Umetnite straga

Ova operacija dodaje element straga.

  1. Provjerite je li niz pun. Provjerite je li deque pun
  2. Ako je kapljica puna, reinicijalizirajte rear = 0.
  3. Inače, povećaj straga za 1. Povećaj straga
  4. Dodajte novi ključ 5 u array(rear). Umetnite element straga

3. Izbriši s prednje strane

Operacija briše element sprijeda.

  1. Provjerite je li deque prazan. Provjerite je li deque prazan
  2. Ako je deque prazan (tj. front = -1), Brisanje se ne može izvršiti ( uvjet podlijevanja ).
  3. Ako deque ima samo jedan element (tj. front = rear), Postavite front = -1i rear = -1.
  4. Inače ako je prednja strana na kraju (tj. front = n - 1), Postavite je prema naprijed front = 0.
  5. Inače, front = front + 1. Povećajte prednji dio

4. Izbriši sa stražnje strane

Ova operacija briše element sa stražnje strane.

  1. Provjerite je li deque prazan. Provjerite je li deque prazan
  2. Ako je deque prazan (tj. front = -1), Brisanje se ne može izvršiti ( uvjet podlijevanja ).
  3. Ako deque ima samo jedan element (tj. front = rear), Postavite front = -1i rear = -1, ostalo slijedite korake u nastavku.
  4. Ako je straga sprijeda (tj. rear = 0), Postavite ga prema naprijed rear = n - 1.
  5. Inače, rear = rear - 1. Smanjite stražnji dio

5. Označite Prazno

Ova operacija provjerava je li deque prazan. Ako je front = -1, deque prazan.

6. Označite Potpuno

Ova operacija provjerava je li deque pun. Ako front = 0i rear = n - 1ILI front = rear + 1, slovo je puno.

Implementacija Dequea u 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; )

Složenost vremena

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

Primjene strukture podataka Deque

  1. U operacijama poništavanja softvera.
  2. Za pohranu povijesti u preglednike.
  3. Za implementaciju i snopova i redova.

Zanimljivi članci...