W tym artykule omówimy kolejkę dwustronną lub deque. Najpierw powinniśmy zobaczyć krótki opis kolejki.
Co to jest kolejka?
Kolejka to struktura danych, w której wszystko, co pojawi się jako pierwsze, wyjdzie jako pierwsze, zgodnie z polityką FIFO (pierwszy na wejściu, pierwszy na wyjściu). Wstawienie do kolejki odbywa się z jednego końca, tzw tył albo ogon, podczas gdy usuwanie odbywa się z innego końca, znanego jako przód albo głowa z kolejki.
operator Pythona //
Prawdziwym przykładem kolejki jest kolejka po bilety przed salą kinową, gdzie osoba wchodząca do kolejki jako pierwsza otrzymuje bilet, a osoba wchodząca w kolejce jako ostatnia otrzymuje bilet na końcu.
Co to jest Deque (lub kolejka dwustronna)
Deque oznacza kolejkę z podwójnym zakończeniem. Deque to liniowa struktura danych, w której operacje wstawiania i usuwania są wykonywane z obu końców. Można powiedzieć, że deque jest uogólnioną wersją kolejki.
Chociaż wstawianie i usuwanie w deque można wykonać na obu końcach, nie jest to zgodne z zasadą FIFO. Reprezentacja deque jest podana w następujący sposób -
Rodzaje deque
Istnieją dwa rodzaje deque -
- Kolejka z ograniczeniami wejściowymi
- Kolejka z ograniczeniami wyjściowymi
Kolejka z ograniczeniami wejściowymi
W kolejce z ograniczeniami wejściowymi operację wstawiania można wykonać tylko na jednym końcu, natomiast usuwanie można wykonać na obu końcach.
Kolejka z ograniczeniami wyjściowymi
W kolejce z ograniczeniami wyjściowymi operację usuwania można wykonać tylko na jednym końcu, natomiast wstawianie można wykonać na obu końcach.
Operacje wykonywane na deque
Na deque można zastosować następujące operacje:
- Wstawka z przodu
- Wstawka z tyłu
- Usunięcie z przodu
- Usunięcie z tyłu
Oprócz operacji wymienionych powyżej możemy również wykonywać operacje podglądu w deque. Dzięki operacji podglądu możemy uzyskać przednie i tylne elementy deque. Zatem oprócz powyższych operacji w deque obsługiwane są również następujące operacje -
przełącz Javę
- Zdobądź przedni przedmiot z deque
- Zdobądź tylny przedmiot z deque
- Sprawdź, czy deque jest pełny, czy nie
- Sprawdza, czy deque jest pusta, czy nie
Teraz przyjrzyjmy się operacji wykonywanej na deque na przykładzie.
Wkładanie z przodu
W tej operacji element jest wstawiany z początku kolejki. Przed wykonaniem operacji musimy najpierw sprawdzić, czy kolejka jest pełna, czy nie. Jeśli kolejka nie jest pełna, element można wstawić od frontu, korzystając z poniższych warunków -
algebra zbiorów
- Jeśli kolejka jest pusta, zarówno tył, jak i przód są inicjowane wartością 0. Teraz oba będą wskazywać na pierwszy element.
- W przeciwnym razie sprawdź położenie przodu, jeśli przód jest mniejszy niż 1 (front<1), then reinitialize it by front = n - 1 , tj. ostatni indeks tablicy.
Wkładanie z tyłu
W tej operacji element wstawiany jest z końca kolejki. Przed wykonaniem operacji musimy najpierw ponownie sprawdzić, czy kolejka jest pełna, czy nie. Jeśli kolejka nie jest pełna, element można wstawić od tyłu, korzystając z poniższych warunków -
- Jeśli kolejka jest pusta, zarówno tył, jak i przód są inicjowane wartością 0. Teraz oba będą wskazywać na pierwszy element.
- W przeciwnym razie zwiększ tył o 1. Jeśli tył ma ostatni indeks (lub rozmiar - 1), to zamiast zwiększać go o 1, musimy go wyrównać do 0.
Usunięcie z przodu
W tej operacji element jest usuwany z początku kolejki. Przed wykonaniem operacji musimy najpierw sprawdzić, czy kolejka jest pusta, czy nie.
Jeśli kolejka jest pusta, tj. przód = -1, jest to warunek niedopełnienia i nie możemy wykonać usunięcia. Jeśli kolejka nie jest pełna, element można wstawić od frontu, korzystając z poniższych warunków -
Jeśli deque ma tylko jeden element, ustaw tył = -1 i przód = -1.
W przeciwnym razie, jeśli przód jest na końcu (to znaczy przód = rozmiar - 1), ustaw przód = 0.
typy komputerów
W przeciwnym razie zwiększ przód o 1 (tj. przód = przód + 1).
Usunięcie z tyłu
W tej operacji element jest usuwany z końca kolejki. Przed wykonaniem operacji musimy najpierw sprawdzić, czy kolejka jest pusta, czy nie.
Jeśli kolejka jest pusta, tj. przód = -1, jest to warunek niedopełnienia i nie możemy wykonać usunięcia.
Jeśli deque ma tylko jeden element, ustaw tył = -1 i przód = -1.
Jeśli tył = 0 (tył jest z przodu), to ustaw tył = n - 1.
W przeciwnym razie zmniejsz tył o 1 (lub tył = tył -1).
Sprawdź puste
Ta operacja jest wykonywana w celu sprawdzenia, czy deque jest pusta, czy nie. Jeśli front = -1, oznacza to, że deque jest pusta.
Sprawdź pełne
Ta operacja jest wykonywana w celu sprawdzenia, czy deque jest pełna, czy nie. Jeśli przód = tył + 1 lub przód = 0 i tył = n - 1, oznacza to, że deque jest pełne.
Złożoność czasowa wszystkich powyższych operacji deque wynosi O(1), tj. jest stała.
Zastosowania deque
- Deque może być używany zarówno jako stos, jak i kolejka, ponieważ obsługuje obie operacje.
- Deque może służyć jako sprawdzanie palindromu, co oznacza, że jeśli odczytamy ciąg z obu końców, będzie on taki sam.
Implementacja deque
Przyjrzyjmy się teraz implementacji deque w języku programowania C.
znak na int w Javie
#include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; } Wyjście:
To tyle na temat artykułu. Mamy nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.