Deque-tietorakenne

Tässä opetusohjelmassa opit, mikä on kaksipäinen jono (deque). Löydät myös toimivia esimerkkejä erilaisista toiminnoista dequelle C, C ++, Java ja Python.

Deque tai Double Ended Queue on jonotyyppi, johon elementtien lisääminen ja poistaminen voidaan suorittaa joko edestä tai takaa. Siten se ei noudata FIFO-sääntöä (First In First Out).

Dequen edustus

Deque-tyypit

  • Syöttörajoitettu viive
    Tässä tällöin tulo on rajoitettu yhdestä päästä, mutta sallii poistamisen molemmista päistä.
  • Lähtörajoitettu viive
    Tässä tällöin lähtö on rajoitettu yhdestä päästä, mutta se sallii työnnön molempiin päihin.

Operaatiot Dequella

Alla on dequen pyöreän matriisin toteutus. Pyöreässä taulukossa, jos taulukko on täynnä, aloitamme alusta.

Lineaarisen taulukon toteutuksessa, jos taulukko on täynnä, enempää elementtejä ei voida lisätä. Jos taulukko on täynnä, jokaisessa alla olevassa toiminnossa heitetään "ylivuotoviesti".

Noudata näitä vaiheita ennen seuraavien toimintojen suorittamista.

  1. Ota taulukko (deque), jonka koko on n.
  2. Aseta kaksi osoittinta ensimmäiseen kohtaan ja aseta front = -1ja rear = 0.
Alusta matriisi ja osoittimet dequelle

1. Aseta etuosaan

Tämä toiminto lisää elementin eteen.

  1. Tarkista etuosan sijainti. Tarkista etuosan sijainti
  2. Jos front < 1, alusta uudelleen front = n-1(viimeinen hakemisto). Vaihda eteenpäin loppuun
  3. Muuten vähennä etuosa yhdellä.
  4. Lisää uusi avain 5 array(front). Aseta elementti eteen

2. Aseta takaosaan

Tämä toiminto lisää elementin taakse.

  1. Tarkista, onko taulukko täynnä. Tarkista, onko deque täynnä
  2. Jos deque on täynnä, alusta se uudelleen rear = 0.
  3. Muuten, lisää takaa 1: llä. Lisää takaa
  4. Lisää uusi avain 5 array(rear). Aseta elementti takana

3. Poista edestä

Toiminto poistaa elementin edestä.

  1. Tarkista, onko deque tyhjä. Tarkista, onko deque tyhjä
  2. Jos deque on tyhjä (eli front = -1), poistamista ei voida suorittaa ( alivirtaustila ).
  3. Jos dequessa on vain yksi elementti (eli front = rear), aseta front = -1ja rear = -1.
  4. Muuten, jos etuosa on lopussa (eli front = n - 1), aseta mene eteen front = 0.
  5. Muuten front = front + 1. Lisää etuosa

4. Poista takaosasta

Tämä toiminto poistaa elementin takaa.

  1. Tarkista, onko deque tyhjä. Tarkista, onko deque tyhjä
  2. Jos deque on tyhjä (eli front = -1), poistamista ei voida suorittaa ( alivirtaustila ).
  3. Jos dequessa on vain yksi elementti (eli front = rear), aseta front = -1ja rear = -1noudata seuraavia ohjeita.
  4. Jos takaosa on edessä (eli rear = 0), aseta eteenpäin rear = n - 1.
  5. Muuten rear = rear - 1. Pienennä takaosaa

5. Valitse Tyhjä

Tämä toiminto tarkistaa, onko deque tyhjä. Jos front = -1, deque on tyhjä.

6. Tarkista täynnä

Tämä toiminto tarkistaa, onko deque täynnä. Jos front = 0ja rear = n - 1OR front = rear + 1, deque on täynnä.

Deque-toteutus Pythonissa, Java: ssa, C: ssä ja C ++: ssa

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; )

Ajan monimutkaisuus

Kaikkien yllä mainittujen toimintojen aikakompleksi on vakio eli O(1).

Deque-tietorakenteen sovellukset

  1. Kumoa toimintoja ohjelmisto.
  2. Historin tallentaminen selaimiin.
  3. Sekä pinojen että jonojen toteuttamiseen.

Mielenkiintoisia artikkeleita...