DOUG LLOYD: Więc jeśli masz oglądałem film na stosie,
jest to prawdopodobnie będzie czuć się jak trochę deja vu.
To będzie bardzo podobnej koncepcji, tylko z lekkim akcentem na jej temat.
Mamy zamiar rozmawiać teraz o kolejkach.
Tak kolejka podobny do stosu jest inny rodzaj struktury danych
że możemy użyć, aby utrzymać dane w sposób zorganizowany.
Podobnie jak w przypadku stosu może to być realizowane
jako tablica lub połączonej listy.
W przeciwieństwie do stosu, zasady używamy, aby określić
Kiedy robi się dodawane i usuwane z kolejki są nieco inne.
>> W przeciwieństwie do stosu, który jest strukturą LIFO,
trwać, pierwsze wyszło, kolejka jest FIFO Struktura, FIFO, pierwsze weszło, pierwsze wyszło.
Teraz kolejek, prawdopodobnie mają analogię do kolejek.
Jeśli kiedykolwiek byłeś w kolejce park rozrywki lub w banku,
jest swego rodzaju uczciwości wdrożenie struktury.
Pierwsza osoba w kolejce bank jest pierwszą osobą,
kto może mówić do kasjera.
>> Byłoby to coś w rodzaju wyścigu części dolnej, jeśli jedynym sposobem
masz mówić do kasjera Bank miał być ostatnią osobą w kolejce.
Wszyscy zawsze chcą być ostatnią osobą w kolejce,
a osoba, która była tam pierwszy którzy czekali na chwilę,
może być tam przez kilka godzin, i godziny, a godzina
przed mają szansę rzeczywiście wycofania pieniędzy w banku.
A więc kolejki są sortowania rzetelność realizacji struktury.
Ale to nie musi oznaczać, że stosy są złe, po prostu
że kolejki są kolejnym sposobem, aby to zrobić.
Więc znowu kolejka jest pierwsze weszło, pierwsze się, w stosunku do stosu, który trwał w,
pierwsze wyszło.
Podobnie jak w przypadku stosu mamy dwie operacje
które możemy wykonać na kolejkach.
Nazwy są enqueue, która jest dodanie Nowym elementem na końcu w kolejce,
oraz z kolejki, która jest usunąć najstarszy
Element z przodu kolejki.
Tak więc mamy zamiar dodać elementy na koniec kolejki
i jedziemy do usunięcia elementów od przodu kolejki.
Ponownie, ze stosem, byliśmy dodanie Elementy do szczytu stosu
i usuwanie elementów ze szczytu stosu.
Więc z Kolejkuj, to dodanie do końcem, usuwając z przodu.
Więc coś w najstarszej tam zawsze jest następna rzecz
wyjdzie, jeśli spróbujemy i dequeue coś.
>> Więc jeszcze raz, z kolejkami, możemy implementacje oparte na tablicy
i połączone listę opartą implementacje.
Zaczniemy ponownie implementacje oparte na tablicy.
Definicja struktury wygląda dość podobnie.
Mamy kolejną tablicę nie wartości typu danych,
więc może posiadać dowolne typy danych.
Jesteśmy znowu będziemy używać całkowitymi w tym przykładzie.
>> I tak jak z naszym Realizacja Stos układów opartych na
dlatego, że używasz tablica, z konieczności
mają to ograniczenie, że C rodzaju od wymusza na nas, co my
nie mają żadnego dynamizmu w naszym zdolność do wzrostu i kurczyć tablicę.
Musimy zdecydować, na początku co jest maksymalną liczbą rzeczy
że możemy umieścić w tym Kolejka, w tym przypadku,
Pojemność byłoby niektóre funta zdefiniowane stałe w naszym kodzie.
I dla celów tego wideo, pojemność będzie 10.
>> Musimy śledzić przód kolejki
więc wiemy, jaki element chcemy z kolejki,
i musimy również śledzić coś else-- liczbę elementów
że mamy w naszej kolejki.
Zauważ, że nie jesteśmy śledzenie Na koniec w kolejce, tak
wielkość kolejki.
A powodem, który, miejmy nadzieję, stać się nieco jaśniejsze w jednej chwili.
Kiedy zakończyliśmy to definicja typu,
mamy nowy typ danych nazywa kolejki, które możemy teraz
deklarować zmienne tego typu danych.
I nieco myląco, zdecydowałem do wywołania tej kolejki q, list
q zamiast typu danych q.
>> Więc tutaj jest nasza kolejka.
Jest to struktura.
Zawiera ona trzy osoby lub trzy Pola, tablica wielkości pojemności.
W tym przypadku pojemność wynosi 10.
A ta tablica jest zamiar trzymać liczby całkowite.
Na zielono jest przednia naszej kolejki, Kolejnym elementem być usunięte, a na czerwono
będzie wielkość kolejki jak wiele elementów są obecnie
istniejących w kolejce.
Więc jeśli mówimy q.front równi 0, i wielkość q.size równa 0--
My kładziemy 0s w tych dziedzinach.
I w tym momencie, że jesteśmy dość dużo gotowy do rozpoczęcia pracy z naszej kolejki.
>> Więc pierwsza operacja możemy wykonanie jest enqueue coś,
aby dodać nowy element do Koniec kolejki.
No co trzeba to w ogólnym przypadku?
Cóż ta funkcja enqueue potrzeb przyjąć wskaźnik do naszej kolejki.
Ponownie, jeśli oświadczył nasza kolejka na całym świecie,
nie będzie musiał to zrobić jest to konieczne, ale w ogóle,
należy przyjąć wskaźniki struktur danych
tak, ponieważ w przeciwnym razie, jesteśmy przechodzi value-- jesteśmy
przekazując kopie kolejce, i tak nie jesteśmy rzeczywiście się zmienia
kolejka, że ​​chcemy zmienić.
>> Inna sprawa, że ​​musi zrobić, to zaakceptować element danych odpowiedniego typu.
Także w tym przypadku jest będzie całkowite,
ale można dowolnie zadeklarować typ danych jako wartości
i wykorzystują to bardziej ogólnie.
To element chcemy enqueue, chcemy dodać na końcu kolejki.
Wtedy rzeczywiście chcesz umieścić te dane w kolejce.
W tym przypadku, umieszczenie go w prawidłowe położenie naszej tablicy,
a następnie chcemy zmienić rozmiar z kolejki, ile elementów mamy
Obecnie posiadamy.
>> Więc zaczynajmy.
Oto znowu, że ogólnie deklaracja funkcji formą
za to, co enqueue może wyglądać.
I jedziemy.
Miejmy enqueue numer 28 do kolejki.
Więc co zrobimy?
Cóż, przed naszym kolejce jest w 0 ° C, a wielkością naszego kolejki
jest w stanie 0, a więc prawdopodobnie chcesz umieścić liczba 28 w liczbie elementów tablicy
0, tak?
Więc my teraz umieszczone, że tam jest.
Więc teraz, co musimy zmienić?
Nie chcemy, aby zmienić przód kolejki,
bo chcemy wiedzieć, co elementu Może musimy z kolejki później.
Więc powodem mamy przodu nie jest swego rodzaju wskaźnik, co jest
najstarszą rzeczą w tablicy.
Cóż najstarszą rzeczą w array-- w Fakt, jedyną rzeczą w tablicy w prawo
now-- wynosi 28, co jest w miejscu tablicy 0.
Więc nie chcę zmienić ten numer zielony,
dlatego, że to najstarszy elementem.
Przeciwnie, chcemy zmienić rozmiar.
Więc w tym przypadku, będziemy zwiększyć rozmiar do 1.
>> Teraz ogólny rodzaj idei, gdzie Kolejnym elementem jest zamiar iść w kolejce
jest dodanie tych dwóch liczb razem, przód i wielkości,
a powiem ci, gdzie obok element w kolejce pójdzie.
Więc teraz niech enqueue inny numer.
Miejmy enqueue 33.
Więc 33 pójdzie do położenie tablicy 0 oraz 1.
Więc w tym przypadku, to będzie , aby przejść do lokalizacji tablicy 1,
a teraz wielkość naszej kolejce 2.
>> Ponownie, nie zmieniamy przód naszej kolejki,
ponieważ 28 jest nadal Najstarszym elementem, a my
chcą to-- kiedy w końcu się do usuwające wiadomości z kolejki, usuwanie elementów
z tej kolejki, chcemy wiedzieć gdzie najstarszym elementem jest.
A więc zawsze należy zachować niektóre wskaźnik, gdzie to jest.
Więc to, co jest tam na 0.
To, co tam jest przednia.
>> Niech w Kolejkuj jeden element, 19.
Jestem pewien, że można się domyślić gdzie 19 pójdzie.
To będzie iść do Tablica liczba lokalizacja 2.
To 0 plus 2.
A teraz wielkość naszej kolejce 3.
Mamy 3 elementy w nim.
Więc jeśli byliśmy i nie będziemy do teraz, enqueue kolejny element,
byłoby to na miejscu tablicy numer 3, a wielkość naszej kolejki
będzie 4.
Więc my skolejkowany teraz kilka elementów.
Teraz zacznijmy je usunąć.
Miejmy dequeue je z kolejki.
>> Tak podobny do pop, która jest swego rodzaju analogu tego dla stosów
rozkolejkowania musi zaakceptować wskaźnik do queue-- ponownie
chyba to globalnie oświadczył.
Teraz chcemy zmienić lokalizację z przodu kolejki.
To gdzie to rodzaj przychodzi do gry, że zmienna z przodu,
bo kiedy usuniemy element, chcemy
aby przejść do następnego najstarszego elementu.
>> Następnie chcemy, aby zmniejszyć wielkość kolejki
a następnie chcemy zwrócić wartość które zostały usunięte z kolejki.
Ponownie, nie chcemy, aby po prostu wyrzucić.
My prawdopodobnie wyodrębnianiu to z queue-- jesteśmy
usuwające wiadomości z kolejki, bo dbamy o nią.
Dlatego chcemy, to funkcja zwraca element danych wartości typu.
Ponownie, w tym przypadku, wartość ta jest liczbą całkowitą.
>> Więc teraz niech dequeue coś.
Miejmy usunąć element z kolejki.
Jeśli mówimy, int x równa & q, handlowe i q-- jeszcze, że jest to wskaźnik do tego q danych
structure-- co elementem będzie rozkolejkowywana?
W tym przypadku, ponieważ jest to pierwszy in, first out struktury danych, FIFO,
pierwszą rzeczą, jaką wkładamy w to kolejka 28, a więc w tym wypadku
mamy zamiar podjąć 28 z kolejka, a nie 19, co jest czym
byśmy zrobili, gdyby to był stos.
Mamy zamiar wziąć 28 z kolejki.
>> Podobny do tego, co zrobiliśmy z stos, nie jesteśmy w rzeczywistości
zamierza usunąć 28 od samej kolejki
jesteśmy po prostu się do rodzaju z udawać, że nie ma.
Tak to się tam w pamięci, ale jesteśmy po prostu
będzie rodzaj zignorować przesuwając pozostałe dwa obszary naszej danych q
Struktura.
Mamy zamiar zmienić front.
Q.front teraz będzie za 1, bo to jest teraz
najstarszym elementem mamy w naszym kolejki, bo my już usunięty 28,
który był byłym najstarszym elementem.
>> A teraz chcemy zmienić wielkość kolejki
dwa elementy zamiast trzech.
Teraz pamiętam wcześniej powiedziałem, kiedy Aby dodać elementy do kolejki,
umieścić go w miejscu tablicy która jest sumą przedniej i wielkości.
Więc w tym przypadku, jesteśmy w trakcie wdrażania Opisz następny element w kolejce,
w miejscu tablicy 3 oraz zobaczymy, że w drugim.
>> Więc my teraz rozkolejkowywana nasze Pierwszy element z kolejki.
Zróbmy to jeszcze raz.
Miejmy usunąć inny elementu z kolejki.
W przypadku, obecny najstarszych elementem jest lokalizacja tablicy 1.
To, co q.front mówi nam.
To zielone pole mówi nam, że to jest najstarszym elementem.
I tak, x będzie 33.
Będziemy po prostu rodzaj zapomnieć że 33 istnieje w tablicy,
a my powiedzieć, że pory Nowy najstarszy element w kolejce
jest w miejscu tablicy 2, a wielkość kolejki, liczba elementów
mamy w kolejce, to 1.
Teraz enqueue coś, a ja Ten rodzaj dał się drugi temu
ale jeśli chcemy umieścić 40 Into the Kolejka, gdzie jest 40 pójdzie?
Dobrze byliśmy wprowadzenie go w q.front oraz kolejki wielkości,
i tak ma sens faktycznie umieścić 40 tutaj.
Teraz zauważyć, że w jakiś punkt, jedziemy
aby dostać się do końca nasza tablica wewnątrz q,
ale wygaszone 28 i 33-- są faktycznie technicznie
otwarte przestrzenie, prawda?
I tak, możemy eventually-- że zasada dodawania
te dwa together-- możemy w końcu muszą mod o wielkości pojemności
więc możemy owinąć wokół.
>> Więc jeśli mamy do elementu Numer 10, jeśli będziemy
zastępując go w elemencie numer 10, my mieliśmy rzeczywiście umieścić go w miejscu tablicy 0.
A jeśli mieliśmy Tablica miejscowość-- mi wybaczyć,
jeśli dodaliśmy je razem, i udało nam się liczba
11 byłoby gdzie musimy umieścić to, co nie występuje w tym array--
byłoby dzieje poza granicami.
Możemy mod przez 10 i umieścić to w miejscu tablicy 1.
Tak to jest, jak działa kolejki.
Oni zawsze będzie przejść od lewej do prawej ewentualnie zawinięcia.
I wiesz, że są one całości, jeżeli rozmiar, że czerwone pole,
staje się równa pojemności.
I tak po dodaliśmy 40 do Kolejka, oraz co trzeba zrobić?
Cóż, najstarszym elementem w kolejce jest jeszcze 19,
tak, że nie chcemy, aby zmienić przód kolejki,
ale teraz mamy dwa Elementy w kolejce
i tak chcemy zwiększyć nasza wielkość od 1 do 2.
>> To dość dużo go pracy z kolejek macierzy oparte
i podobne w stos, jest również sposób
zaimplementować kolejkę jako połączonej listy.
Teraz, jeśli tego typu struktura danych Wygląda znajomo, to jest.
To nie jest pojedynczo związane listy, jest to podwójnie połączonej listy.
A teraz, na marginesie, to jest w rzeczywistości można zrealizować
kolejka jako pojedynczo połączonej listy, ale Myślę, że w zakresie wizualizacji,
to faktycznie może pomóc, aby zobaczyć to jako podwójnie związaną listy.
Ale to jest na pewno możliwe zrobić to jako pojedynczo połączonej listy.
>> Warto więc spojrzeć na co to może wyglądać.
Jeśli chcemy enquue-- tak i teraz znów jesteśmy
przejście do połączonej listy na podstawie modelu tutaj.
Jeśli chcemy enqueue, chcemy aby dodać nowy element, dobrze
co musimy zrobić?
Cóż, przede wszystkim dlatego, dodajemy na końcu
i usunięcie z począwszy, prawdopodobnie
chcą utrzymać wskaźniki do zarówno głowa i ogon połączonej listy?
Ogon jest inne określenie końcem połączonym listy
ostatni element w połączonej listy.
A to będzie prawdopodobnie, kolejny korzystny nas
jeśli są zmienne globalne.
Ale teraz, jeśli chcemy, aby dodać nowy elementem tego, co mamy robić?
Co nam po prostu [? Malak?] lub dynamicznie przeznaczyć nasz nowy węzeł dla siebie.
A potem, po prostu lubię, gdy dodamy dowolny elementem podwójnie połączonej listy my,
Wystarczy sortować of-- te ostatnie trzy kroki tutaj
są po prostu wszystko o przesunięcie wskaźniki w sposób prawidłowy
tak, że element zostanie dodany do łańcuch bez zerwania łańcucha
lub co jakiś błąd lub z jakiegoś wypadku
zdarzyć, którym przypadkowo sierocych niektóre elementy naszej kolejki.
Oto, co to może wyglądać.
Chcemy, aby dodać element 10 do końca tej kolejce.
Więc najstarszym elementem tutaj reprezentowany jest przez głowę.
To pierwsza rzecz, którą umieścić w tej hipotetycznej kolejce tutaj.
I ogon, 13, jest najbardziej ostatnio dodane element.
I tak, jeśli chcemy enqueue 10 do ta kolejka, chcemy umieścić go po 13.
I tak będziemy dynamicznie przydzielić miejsca dla nowego węzła
i sprawdzić, czy wartość null, aby upewnić się, nie mamy awarię pamięci.
Następnie jedziemy do miejsce 10 w tym węźle,
a teraz musimy być ostrożni o tym, jak zorganizować wskaźniki
więc nie przerwać łańcuch.
>> Możemy ustawić 10 za poprzednie pole zwrócić z powrotem do starego ogona,
i od '10 będzie Nowy ogon w pewnym momencie
od czasu, gdy wszystkie z tych Łańcuchy są połączone
nic nie przyjdzie po 10 teraz.
I tak 10 w następny wskaźnik będzie wskazywać na null,
a następnie po tym jak to zrobić, po mamy podłączony 10 do tyłu do łańcucha
możemy wziąć starą głowę, albo, przepraszam ja, stary ogon kolejki.
Stary koniec kolejki 13, i sprawiają, że wskazują na 10.
A teraz, w tym momencie, mamy skolejkowany numer 10 w tej kolejce.
Wszystko, co musimy zrobić, to po prostu przenieść Ogon pkt do 10 zamiast do 13.
>> Usuwające wiadomości z kolejki jest rzeczywiście bardzo podobne do popping
ze stosu, który jest realizowane jako połączonego listy
jeśli widziałem film stosów.
Wszystko, co musimy zrobić, to rozpocząć się począwszy, znaleźć drugi element,
zwolnienia pierwszego elementu a następnie przesuń głowicę
punkt drugiego elementu.
Chyba lepiej go wizualizować po prostu być bardzo jasne o tym.
Więc oto kolejny nasz kolejki.
12 jest najstarszym elementem w naszej kolejki, głowę.
10 jest najnowszym elementem w naszej kolejki, ogonie.
>> I tak, gdy chcemy z kolejki element,
chcemy usunąć najstarszy element.
Więc co robimy?
Cóż możemy ustawić wskaźnik przejścia który zaczyna się na głowie
i przenieść go tak, że Wskazuje to na drugim elemencie
tego queue-- coś mówiąc TRAV wynosi trav strzałkę obok, na przykład
ruszy trav nie zwrócić się do 15, które, po tym jak z kolejki 12,
usuwamy lub po 12, będzie stają się wówczas najstarszym elementem.
>> Teraz musimy trzymać się na pierwszym elementem przez głowicę wskaźnika
i drugi element poprzez trav wskaźnika.
Możemy teraz wolną głowę, a następnie możemy powiedzieć, nic nie przychodzi przed 15 już.
Tak więc możemy zmienić 15 poprzednią wskaźnik do punktu na null,
i po prostu przesunąć głowę nad.
A tam idziemy.
Teraz mamy powodzeniem rozkolejkowywana 12, a teraz
mieć inną kolejkę 4 elementów.
To dość dużo wszystko nie ma kolejek,
oba oparte na tablicy i linkowane lista oparta.
Jestem Doug Lloyd.
To CS 50.