DOUG LLOYD: Tehát, ha már nézte a videót verem, ez valószínűleg fog érezni mint egy kis deja vu. Ez lesz egy nagyon hasonló fogalom, Csak egy kis csavarral rajta. Fogunk beszélni most körülbelül sorok. Tehát egy sorban, hasonló egy köteg, egy másik fajta adatstruktúra hogy tudjuk használni, hogy fenntartsák adatokat szervezett módon. Hasonlóan egy köteg, ez lehet végrehajtani mint egy tömb, vagy egy láncolt lista. Ellentétben a verem, a szabályok hogy az általunk használt meghatározásához Amikor a dolgok hozzá, és eltávolították Egy sorban egy kicsit más. Szemben egy köteg, amely egy LIFO szerkezet, tart, first out, a várólista egy FIFO szerkezet, FIFO, első, first out. Most sorba, akkor valószínűleg Van egy analógia sorok. Ha valaha is volt a sorban egy vidámpark és egy bank, van egyfajta méltányosság végrehajtási struktúrát. Az első ember a sorban A bank az első, aki aki kapja, hogy beszéljen a pénztárosnak. 

Nem lenne egyfajta verseny az aljára, ha az egyetlen módja megvan beszélni a pénztárosnak a bank volt, hogy az utolsó, aki a sorban. Mindenki azt mindig akar hogy az utolsó, aki a sorban, és az a személy, aki ott volt az első aki már várja egy darabig, lehet ott órákig, és munkaidő, az órát mielőtt még egy esélyt, hogy ténylegesen vissza semmilyen pénzt a bankban. És így sorok fajta a méltányosság végrehajtási struktúrát. De ez nem feltétlenül jelenti azt, hogy stack egy rossz dolog, csak hogy várólisták más módon kell csinálni. Szóval megint egy sort először, első ki, szemben egy köteg, amely utolsóként első ki. Hasonlóan egy köteg, van két művelet hogy el tudjuk végezni a sorok. A nevek Enqueue, ami az, hogy adjunk Új elem, hogy a végén a sorban, és dequeue, amely hogy távolítsa el a legrégebbi elem az első a sorban. Mi is így fogjuk adni elemek rá a végén a sorban, és megyünk elemek eltávolítása A első a sorban. Ismét a verem, mi volt hozzá elemek a tetején a verem és eltávolítása elemek A tetején a verem. Tehát Enqueue, ez hozzátéve, hogy A végén, megszüntetve elölről. Tehát a legrégebbi dolog van Mindig a következő dolog, hogy jöjjön ki, ha megpróbáljuk és dequeue valamit. 

Tehát megint a sorokat, tudjuk tömb alapú megvalósítások és a hozzá kapcsolódó-lista alapú megvalósítások. Kezdjük újra tömb alapú megvalósítások. A szerkezet meghatározása úgy néz ki, szép hasonló. Van egy másik tömb ott az adatok típusú érték, így tartsa tetszőleges adattípusok. Mi újra fog használni egészek ebben a példában. 

És csakúgy, mint a mi tömbalapú verem megvalósításban mert mi használ tömb, akkor feltétlenül Van ez a korlátozás, hogy a C típusú A érvényesíti ránk, ami azt nincs dinamizmus mi növekedni tudjon, és összezsugorodik a tömbben. El kell döntenünk, az elején mi az a maximális számú dolog hogy mi is ebbe várakozási sor, és ebben az esetben, kapacitás lenne néhány font meghatározott állandó kódunkat. És a jelen videó, kapacitás lesz 10. 

Meg kell nyomon követni Az első a sorban így tudjuk, hogy melyik elem akarunk dequeue, és azt is meg kell nyomon követni valami else-- az elemek száma hogy mi a mi sorban. Figyeljük meg mi nem nyomon követhetőek a végén a sorban, csak a méret a sorban. És az oka, hogy remélhetőleg lesz egy kicsit világosabb, egy pillanat. Miután befejeztük Az ilyen típusú meghatározása, van egy új adattípus nevű sorban, amiről most Kijelentem, változó ugyanilyen típusra. És némi zavart, úgy döntöttem, hívni ezt a sort q, a levél q helyett az adatok a q. 

Tehát itt van a mi sorban. Ez egy szerkezet. Ez tartalmaz három tagja vagy három mezők, egy sor méretű kapacitás. Ebben az esetben, a kapacitás 10. És ez a tömb fog tartani egész számok. Ebben a zöld az első a mi sorban, a következő elem el kell távolítani, és a piros lesz a méret a sorban, hány elem jelenleg meglévő a sorban. Tehát, ha azt mondjuk, q.front egyenlők 0, és q.size mérete megegyezik 0-- mi vagyunk ami 0-át ezeken a területeken. És ezen a ponton, mi elég sokat készen áll a munka a mi sorban. 

Tehát az első művelet, amit lehet végre van sorba állítását valamit, hogy egy új elem, hogy a végén a sorban. Hát mit is kell nem az általános esetben? Hát ez a funkció sorba állítását igényeinek hogy elfogadja a mutatót a sorban. Ismét, ha már kijelentette, a sorban globálisan, akkor nem kell, hogy ezt szükségszerűen, de általában, mi el kell fogadnunk mutatók az adatstruktúrák mint ez, mert különben mi elhaladó value-- vagyunk elhaladó példányban a sorban, és így akkor nem is igazából változó a sorban, hogy mi áll szándékunkban változtatni. 

A másik dolog, hogy meg kell tennie, elfogadom egy adat eleme a megfelelő típust. Ismét, ebben az esetben ez lesz egészek, de lehet önkényesen Kijelentem, az adatok típusát, mint érték és ezt általában. Ez az elem szeretnénk sorba állítását, szeretnénk hozzáadni, hogy a végén a sorban. Aztán tényleg akar helyezze, hogy az adatok a sorban. Ebben az esetben, helyezze azt a megfelelő helyen a mi tömb, majd meg akarjuk változtatni a méretét A sorban, hány elem van jelenleg. 

Szóval kezdjük. Itt van, megint, hogy az általános formában funkciót nyilatkozat amit Enqueue nézhet. És kész is van. Nézzük sorba állítását száma 28 a sorba. Szóval mit fogunk csinálni? Nos, az első a mi várólista 0, és a mérete a sorban értéke 0, és így valószínűleg kívánja helyezni száma 28 tömb elem száma 0, ugye? Így már most elhelyezni, hogy ott van. Tehát most mit is kell változtatni? Nem akarjuk megváltoztatni Az első a sorban, mert azt szeretnénk tudni, hogy mi elem szükségünk lehet a dequeue később. Szóval miért kapnak előlap egyfajta indikátora mi A legrégebbi dolog a tömbben. Nos legrégebbi dolog a array-- a Tény, hogy az egyetlen dolog a tömb jobb now-- 28, amely a A tömb 0 helyen. Tehát mi nem akarjuk, hogy megváltoztatni, hogy a zöld számot, mert ez a legrégebbi eleme. Inkább azt szeretnénk változtatni a méretét. Tehát ebben az esetben, akkor növekmény mérete 1. 

Most egy általános egyfajta képet, ahol a következő elem fog menni a sorban van hozzá a két számot együtt, első és mérete, és hogy megmondjuk, ahol a következő elem a sorban fog menni. Így most nézzük sorba állítását másik számot. Nézzük sorba állítását 33. Tehát 33 fog menni tömb helyen 0 és 1. Tehát ebben az esetben, ez lesz bemenni tömb helyen 1, és most a mérete a sorban 2. 

Ismét nem vagyunk változó Az első a mi sorban, mert 28 még mindig a legrégibb eleme, és mi szeretnénk az alábbiakra: amikor végül kap hogy dequeuing, megszüntetve elemek ebből a sorból, azt szeretném tudni, ahol a legrégebbi elem. És így mindig fenn kell tartani Néhány mutatója, hol van. Szóval ez az, amit a 0 ott van. Ez az, ami előtte van ott. 

Nézzük a Enqueue még egy elem, 19. Biztos vagyok benne, akkor hiszem, ahol 19 fog menni. Meg fog menni tömb helyét száma 2. Ez 0 és 2. És most a mérete a sorban 3. Jelenleg 3 elem kerül bele. Tehát ha mi voltunk, és nem megyünk hogy most, sorba állítását másik elem, akkor bemegy tömb helyét 3. számú, és a mérete a sorban lenne 4. Így már enqueued több elemből most. Most kezdjük eltávolítani őket. Nézzük dequeue őket a sorból. 

Tehát hasonló pop, ami egyfajta Az analóg ennek a stack, dequeue kell elfogadni mutatót a queue-- újra, hacsak nem globálisan deklarált. Most szeretnénk változtatni a helyét Az első a sorban. Ez az, ahol ez a fajta jön játékba, hogy a front változó, mert azonnal elhárítjuk egy elem, szeretnénk mozgatni, hogy a következő legrégebbi eleme. 

Aztán csökkenteni akarjuk a méret a sorban, és aztán vissza akar térni az értéket hogy lekerült a sorban. Ismét nem akarjuk, hogy csak megválni tőle. Mi feltehetően bontja ez a queue-- vagyunk dequeuing, mert mi érdekli. Ezért szeretnénk ezt a funkciót, hogy visszatérjen adatelem típusú értéket. Ismét, ez esetben, az érték egész szám. 

Így most nézzük dequeue valamit. Nézzük eltávolít egy elemet a sorból. Ha azt mondjuk, int x = & q, és jelet q-- újra, hogy egy mutató ebben q adatok structure-- melyik elem lesz dequeued? Ebben az esetben, mert ez egy első in, first out adatok szerkezete, FIFO, Az első dolog, amit ebbe várakozási sor 28 volt, és így ebben az esetben, fogunk venni 28 ki a sorba, nem 19, amely a mi mi volna, ha ez egy verem. Megyünk, hogy 28 ki a sorból. 

Hasonló ahhoz, amit csinált verem, nem vagyunk valójában fog törölni 28 a sorból magát, mi csak lesz ilyen A tettetni, hogy nincs ott. Szóval ez ott marad a memóriában, de mi csak fog fajta figyelmen kívül hagyja azt a mozgó a másik két terület a mi Q adatok szerkezetét. Fogunk előlapja cserélhető. Q.front most fog lehet 1, mert ez most A legrégebbi elem van a mi sorban, hiszen már eltávolították 28, ami a korábbi legrégebbi eleme. 

És most, szeretnénk változtatni a méret a sorban a két elem három helyett. Most emlékszem, korábban mondtam, amikor szeretné adni elemek a sorban, rakjuk egy tömbben helyen amely az összege elülső és mérete. Tehát ebben az esetben, mi még mindig üzembe ez a következő elem a sorban, a tömb helyen, 3, és látni fogjuk, hogy a második. 

Így már most dequeued mi első eleme a sorból. Csináljuk újra. Nézzük eltávolítani egy másik eleme a sorból. Abban az esetben, a jelenlegi legrégebbi elem tömb helyét 1. Ez az, amit q.front mondja nekünk. Hogy a zöld mezőben azt mondja, hogy ez a legrégebbi eleme. És így, x lesz 33. Majd csak ilyen elfelejteni hogy 33 létezik a tömb, és azt fogjuk mondani, hogy most, a Új legrégebbi elem a sorban van tömb helyen 2, és a mérete A sorban az elemek száma van a sorban, az 1. Most nézzük sorba állítását valamit, és én egyfajta adta ezt el egy második ezelőtt, de ha azt akarjuk, hogy 40 a sorban, ahol 40 fog menni? Hát mi már üzembe is A q.front plusz sornak a mérete, És ez így van értelme valóban, hogy 40 itt. Most észre, hogy a Valamikor megyünk eljutni a végére a tömb belsejében q, de ez elhalványult 28 és 33-- ők valójában, technikailag tereivel, ugye? És igen, mi is eventually-- ezt a szabályt, hozzátéve E két together-- előbb utóbb kell, hogy mod a méret a kapacitás így tudjuk kerületi. 

Tehát, ha eljutunk elem száma 10, ha mi vagyunk helyette az elemszám 10, mi lenne ténylegesen tedd tömb 0 helyen. És ha megyünk tömb telephelyein bocsánat, ha hozzáadott azokat össze és mi van számát 11 lenne, ha azt kellene tenni azt, amely nem létezik ebben array-- akkor megy ki a határokat. Mi lehetne mod 10 és tegye ez a tömb helyét 1. Szóval így sorban állás dolgozni. Mindig csak menni balról jobbra és esetleg kerületi. És tudod, hogy ők Teljes ha a méret, hogy a piros doboz, egyenlővé válik kapacitást. És így, miután elérhetővé tettük, hogy a 40 queue, illetve mit kell tennünk? Nos, a legrégebbi elem a sorban még mindig 19, így nem akar változtatni Az első a sorban, de most már két elemek a sorban, és így növelni akarjuk, a mérete 1-2. 

Ez nagyjából azt a dolgozó tömb alapú sorok, és hasonló verem, van még egy módja hogy végre egy sorba, mint egy láncolt lista. Most, ha ez az adat struktúra típus úgy néz ki, ismerős neked ez. Ez nem egy egyszeresen láncolt lista, ez egy kétszeresen láncolt lista. És most, mint félretéve, ez valóban lehetséges, hogy végre egy sorba, mint egy egyszeresen láncolt lista, de Azt hiszem, tekintve a megjelenítés, valójában talán segít, hogy megtekinthesse ezt egy kétszeresen láncolt lista. De ez határozottan lehetséges Ehhez a külön-külön láncolt lista. 

Szóval vessünk egy pillantást mi ez a nézhet. Ha azt akarjuk, hogy enquue-- így most megint mi vagyunk váltás egy kapcsolt lista alapú modell itt. Ha azt akarjuk, hogy sorba állítását, azt akarjuk, hogy egy új elem, valamint Mit kell tennünk? Nos, először is, mert mi hozzátéve, hogy a végén és eltávolítja a kezdődő, akkor valószínűleg szeretné fenntartani mutatók mind a fej és a farok a láncolt lista? Farok hogy egy másik kifejezés a végén a láncolt lista, Az utolsó elem a láncolt lista. És ezek valószínűleg, megint lehet hasznos számunkra ha globális változókat. De most, ha azt akarjuk, hogy egy új elem mit kell tennünk? Amit most [? malak?], vagy dinamikusan osztja az új csomópont magunknak. És akkor, mint amikor mi hozzá semmilyen elemet egy kétszeresen láncolt lista vagyunk, Csak meg kell rendezni of-- az utolsó három lépés itt Íme, minden a mozgásról szól a mutatók a helyes utat úgy, hogy az elem lesz hozzá A lánc feltörése nélkül a lánc vagy hogy valamilyen hiba vagy amelynek valamilyen baleset történni, amely által véletlenül árva egyes elemeit a sorban. Itt van, amit ez nézhet. Szeretnénk felvenni az elem 10 a vége ennek a sorban. Tehát a legrégebbi eleme van képviseli a fejét. Ez az első dolog, amit tenni ebbe a feltételezett sorban itt. És a farok, a 13., a leginkább Nemrég hozzáadott elem. És így ha azt akarjuk, hogy sorba állítását 10-et ez a sorban, szeretnénk tedd után 13. És így fogunk dinamikusan osztja helyet egy új csomópont és ellenőrizze a null hogy győződjön meg arról nincs memória hiba. Aztán megyünk helyezze be, hogy a 10 csomópont, és most meg kell, hogy legyen óvatos hogyan szervezzük mutatók így nem megtörni a láncot. 

Mi lehet állítani 10 korábbi terén hogy pont vissza a régi farok, és mivel '10 lesz az új hátsó valamikor Mire az összes ilyen láncok vannak kapcsolva, semmi sem fog jönni 10 után most. És így 10 következő mutatót fog mutatni null, majd miután ezt tesszük, miután már csatlakoztatva 10 hátra a lánc, tudjuk venni a régi fej, vagy mentség Számomra a régi farok a sorban. A régi és a sor végéről, 13, és azt pont 10. És most, ezen a ponton, van enqueued száma 10 ebbe a sorba. Csak annyit kell csinálni, csak ki kell menni a farok, hogy pont helyett 10 és 13. 

Dequeuing valójában nagyon hasonló a felbukkanó kéményből, amely végre egy láncolt lista ha láttad a halom videót. Csak annyit kell tennie, hogy indítsa el a kezdődő, keresse meg a második elem, Az első, az elem, majd mozgatni a fejét hogy pont a második elem. Valószínűleg jobb képzelni csak hogy extra világos róla. Tehát itt van a sorban újra. 12 legrégebbi elem a mi sorban, a fej. 10 a legújabb elem a mi sorban, a farok. 

És amikor azt akarjuk, hogy dequeue egy elem, azt akarjuk, hogy távolítsa el a legrégebbi eleme. Szóval mit tegyünk? Hát mi meg bejárás mutatót hogy indul az élén, és haladunk úgy, hogy rámutat, hogy a második elem E queue-- valamit azzal trav egyenlő Trav arrow következő, például, költözik trav van, hogy pont 15, amely, miután dequeue 12, vagy azt követően, hogy távolítsa el a 12, majd lett az akkori legrégebbi eleme. 

Most már van hatalma az első elem segítségével a mutató vezetője és a második elem keresztül a mutatót trav. Most már szabad fejét, és akkor mi is nem beszélve a szó előtt 15 már. Így tudunk változtatni 15 korábbi mutatóját a null, és mi csak mozog a feje fölött. És ott is vagyunk. Most már sikeresen dequeued 12, és most Van egy másik sorban a 4 elem. Ez elég sok minden van a sorok, Mindkét tömb alapú és kapcsolt-lista alapján. Én Doug Lloyd. Ez CS 50.