Deque andmete struktuur

Selles õpetuses saate teada, mis on kahe otsaga järjekord (deque). Samuti leiate toimivaid näiteid D, de, C, C ++, Java ja Pythoni erinevate toimingute kohta.

Deque ehk Double Ended Queue on teatud tüüpi järjekord, milles elementide sisestamise ja eemaldamise saab teostada kas eest või tagant. Seega ei järgi see FIFO reeglit (First In First Out).

Deque'i kujutamine

Deque'i tüübid

  • Sisend on piiratud Deque
    Selles deque's on sisend piiratud ühes otsas, kuid võimaldab kustutamist mõlemast otsast.
  • Väljundi piiratud deque
    Selles deque's on väljund piiratud ühes otsas, kuid võimaldab sisestada mõlemasse otsa.

Operatsioonid Deque'iga

Allpool on toodud deque'i ümmarguse massiivi rakendamine. Kui massiiv on täis, alustame ringmassiivi otsast.

Kuid lineaarse massiivi rakendamisel ei saa massiivi täitmisel enam elemente sisestada. Kui massiiv on täis, visatakse kõigi järgnevate toimingute korral "ülevoolu teade".

Enne järgmiste toimingute tegemist järgitakse neid samme.

  1. Võtke massiiv (deque) suurusega n.
  2. Pange esimesele kohale kaks osutit ja määrake front = -1ja rear = 0.
Initsialiseeri massiiv ja viited deque'ile

1. Sisestage esiküljel

See toiming lisab esiosa elemendi.

  1. Kontrollige esiosa asendit. Kontrollige esiosa asendit
  2. Kui front < 1, lähtestage uuesti front = n-1(viimane register). Nihutage esiosa lõpuni
  3. Muul juhul vähendage esikülge 1 võrra.
  4. Lisage uus võti 5 array(front). Sisestage element eest

2. Sisestage taga

See toiming lisab tagaküljele elemendi.

  1. Kontrollige, kas massiiv on täis. Kontrollige, kas deque on täis
  2. Kui deque on täis, taasalustage rear = 0.
  3. Muul juhul suurendage tagaosa 1 võrra. Suurendage tagumist osa
  4. Lisage uus võti 5 array(rear). Sisestage element taga

3. Kustutage esiküljest

Operatsioon kustutab elemendi eestpoolt.

  1. Kontrollige, kas deque on tühi. Kontrollige, kas deque on tühi
  2. Kui deque on tühi (st front = -1), ei saa kustutamist teostada ( allavoolu tingimus ).
  3. Kui deque'il on ainult üks element (st front = rear), määrake front = -1ja rear = -1.
  4. Muul juhul, kui esikülg on lõpus (st. front = n - 1), Siis minge esiküljele front = 0.
  5. Else, front = front + 1. Suurendage esiosa

4. Kustutage tagant

See toiming kustutab elemendi tagantpoolt.

  1. Kontrollige, kas deque on tühi. Kontrollige, kas deque on tühi
  2. Kui deque on tühi (st front = -1), ei saa kustutamist teostada ( allavoolu tingimus ).
  3. Kui deque'il on ainult üks element (st front = rear), määrake front = -1ja rear = -1, järgige alltoodud samme.
  4. Kui tagumine on ees (st rear = 0), seadke see ette rear = n - 1.
  5. Else, rear = rear - 1. Vähendage tagumist osa

5. Kontrollige Tühi

See toiming kontrollib, kas deque on tühi. Kui front = -1, on deque tühi.

6. Kontrollige täis

Selle toimingu abil kontrollitakse, kas deque on täis. Kui front = 0ja rear = n - 1VÕI front = rear + 1, on deque täis.

Deque juurutamine Pythonis, Java-s, C-s ja C ++ -s

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

Aja keerukus

Kõigi ülaltoodud toimingute ajaline keerukus on konstantne st O(1).

Deque'i andmestruktuuri rakendused

  1. Tarkvara tagasivõtmise toimingutes.
  2. Ajaloo salvestamiseks brauserites.
  3. Nii virnade kui ka järjekordade rakendamise eest.

Huvitavad Artiklid...