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.