„Deque“ duomenų struktūra

Šioje pamokoje sužinosite, kas yra dviguba pabaiga (deque). Taip pat rasite skirtingų operacijų su C, C ++, Java ir Python operacijomis pavyzdžių.

„Deque“ arba „Double Ended Queue“ yra eilės tipas, kai elementus galima įterpti ir pašalinti iš priekio arba iš galo. Taigi jis nesilaiko FIFO taisyklės („First In First Out“).

Deque atstovavimas

Deque rūšys

  • Apribotas įvesties
    įstūmimas Šiame įvestyje įvestis yra ribojama viename gale, tačiau ją galima ištrinti iš abiejų galų.
  • Ribotas išvesties
    deque Šiame išvestyje išvestis yra ribojama viename gale, tačiau leidžia ją įterpti į abu galus.

„Deque“ operacijos

Žemiau pateikiamas apskrito masyvo deque įgyvendinimas. Žiediniame masyve, jei masyvas yra pilnas, mes pradedame nuo pradžių.

Tačiau įgyvendinant linijinį masyvą, jei masyvas yra pilnas, daugiau elementų įterpti negalima. Kiekvienoje iš žemiau nurodytų operacijų, jei masyvas yra pilnas, išmetamas „perpildymo pranešimas“.

Prieš atlikdami šias operacijas, atlikite šiuos veiksmus.

  1. Paimkite n dydžio masyvą (deque).
  2. Pirmoje padėtyje nustatykite du rodykles ir nustatykite front = -1ir rear = 0.
Inicijuokite deque masyvą ir rodykles

1. Įdėkite priekyje

Ši operacija prideda elementą priekyje.

  1. Patikrinkite priekio padėtį. Patikrinkite priekio padėtį
  2. Jei front < 1, iš naujo suaktyvinkite front = n-1(paskutinis indeksas). Perkelkite priekį iki galo
  3. Kitaip, priekį sumažinkite 1.
  4. Įtraukite naują raktą 5 į array(front). Įdėkite elementą į priekį

2. Įdėkite gale

Ši operacija prideda elementą gale.

  1. Patikrinkite, ar masyvas pilnas. Patikrinkite, ar deque yra pilnas
  2. Jei deque yra pilnas, atkurkite iš naujo rear = 0.
  3. Kitaip, padidinkite galą 1. Padidinkite galą
  4. Įtraukite naują raktą 5 į array(rear). Įdėkite elementą gale

3. Ištrinkite iš priekio

Operacija pašalina elementą iš priekio.

  1. Patikrinkite, ar deque tuščias. Patikrinkite, ar deque tuščias
  2. Jei deque yra tuščias (ty front = -1), ištrinti negalima (perpildymo sąlyga ).
  3. Jei deque turi tik vieną elementą (ty front = rear), nustatykite front = -1ir rear = -1.
  4. Kitaip, jei priekis yra gale (ty front = n - 1), nustatykite eikite į priekį front = 0.
  5. Kita front = front + 1,. Padidinkite priekį

4. Ištrinkite iš užpakalinės dalies

Ši operacija pašalina elementą iš galo.

  1. Patikrinkite, ar deque tuščias. Patikrinkite, ar deque tuščias
  2. Jei deque yra tuščias (ty front = -1), ištrinti negalima (perpildymo sąlyga ).
  3. Jei deque turi tik vieną elementą (ty front = rear), nustatykite front = -1ir rear = -1atlikite toliau nurodytus veiksmus.
  4. Jei galas yra priekyje (ty rear = 0), nustatykite eikite į priekį rear = n - 1.
  5. Kita rear = rear - 1,. Sumažinkite galinę dalį

5. Pažymėkite Tuščias

Ši operacija patikrina, ar deque nėra tuščias. Jei front = -1, deque yra tuščias.

6. Patikrinkite, ar pilna

Ši operacija patikrina, ar deque yra pilnas. Jei front = 0ir rear = n - 1OR front = rear + 1, deque yra pilnas.

„Deque“ diegimas „Python“, „Java“, C ir 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; )

Laiko kompleksiškumas

Visų minėtų operacijų laiko sudėtingumas yra pastovus, t O(1).

„Deque“ duomenų struktūros taikymai

  1. Atšaukiant operacijas su programine įranga.
  2. Norėdami išsaugoti istoriją naršyklėse.
  3. Už stekų ir eilių įgyvendinimą.

Įdomios straipsniai...