Deque dátová štruktúra

V tomto tutoriále sa dozviete, čo je to dvojitý koniec frontu (deque). Nájdete tiež pracovné príklady rôznych operácií na deque v jazykoch C, C ++, Java a Python.

Fronta Deque alebo Double Ended Queue je typ fronty, do ktorej je možné vkladanie a vyberanie prvkov vykonávať spredu alebo zozadu. Nesleduje teda pravidlo FIFO (prvý dovnútra prvý von).

Zastúpenie spoločnosti Deque

Druhy Deque


  • Deque Restricted Deque V tomto deque je vstup obmedzený na jednom konci, ale umožňuje vymazanie na oboch koncoch.
  • Obmedzený výstupný výstup
    V tomto výstupnom režime je výstup obmedzený na jednom konci, ale umožňuje vloženie na oba konce.

Operácie na deke

Nižšie je uvedená implementácia kruhového poľa deque. V kruhovom poli, ak je pole plné, začíname od začiatku.

Ale pri implementácii lineárneho poľa, ak je pole plné, nemožno vložiť ďalšie prvky. Ak je pole plné, pri každej z operácií uvedených nižšie sa vloží „správa o pretečení“.

Pred vykonaním nasledujúcich operácií je potrebné vykonať tieto kroky.

  1. Vezmite pole (deque) veľkosti n.
  2. Nastavte dva ukazovatele na prvú pozíciu a nastavte front = -1a rear = 0.
Inicializujte pole a ukazovatele pre deque

1. Vložte do prednej časti

Táto operácia pridáva prvok spredu.

  1. Skontrolujte polohu spredu. Skontrolujte polohu spredu
  2. Ak front < 1, znova inicializovať front = n-1(posledný index). Posuňte predok na koniec
  3. Inak, znížte predok o 1.
  4. Pridajte nový kľúč 5 do array(front). Vložte prvok spredu

2. Vložte dozadu

Táto operácia pridáva prvok dozadu.

  1. Skontrolujte, či je pole plné. Skontrolujte, či je deque plný
  2. Ak je zariadenie plné, znova ho inicializujte rear = 0.
  3. Inak zväčšite zadnú časť o 1. Zväčšite zadnú časť
  4. Pridajte nový kľúč 5 do array(rear). Vložte prvok zozadu

3. Vymazať spredu

Táto operácia vymaže prvok spredu.

  1. Skontrolujte, či je štít prázdny. Skontrolujte, či je deque prázdny
  2. Ak je deque prázdny (tj. front = -1), Nemožno ho vymazať ( podmienka podtečenia ).
  3. Ak má deque iba jeden prvok (tj. front = rear), Nastavte front = -1a rear = -1.
  4. Pokiaľ nie je koniec na konci (tj. front = n - 1), Choďte na front front = 0.
  5. Inak front = front + 1. Zväčšite predok

4. Vymažte zozadu

Táto operácia vymaže prvok zozadu.

  1. Skontrolujte, či je štít prázdny. Skontrolujte, či je deque prázdny
  2. Ak je deque prázdny (tj. front = -1), Nemožno ho vymazať ( podmienka podtečenia ).
  3. Ak má deque iba jeden prvok (tj. front = rear), Nastavte front = -1a rear = -1, inak postupujte podľa krokov uvedených nižšie.
  4. Ak je zadná časť vpredu (tj. rear = 0), Nastavte chod dopredu rear = n - 1.
  5. Inak rear = rear - 1. Znížte zadnú časť

5. Začiarknite políčko Prázdne

Táto operácia skontroluje, či je deque prázdny. Ak je front = -1, archív je prázdny.

6. Začiarknite políčko Plné

Táto operácia skontroluje, či je deque plný. Ak front = 0a rear = n - 1ALEBO front = rear + 1je deque plný.

Deque Implementácia v Python, Java, C a 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; )

Časová zložitosť

Časová zložitosť všetkých vyššie uvedených operácií je konštantná, tj O(1).

Aplikácie deque dátovej štruktúry

  1. Pri zrušení operácií so softvérom.
  2. Na ukladanie histórie do prehliadačov.
  3. Na implementáciu zásobníkov aj front.

Zaujímavé články...