Struktura podatkov Deque

V tej vadnici boste izvedeli, kaj je dvojna vrsta (deque). Prav tako boste našli delovne primere različnih operacij na deque v C, C ++, Java in Python.

Deque ali Double Ended Queue je vrsta čakalne vrste, pri kateri je mogoče vstavljanje in odstranjevanje elementov iz sprednje ali zadnje strani. Tako ne upošteva pravila FIFO (First In First Out).

Zastopanje Deque

Vrste Deque

  • Input Restricted Deque
    V tej deque je vnos omejen na enem koncu, vendar omogoča brisanje na obeh koncih.
  • Izhodna omejena deque
    V tej deque je izhod omejen na enem koncu, vendar omogoča vstavljanje na obeh koncih.

Operacije na Dequeu

Spodaj je izvedba deque v krožnem polju. Če je polje polno, v krožnem polju začnemo od začetka.

Toda v izvedbi linearnega polja, če je polje polno, ni mogoče vstaviti več elementov. Če je matrika polna, se pri vsaki od spodnjih operacij vrže sporočilo »overflow«.

Pred izvajanjem naslednjih postopkov sledite tem korakom.

  1. Vzemi matriko (deque) velikosti n.
  2. Na prvi položaj nastavite dva kazalca in nastavite front = -1in rear = 0.
Inicializirajte matriko in kazalce za deque

1. Vstavite spredaj

Ta operacija doda element spredaj.

  1. Preverite položaj spredaj. Preverite položaj spredaj
  2. Če front < 1, ponovno inicializirajte front = n-1(zadnji indeks). Premaknite spredaj do konca
  3. V nasprotnem primeru spredaj zmanjšajte za 1.
  4. V ključ dodajte novo tipko 5 array(front). Vstavite element spredaj

2. Vstavite zadaj

Ta postopek doda element zadaj.

  1. Preverite, ali je polje polno. Preverite, ali je deque poln
  2. Če je pokrov poln, ga znova inicializirajte rear = 0.
  3. V nasprotnem primeru povečajte zadnji del za 1. Povečajte zadnji del
  4. V ključ dodajte novo tipko 5 array(rear). Vstavite element zadaj

3. Izbriši s sprednje strani

Operacija izbriše element spredaj.

  1. Preverite, ali je prazno mesto prazno. Preverite, ali je deque prazen
  2. Če je deque prazen (tj. front = -1), Brisanja ni mogoče izvesti ( stanje podtoka ).
  3. Če ima deque samo en element (tj. front = rear), Nastavite front = -1in rear = -1.
  4. V nasprotnem primeru, če je spredaj na koncu (tj. front = n - 1), Nastavite gremo spredaj front = 0.
  5. V nasprotnem primeru front = front + 1. Povečajte sprednji del

4. Izbriši z zadnje strani

Ta operacija izbriše element od zadaj.

  1. Preverite, ali je prazno mesto prazno. Preverite, ali je deque prazen
  2. Če je deque prazen (tj. front = -1), Brisanja ni mogoče izvesti ( stanje podtoka ).
  3. Če ima deque samo en element (tj. front = rear), Nastavite front = -1in rear = -1, sicer sledite spodnjim korakom.
  4. Če je zadaj spredaj (tj. rear = 0), Nastavite gremo naprej rear = n - 1.
  5. V nasprotnem primeru rear = rear - 1. Zmanjšajte zadnji del

5. Označite Empty

Ta postopek preveri, ali je deque prazen. Če je front = -1, je deque prazen.

6. Označi Polno

S to operacijo se preveri, ali je deque poln. Če front = 0in rear = n - 1ALI front = rear + 1, je deque poln.

Implementacija Deque v Python, Java, C in 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; )

Zapletenost časa

Časovna zapletenost vseh zgornjih operacij je konstantna tj O(1).

Uporaba strukture podatkov Deque

  1. Pri razveljavitvi operacij s programsko opremo.
  2. Za shranjevanje zgodovine v brskalnikih.
  3. Za izvajanje nizov in čakalnih vrst.

Zanimive Članki...