Deque datu struktūra

Šajā apmācībā jūs uzzināsiet, kas ir divkāršā rinda (deque). Jūs atradīsit arī dažādu operāciju piemērus ar deque C, C ++, Java un Python.

Deque jeb Double Ended Queue ir rindas veids, kurā elementu ievietošanu un noņemšanu var veikt no priekšpuses vai aizmugures. Tādējādi tas neievēro FIFO likumu (First In First Out).

Deque attēlojums

Deque veidi

Ierobežots ievades ierobežojums
Šajā deikā ievade ir ierobežota vienā galā, bet ļauj to izdzēst abos galos.
Izejas ierobežojums Deque
Šajā deque, izeja ir ierobežota vienā galā, bet ļauj ievietot abos galos.

Operācijas ar Deque

Zemāk ir riņķveida masīva deque ieviešana. Apļveida masīvā, ja masīvs ir pilns, mēs sākam no sākuma.

Bet lineārā masīva ieviešanā, ja masīvs ir pilns, vairs nevar ievietot elementus. Katrā no tālāk norādītajām darbībām, ja masīvs ir pilns, tiek izmests "pārpildes ziņojums".

Pirms šo darbību veikšanas veic šīs darbības.

Paņemiet masīvu (deque) ar n izmēru.
Iestatiet divus rādītājus pirmajā pozīcijā un iestatiet front = -1un rear = 0.

Inicializējiet masīvu un norādes uz deque

1. Ievietojiet priekšpusē

Šī darbība pievieno elementu priekšā.

Pārbaudiet priekšpuses stāvokli. Pārbaudiet priekšpuses stāvokli
Ja front < 1, atkārtoti inicializējiet front = n-1(pēdējais indekss). Pārslēdziet priekšpusi līdz beigām
Citādi samaziniet priekšpusi par 1.
Pievienojiet jauno taustiņu 5 array(front). Ievietojiet elementu priekšā

2. Ievietojiet aizmugurē

Šī darbība aizmugurē pievieno elementu.

Pārbaudiet, vai masīvs ir pilns. Pārbaudiet, vai deque ir pilns
Ja deque ir pilns, atjaunojiet to no jauna rear = 0.
Citādi palieliniet aizmuguri par 1. Palieliniet aizmuguri
Pievienojiet jauno taustiņu 5 array(rear). Ievietojiet elementu aizmugurē

3. Dzēst no priekšpuses

Darbība izdzēš elementu no priekšpuses.

Pārbaudiet, vai deque nav tukšs. Pārbaudiet, vai deque nav tukšs
Ja deque ir tukšs (ti front = -1), dzēšanu nevar veikt ( nepietiekamas plūsmas nosacījums ).
Ja deque ir tikai viens elements (ti front = rear), iestatiet front = -1un rear = -1.
Citādi, ja priekšpuse ir beigās (ti front = n - 1), iestatiet iet uz priekšu front = 0.
Cits front = front + 1,. Palieliniet priekšpusi

4. Dzēst no aizmugures

Šī darbība izdzēš elementu no aizmugures.

Pārbaudiet, vai deque nav tukšs. Pārbaudiet, vai deque nav tukšs
Ja deque ir tukšs (ti front = -1), dzēšanu nevar veikt ( nepietiekamas plūsmas nosacījums ).
Ja deque ir tikai viens elements (ti front = rear), iestatiet front = -1un rear = -1, veiciet tālāk norādītās darbības.
Ja aizmugure ir priekšā (ti rear = 0), iestatiet pāreju uz priekšu rear = n - 1.
Cits rear = rear - 1,. Samaziniet aizmuguri

5. Pārbaudiet Tukšs

Šī darbība pārbauda, vai deque ir tukšs. Ja front = -1, deque ir tukšs.

6. Pārbaudiet pilnu

Šī darbība pārbauda, vai deque ir pilns. Ja front = 0un rear = n - 1VAI front = rear + 1, deque ir pilns.

Deque ieviešana Python, Java, C un 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; )

Laika sarežģītība

Visu iepriekš minēto darbību sarežģītība ir nemainīga, ti O(1).