Даг Ллоид: Дакле, ако сте гледао видео на стеку, Ово је вероватно ће се осећати као мало деја ву. То ће врло сличан концепт, само са благим преокретом на њему. Ми ћемо сада говорити о редовима. Дакле, ред, сличан стека, је друга врста структуре података да можемо користити за одржавање Подаци на организован начин. Слично стеку, може да се спроводи као низа или повезане листе. За разлику од гомиле, правила које користимо за одређивање Када ствари постану додао и уклоњена из Ред је су мало другачије. За разлику од гомиле, која је ЛИФО структура, ласт ин, фирст оут, низ је ФИФО структура, ФИФО први у, први напоље. Сада редови, вероватно имају аналогију са редовима. Ако сте икада били у реду у забавни парк или у банци, ту је нека врста праведности имплементацију структуре. Прва особа у реду у банка је прва особа ко ће говорити на Врачару. 

Било би врста расе на дно, ако једини начин мораш да разговарате са благајника на Банка је требало да буде последња особа у реду. Сви би увек желе да је последња особа у реду, а особа која је тамо први који је чекао неко време, може бити тамо сатима, и сати, и сати пре него што имају прилику да заиста повући никакав новац у банци. И тако су редови врста од правичност спровођење структуру. Али то не мора да значи да гомила су лоша ствар, само да редови су још један начин да се то уради. Дакле, опет ред је први у, први се, насупрот стека који траје у, Први напоље. Слично стеку, имамо две операције да можемо изводити на редовима. Имена су енкуеуе, што је додавање нови елемент до краја реда, и декуеуе, које је за уклањање најстарији елеменат са предње реда. Тако да ћемо додати елементи на крају реда, а ми ћемо уклонити елементе са предње реда. Опет, са стека, додајући смо елементи до врха стека и уклањање елемената са врха стека. Тако је и са енкуеуе, то додајући да крај, уклањање са предње стране. Тако најстарија ствар у ту увек је следећа ствар да изађу ако покушамо и декуеуе нешто. 

Дакле, опет, са редовима, можемо арраи-басед имплементације и повезана листа на бази имплементације. Ми ћемо поново почети са арраи-басед имплементације. Дефиниција Структура Изгледа прилично слично. Имамо још један низ има података типа вредности, тако да може да произвољне врсте података. Опет ћемо користити целих бројева у овом примеру. 

И баш као са нашим Имплементација стек низ-басед, јер смо коришћењем Арраи, ми нужно има ту ограничење да је Ц врста од намеће на нас, који смо се немају динамику у нашим способност да расте и смањују низ. Морамо да одлучимо на почетку што је максималан број ствари да можемо ставити у ово ред, и у овом случају, Капацитет ће бити неких фунта дефинисана константа у нашем коду. И за потребе овог Видео, капацитет ће бити 10. 

Морамо да пратимо предњи део реда тако да знамо који елеменат желимо да декуеуе, и ми такође треба да пратите Нешто елсе-- број елемената да имамо у нашем реду. Обратите пажњу да не праћење на крају реда, само величина реда. А разлог за то ће, надамо се, постати јасније у једном тренутку. Када смо завршили овај тип дефиниција, имамо нову врсту података зове ред, што сада можемо прогласи променљиве тог типа података. И помало збуњујуће, одлучила сам звати овај редослед к, писмо К уместо типа података к. 

Дакле, овде је наш ред. То је структура. Она садржи три члана или три поља, низ величине капацитета. У том случају, капацитет је 10. И ово је низ да држи цели бројеви. У зеленој је предњи део нашег реду је Следећи елемент да се уклоне, а ин ред ће бити величина реда, колико елементи су тренутно постоје у реду. Дакле, ако кажемо к.фронт једнаки 0, а к.сизе величина износи 0-- стављамо 0с у тим областима. И у овом тренутку, ми смо прилично спремни да почнемо да радимо са нашим редовима. 

Дакле, прва операција можемо врши се на енкуеуе нешто, да додате нови елемент крај реда. Па шта треба да раде у општем случају? Па ова функција енкуеуе потребе да прихвати показивач на нашем реду. Опет, ако смо прогласили наш ред глобално, не би требало да урадите нужно, али генерално, ми смо треба да прихвате савете структурама података овако, јер у супротном, смо пролазили поред валуе-- смо пролази копије реду, па ми у ствари не мења да је ред да намеравамо да се мења. 

Друга ствар је потребно да урадите је да прихвати елемент података одговарајућег типа. Опет, у овом случају, то је ће бити цели бројеви, али ти произвољно могао прогласи тип података као вредност и користити ово уопште. То је елеменат желимо да енкуеуе, желимо да додамо на крај реда. Онда смо заправо желе да поставите те податке у реду. У овом случају, што га сврстава у тачна локација нашег низа, а онда желите да промените величину у реду, колико нам елементи Тренутно имамо. 

Дакле, хајде да почнемо. Ево, опет, да се општи облик функција декларација за оно енкуеуе може изгледати. И идемо. Хајде да енкуеуе број 28 у реду. Па шта ћемо да радимо? Па, предњи део нашег реду је на 0, и величину нашег реда је на 0, и тако смо вероватно желите да поставите број 28 у арраи броју елемената 0, зар не? Дакле, сада смо поставили да тамо. Дакле, сада шта нам је потребно да промените? Ми не желимо да промените предњи део реда, јер желимо да знамо шта елемент смо можда ћете морати да декуеуе касније. Дакле, разлог што имамо предњи тамо је нека врста показатеља шта је најстарија ствар у низу. Па најстарија ствар у арраи-- у Чињеница је једина ствар у низу право сада-- је 28, што је на арраи локацији 0. Дакле, ми не желимо да промијенити тај број зелено, јер је то најстарији елеменат. Уместо тога, желимо да промените величину. Дакле, у овом случају, ми ћемо инкрементирање величине до 1. 

Сада општи врста идеје где Следећи елемент ће ићи у реду је то адд та два броја заједно, предња и величина, и то ће вам рећи где следећи елемент у реду је ићи. Дакле, хајде да енкуеуе други број. Идемо енкуеуе 33. Дакле, 33 ће ићи у Арраи локација 0, плус 1. Дакле, у овом случају, то ће да иде у арраи број 1, а сада величине нашег реду је 2. 

Опет, ми не мења предњи део нашег реда, јер 28 је и даље Најстарији елеменат, а ми Желим да-- када смо на крају добили да декуеуинг, уклањање елемената из овог реда, желимо да знамо где је најстарији елемент. И тако смо увек треба да се одржи неки показатељ где је то. Дакле, то је оно што је ту за 0. То је оно фронт је тамо. 

Хајде да у енкуеуе још један елемент, 19. Сигуран сам да можете да погодите где 19 се ићи. То ће ићи у низ локација број 2. То је 0, плус 2. И сада величина нашег реду је 3. Имамо 3 елемента у себи. Дакле, ако бисмо и ми не идемо да одмах, енкуеуе један елемент, да ће то ићи у арраи локација број 3, а величина нашег реда ће бити 4. Тако смо енкуеуед неколико елемената сада. Сада ћемо почети да их уклоните. Хајде да их декуеуе из реда. 

Дакле, слично поп, који је некако од аналога ово за гомиле, декуеуе треба да прихвате показивач на куеуе-- опет, осим ако је глобално проглашен. Сада желимо да променимо локацију на предњој страни реда. Ово је место где је врста у питању у игру, да предња променљива, јер када смо уклонили елемент, желимо да га прешли на следећи најстарији елемент. 

Затим желимо да смањите величина реда, и онда желе да се врате вредност који је уклоњен из реда. Опет, не желимо само да га одбаците. Ми вероватно су вађење је од куеуе-- коме смо то декуеуинг јер нам је стало о томе. Дакле, желимо ову функцију да се врати елемент података типа вредности. Опет, у овом случају, вредност је цео број. 

Тако да сада идемо декуеуе нешто. Да бисте уклонили елемент из реда. Ако кажемо инт једнако & К, Амперсанд к-- Опет то је показивач на овом к подацима струцтуре-- шта елеменат ће бити декуеуед? У овом случају, јер је први у, први пут од структуре података, ФИФО, Прва ствар коју смо ставили у ово ред је био 28, па у том случају, ћемо узети 28 од је ред, а не 19, што је оно што бисмо урадили ако је то гомила. Идемо да 28 из реда. 

Слично ономе што смо урадили са стек, нисмо заправо Избрисаћете 28 из самог реда, ми ћемо само врсти од претварамо да не постоји. Тако да ће остати тамо у меморији, али ми смо само да некако игнорисати померањем друга два поља нашег к података структура. Ми ћемо променити фронт. К.фронт ће сада бе 1, јер то је сада најстарији елеменат имамо у нашој ред, јер смо већ уклоњени 28, што је бивши најстарији елеменат. 

А сада, желимо да променимо величина реда да два елемента уместо три. Сада се сетим раније сам рекао када смо желите да додате елементе у ред, смо га у низ локација што је збир напред и величине. Дакле, у овом случају, ми смо и даље стављање да, следећи елемент у реду, у арраи Локација 3, и видећемо да у секунди. 

Дакле, сада смо наше декуеуед први елемент из реда. Хајде да то урадимо поново. Да бисте уклонили други елеменат из реда. У овом случају, садашњи најстарији елемент је низ локација 1. То је оно што к.фронт нам говори. То зелена кутија нам говори да То је најстарији елеменат. И тако, х ће постати 33. Само ћемо некако заборави да 33 постоји у низу, и ми ћемо рећи да сада, Нова најстарији елемент у реду је на арраи локацији 2, и величину у реду, број елемената имамо у реду, је 1. Сада идемо енкуеуе нешто, а ја некако је то далеко пре секунде, али ако желимо да пут 40 Инто тхе ред, где је 40 ићи? Па смо га ставља у к.фронт, плус куеуе величине, па има смисла заправо ставити 40 овде. Сада приметите да је на нека поента, идемо да се до краја наш низ унутар к, али да избледела 28 и 33-- они у ствари, технички отворени простори, зар не? И тако, можемо евентуалли-- то правило додавања њих двојица заједно-- смо на крају може требају мод по величини капацитета тако да можемо завршити около. 

Дакле, ако стигнемо до елемента број 10, ако смо замењујући у елементу броја 10, ми би Заправо га у арраи локацији 0. А ако ћемо да Арраи лоцатион-- ме извините, ако их додао заједно, и морамо да број 11 би било гдје бисмо морали да ставе она која не постоји у овом арраи-- да би се иде ван граница. Могли мод са 10 и стави је у арраи локацији 1. Па тако редови раде. Они увек отићи из леве десно и евентуално обавије око. И знате да су они пуну величину ако то црвеној кутији, постаје једнако капацитету. И тако након што смо додали 40 до ред, па шта треба да радимо? Па, најстарији елеменат у реду је и даље 19, тако да не желите да промените предњи део реда, али сада имамо два елементи у реду, па желимо да повећамо наше величине од 1 до 2. 

То је прилично га много са рад са арраи-басед редовима, и слично стацк, Такође постоји начин да спроведе ред као повезане листе. Сада, ако ова структура података тип Изгледа познато, јесте. То није појединачно линкед лист, То је двоструко повезана листа. И сада, као на страну, то је заправо могуће спровести Ред је као појединачно повезане листе, али Мислим да је у питању визуелизације, заправо може помоћи да видите ово као двоструко повезане листе. Али је свакако могуће ово као појединачно повезане листе. 

Дакле, хајде да погледамо шта би ово могло изгледати. Ако желимо да енкууе-- тако да сада, опет смо Преласком на повезане листе заснован модел овде. Ако желимо да енкуеуе, желимо да додате нови елемент, добро шта треба да урадимо? Па, пре свега, због тога што смо додавање до краја и уклањање из почиње, вероватно желе да задрже путоказе до оба глава и реп повезане листе? Реп као још један термин за крај повезане листе, последњи елемент у повезане листе. И то ће вероватно, опет, бити корисно нам ако су глобалне променљиве. Али сада ако желимо да додамо нови елеменат шта морамо да урадимо? Оно што смо [? Малак?] или динамички издвајају наш нови чвор за себе. А онда, баш као кад додамо било елемент за двоструко повезана попису, Само треба да сортирате од-- те последња три корака овде само све о померање показивачи на исправан начин тако да је елемент се додаје в ланац без прекидања ланца или прављење неку врсту грешке или имају неку врсту несреће догодити чиме смо случајно сироче неке елементе наше ред. Ево шта би то могло изгледати. Желимо да додате елемент 10 до краја овог реда. Дакле, најстарији елеменат овде заступа главу. То је прва ствар коју смо ставили у овом хипотетички ред овде. И реп, 13, је највише Недавно је додао елемент. И тако, ако желимо да енкуеуе 10 у ово ред, желимо да га ставите након 13. И тако ћемо динамички доделити простор за нови чвор и проверите нулл бисте били сигурни немамо меморијску неуспех. Онда ћемо место 10 у тај чвор, и сада морамо да будемо опрезни о томе како смо организујемо савете тако да не прекинути ланац. 

Можемо сет 10 је претходном пољу да укаже врати на старо репа, и пошто '10 ће бити Нова реп у неком тренутку у време свих ових ланци су повезани, ништа се неће доћи после 10 сада. И тако 10 је следећи показивач ће указати на нулл, и онда када смо ово, након што сам повезан 10 уназад за ланац, можемо узети стару главу, или, изговор ја, стари реп реду. Стари крај реда, 13, и чине га указују на 10. И сада, у овом тренутку имамо енкуеуед број 10 у овом реду. Све што треба да урадимо је само померање реп да укаже на 10, уместо на 13. 

Декуеуинг је заправо веома сличан искакање из стека који је имплементиран као повезане листе ако сте видели димњака видео. Све што треба да урадите је почети у почиње, наћи други елемент, ослободи први елемент, а затим померите главу да укаже на други елемент. Вероватно боље да га представи Само да би било екстра јасно о томе. Дакле, овде је опет наш ред. 12 је најстарији елеменат у нашем реду, главе. 10 је најновији елеменат у нашем реду, наш репа. 

И тако, када желимо да декуеуе елемент, желимо да уклоните најстарији елемент. Па шта да радимо? Па смо поставили Траверсал показивач који почиње на челу, а ми га померите тако да указује на други елемент ово куеуе-- нешто говорећи Трав једнако Трав арров следећи, на пример, би се кретали Трав ту да укаже на 15, који, када смо декуеуе 12, или након што смо уклонили 12, хоће постао тада најстарији елеменат. 

Сада имамо држите на први елеменат преко показивача главе а други елемент преко показивача трав. Ми смо сада могу слободно главу, а онда можемо кажу ништа више долази пре 15 година. Дакле, можемо да променимо 15 је претходна показивач да укаже на нулл, а ми смо само померите главу изнад. И тамо идемо. Сада смо успешно декуеуед 12, а сада смо још један ред од 4 елемента. То је отприлике све ту је редовима, и низ засноване и повезане листа основи. Ја сам Доуг Лојд. Ово је ЦС 50.