W tym wykładzie porozmawiamy o konkretnej implementacji typu danych Q utrudnianie.
Przede wszystkim zamierzam utworzyć inny plik Python o nazwie Q.
I jak omówiliśmy w poprzednich wykładach, ma opłatę za strukturę.
Więc pierwszy, pierwszy, pierwszy termin, który wstawiamy, jest pierwszym, który wyjmujemy.
DOBRZE.
Zdefiniujmy więc klauzulę Q.
Oczywiście znowu będziemy mieli kilka funkcji pomocniczych.
Przede wszystkim definiujemy to w swojej funkcji.
I tutaj tworzymy sygnał jako jednowymiarową tablicę.
Ponownie będziemy przechowywać przedmioty z połową jednowymiarowej tablicy.
Więc cue jest typem danych blokujących.
A jednowymiarowa tablica to podstawowa struktura danych.
Mamy więc tę pustą metodę, a funkcja wróci.
S.
To Q jest równe pustej tablicy lub nie.
Oczywiście złożoność czasu wykonywania tej operacji lub czas otwarcia drzwi.
Dlatego bardzo szybko można sprawdzić, czy ulegają utrudnieniu, czy typ danych jest pusty, czy nie.
OK, porozmawiajmy o funkcji NQ.
Funkcja dochodu będzie pobierać dane.
I znowu musimy dołączyć do struktury danych.
Zasadniczo macierz jednowymiarowa.
Więc znowu będziemy mieć jednowymiarowy układ.
I ilekroć wywołamy funkcję NQ, będziemy zachowywać jeden, dwa, trzy, cztery i tak dalej.
Zamierzamy więc uporządkować dane na końcu jednowymiarowej tablicy.
Ta operacja nakazała wszystkim tak stałą złożoność czasu działania.
Musimy tylko zaplanować.
Dają element na końcu jednowymiarowej tablicy.
A co z Q?
Funkcja Q otrzyma pierwszy element.
Zatem przy indeksie zero usuwamy pierwszy element z jednowymiarowej tablicy.
Więc tutaj skopiuję i wkleję.
A potem wracamy z samymi danymi.
Tak możemy to zrobić.
P Dany przedmiot wyjmujemy z pierwszego elementu, który wstawiliśmy w tym przypadku.
Pierwszy jest jeden.
Więc jeśli to zrobimy.
Q Jeden zatem.
Jeśli ponownie nazwiemy to Q, zwrócimy liczbę całkowitą dwa.
Dlatego zawsze zwrócimy pierwszy przedmiot z początku.
I oczywiście musimy pozbyć się pierwszego przedmiotu, ponieważ go usunęliśmy.
Oczywiście mieliśmy funkcję Bique, która powróci z kropką S.
Indeks Q wynosi zero.
Ta operacja nakazała jeden stały czas działania, ponieważ oczywiście nie usuwamy podanego ITN.
Właśnie zwracamy pierwszy przedmiot.
Będziemy dużo rozmawiać o złożoności tej operacji w czasie wykonywania.
Przede wszystkim porozmawiajmy o samej implementacji.
DOBRZE.
I znowu będziemy mieli.
Skopiuję i wkleję to, żeby być trochę szybszym.
DOBRZE.
Więc mamy rozmiar.
P: Właśnie wracamy z długością kropki S.
Q i funkcja lądowa będą miały jedną stałą złożoność czasu działania.
Ponieważ Python będzie przechowywać liczbę elementów.
Tak więc rozmiar danej struktury danych w tym przypadku mamy tablicę jednowymiarową.
Tak więc funkcja lądowania powróci z liczbą elementów w kolejce.
Właśnie o to nam chodzi.
Więc stworzymy kolejkę.
DOBRZE.
Chcielibyśmy na przykład w kolejce.
Idę na przykład do kolejki.
Dwa, a potem trzy.
A my wydrukujemy tę kolejkę.
I rozszerzamy kolejkę w kolejce.
Więc jeśli uruchomię aplikację, którą, jak widać, udało nam się zrobić kolejkę.
Pierwszy wstawiony element wracam do stosu i zamierzam skopiować tę operację rozmiaru.
Zamierzam więc wydrukować rozmiar kolejki zamiast stosu.
Musimy użyć kolejki, ale w każdym razie, jeśli ją uruchomimy, otrzymamy błąd atrybutu, ponieważ
zamiast.
Rozmiar stosu.
Więc musimy użyć rozmiaru.
P Jeśli więc ponownie uruchomię aplikację i jak widać na początku, rozmiar wynosi trzy, ponieważ w typie danych
przeszkody w kolejce znajdują się trzy elementy, które po operacji w kolejce będą miały również rozmiar
typu danych blokujących kolejkę.
Więc działa dobrze.
Co z operacją w kolejce, że operacja w kolejce będzie musiała wykonać liniowy czas działania, ponieważ mamy
za dużo pilady.
Pierwszy element w tablicy, jeśli otrzymamy pierwszy element w tablicy, jest dość szybki, ponieważ musimy
dosłownie zdobyć pierwszy element w tablicy.
Ale musimy usunąć pierwszy element z tablicy.
Co to znaczy, że mamy taką tablicę?
Pięć, sześć, siedem, osiem, na przykład, jeśli chcemy usunąć pierwszy element i co się stanie, zanim
usuniemy ten dany element.
Ale musimy skopiować wszystkie elementy.
Zasadniczo musimy przesunąć elementy o krok w lewo.
A więc trzy zostaną tutaj skopiowane.
Potem cztery zostaną tutaj skopiowane.
Pięć zostanie skopiowanych tutaj i tak dalej.
Musimy więc iterować po jednowymiarowej tablicy.
I musimy kopiować te elementy jeden po drugim, ponieważ mamy wiele płyt.
Pierwszą kwestią może być pytanie, jak rozwiązać ten problem.
Właśnie dlatego wolimy legalistę.
Ponieważ za każdym razem, gdy musimy manipulować pierwszym elementem, musimy po prostu zaktualizować odniesienia do długiej
listy.
Ale jeśli użyjemy prostej listy łączy, wówczas operacja NQ miałaby liniową złożoność czasu działania,
ponieważ najpierw zdefiniowaliśmy ostatni element struktury danych.
Dobrym podejściem byłoby więc użycie podwójnie połączonej listy, a lista podwójnych transakcji może manipulować pierwszą
pozycją struktury danych w kolejności.
Jedna stała złożoność czasu działania i podwójne zabójcze skanowanie.
Wiele osób uważa ostatni element struktury danych za jeden stały czas działania.
Możemy więc zmniejszyć obie te operacje, aby uporządkować jedną stałą złożoność czasu działania.
W tym przypadku używamy jednowymiarowej tablicy jako podstawowej struktury danych.
Ale nieco lepszym rozwiązaniem byłoby skorzystanie z podwójnej listy rozdań.
To wszystko dotyczy operacji NQ i Q.
Jak widać, działa dobrze.
Ponownie, myślę, że jeśli zrobiliśmy Q wielu przedmiotów, to otrzymujemy błąd.
Więc jeśli go uruchomię, to oczywiście błąd indeksu lub przynajmniej indeks poza zakresem.
Co więc musimy zrobić?
Tutaj musimy to sprawdzić.
Jeśli s tego rozmiaru Q nie jest równy zero, to otrzymamy dane, usuniemy dany węzeł i zwrócimy
dane.
Wreszcie.
Więc jeśli uruchomię go ponownie, oczywiście będzie znowu znany typ.
Możemy więc powiedzieć, że tak.
Zwracamy na przykład minus jeden.
Więc jeśli kolejka jest pusta i chcemy zrobić kolejkę, wówczas zwracamy minus jeden.
Jak widzisz.
W ten sposób możemy uniknąć błędów w czasie wykonywania.
To wszystko dotyczy implementacji typu danych blokującej kolejkę.
Dzięki za oglądanie.