Дъг LLOYD: Така че, ако сте Гледах видеото на комин, Това е може би щеше да се почувства като малко на дежа вю. Това ще е много подобна концепция, само с лек привкус на него. Отиваме да говорим сега за опашки. Така опашка, подобна на комин, е друг вид структура на данните че можем да използваме, за да се запази данни в организиран начин. Подобно на комин, тя може да бъде приложена като масив или свързан списък. За разлика от комин, правилата която ние използваме, за да се определи когато нещата се добавят и премахват от опашката са малко по-различно. За разлика от комин, който е структура LIFO, издържи, първа изходяща, а опашката е FIFO структура, FIFO, първа, първа изходяща. Сега се реди на опашка, най-вероятно има аналогия с опашки. Ако някога сте били в съответствие с увеселителен парк или в банка, там е нещо като справедливост прилагане структура. Първият човек, на опашка в банката е първият човек, кой да говоря с касиера. 

Това ще бъде нещо като състезание до дъното ако единственият начин вие трябва да говорите с касиера в банка е трябвало да бъде последният човек, в съответствие. Всеки винаги ще искам да бъде последният човек, в съответствие, и лицето, което е там първа който е чакал за известно време, може да има в продължение на часове, и часове, и часове преди те да имат шанс да всъщност изтегли пари в банката. И така опашки са подредени на справедливостта прилагане структура. Но това не означава непременно, че стакове са лошо нещо, просто че опашките са друг начин да го направя. Така че отново опашка е на първо място в първо вън, в сравнение с комин, който продължи в, първо се изважда. Подобно на комин, имаме две операции че можем да се извърши по опашки. Имената са Enqueue, която е да се добави нов елемент към края на опашката, и dequeue, което е за да се отстрани най-старите елемент от предната част на опашката. Така че ние ще добавим елементи върху края на опашката, и ние ще премахнете елементи отпред на опашката. Отново с топчето, бяхме добавяне елементи на върха на купчината и премахване на елементи от върха на купчината. Така че с Enqueue, това е като към края, отстраняване от предната. Така че най-старото нещо там Винаги е следващото нещо, да излезе, ако се опитаме и dequeue нещо. 

Така че отново, с опашки, което можем масив-базирани приложения и свързан списък базирани приложения. Ще започнем отново с масив-базирани приложения. Дефиницията на структура изглежда доста сходни. Имаме още един масив там от тип стойност на данните, така че може да побере произволни типове данни. Ние отново ще използваме числа в този пример. 

И точно като в нашия масив-базирани изпълнението комин, защото ние сме с помощта на масив, ние непременно имат това ограничение, че C вид от налага на нас, което е ние не разполагат с никаква динамика в нашия способност да растат и да се свие на масива. Ние трябва да решим в началото което е максималният брой на нещата че можем да се пускат в тази опашка, и в този случай, капацитет ще бъде известна паунд дефинирана константа в нашия код. И за целите на настоящия видео, капацитет ще бъде 10. 

Ние трябва да следим предната част на опашката така че ние знаем кой елемент ние искаме да dequeue, и ние също трябва да следите нещо else-- броя на елементите които имаме в нашата опашка. Забележете, ние не сме следенето на края на опашката, просто размерът на опашката. И причината за това ще се надяваме стане малко по-ясно в един миг. След като сме завършили това определение на типа, имаме нов тип данни нарича опашка, която можем сега декларират променливи от този тип данни. И малко по-объркващо, аз реших да наричаме тази опашка р, буквата р вместо тип данни р на. 

Така че тук е нашата опашка. Това е структура. Тя съдържа три членове или три полета, масив от размера КАПАЦИТЕТ. В този случай, КАПАЦИТЕТ е 10. И това е масив ще се съхраняват числа. В зелено е отпред на нашата опашка, за следващия елемент трябва да се отстрани, и в червено ще бъде размерът на опашката, колко елемента са в момента съществуваща в опашката. Така че, ако ние казваме q.front равни 0, и размер q.size равнява 0-- ние сме пускането 0су в тези области. И в този момент, ние сме доста много готови да започнем да работим с нашите опашка. 

Така че първата операция можем изпълнява е да Enqueue нещо, да се добави нов елемент към в края на опашката. Ами това, което ни е нужно, за да направя в общия случай? Ами тази функция Enqueue нужди да приеме указател към нашата опашка. Отново, ако бяхме обявени за нашата опашка в световен мащаб, ние няма да се наложи да направите това задължително, но като цяло, ние Трябва да приемете указатели на структури от данни по този начин, защото в противен случай, ние сме минава value-- сме минаваща през копия на опашката, и така ние не сме всъщност променя опашката, че възнамеряваме да се промени. 

Другото нещо, то трябва да направите, е да приеме един елемент от данни на съответния тип. Отново, в този случай, това е Ще бъде числа, но бихте могли произволно декларира типа данни като стойност и използвате този по-общ план. Това е елемент, което искаме да Enqueue, искаме да добавим към края на опашката. Тогава ние всъщност искаме да поставете, че данните в опашката. В този случай, което я поставя в правилното разположение на нашия масив, и след това искаме да променим размера на опашката, колко елементи ние, В момента има. 

Така че нека да започнем. Ето, отново, че като цяло декларация формуляр функция за това, което Enqueue може да изглежда така. И ето го. Нека Enqueue броя 28 в опашката. И така, какво ще правим? Е, предната част на нашата опашка е на 0, и размера на нашия опашка е на 0, и така най-вероятно искате да сложите броя 28 на брой елемент на масива 0, нали? Така че ние сега сме поставени, че в там. Така че сега това, което ни е нужно, за да се промени? Ние не искаме да се промени предната част на опашката, защото искаме да знаем какво елемент ние може да се наложи да dequeue късно. Така че причината ние имаме пред там е нещо като индикатор за това, което е най-старото нещо в масива. Ами най-старото нещо в array-- в Всъщност, единственото нещо, в масива полето now-- е 28, което е в масив място 0. Така че ние не искаме да промени това зелено номер, защото това е най-старият елемент. Напротив, ние искаме да промените размера. Така че в този случай, ние ще нарастване размер на 1. 

Сега общ вид на идеята за където следващия елемент е да отиде в режим на изчакване е да добавите тези две числа заедно, предни и размер, и че ще ви кажа, когато на следващия елемент в опашката е да отиде. Така че сега нека Enqueue друг номер. Нека Enqueue 33. Така че 33 ще отидат в масив място 0 плюс 1. Така че в този случай, то се случва да отидат в населено място масив 1, и сега с размерите на нашата опашка е 2. 

Отново, ние не се променя предната част на нашата опашка, защото 28 е все още старият елемент, и ние Искам to-- когато ние в крайна сметка се получи да dequeuing, премахване на елементи от тази опашка, ние искаме да знаем където най-старата елемент. И така, ние винаги трябва да се запази някои показател за къде е това. Така че това е, което за 0 е там за. Това е, което предния е там за. 

Нека в Enqueue още един елемент, 19. Сигурен съм, че можете да се досетите където 19 е да отиде. Това ще отидат в масив място номер 2. Това е 0 плюс 2. И сега с размерите на нашата опашка е 3. В момента има 3 елементи в него. Така че, ако бяхме да, и ние няма до момента, Enqueue друг елемент, тя ще отиде в населено място масив номер 3, както и размерът на нашия опашка ще бъде 4. Така че ние сме enqueued няколко елемента сега. Сега нека да започнем да ги премахнете. Нека да ги dequeue от опашката. 

Така че подобно на поп, който е нещо като на аналог на тази за купчини, dequeue трябва да приеме указател към queue-- отново, освен ако не е в световен мащаб обявена. Сега искаме да промените местоположението на предната част на опашката. Това е мястото, където нещо идва в игра, че пред променлива, защото след като премахнем елемент, ние искаме да го премести към следващото най-старият елемент. 

След това ние искаме да се намали размерът на опашката, и след това ние искаме да се върне стойността че се отстранява от опашката. Отново, ние не искаме просто да го изхвърли. Ние вероятно са извличане то от queue-- сме тя dequeuing, защото ни е грижа за него. Така че ние искаме тази функция, за да се върнете един елемент от данни от тип стойност. Отново, в този случай, стойност не е цяло число. 

Така че сега нека dequeue нещо. Нека да премахнете елемент от опашката. Ако кажем, инт х равнява & Q, амперсанд q-- отново, че е указател към този р данни structure-- какво елемент ще се dequeued? В този случай, тъй като това е първата , първа изходяща структура на данните, FIFO, първото нещо, което ще се постави в тази опашката е 28, и така в този случай, ние ще вземат 28 от опашката, не 19, което е това, ние би направила, ако това е купчина. Отиваме да вземе 28 от опашката. 

Подобно на това, което направихме с комин, ние не сме в действителност ще изтрие 28 от самата опашка, ние просто ще натура на преструвам, че не е там. Така тя ще остане там в паметта, но ние сме просто Ще вид го игнорира, като движите другите две области на нашия р данни структура. Отиваме да се промени на фронта. Q.front сега ще е 1, защото това е в момента най-старият елемент имаме в нашия опашката, защото ние вече сме отстранени 28, който е бивш старият елемент. 

И сега, ние искаме да се промени размерът на опашката до два елемента, вместо три. Сега си спомня по-рано казах, когато ние искате да добавите елементи към опашката, ние го постави в населено място масив която е сумата от предната и размер. Така че в този случай, ние сме все още извеждайки това, на следващия елемент в опашката, в населено място масив 3, и ще видим, че в секунда. 

Така че ние сега сме dequeued ни първи елемент от опашката. Да го направим отново. Нека да премахнете някоя елемент от опашката. В случай, токът старият елемент е място масив 1. Това е, което ни казва q.front. Това зелена кутия ни казва, че това е най-старият елемент. И така, х ще стане 33. Ние просто ще вид забравите че 33 съществува в масива, и ние ще кажем, че сега, Новата най-старият елемент в опашката е на разположение масив 2, както и размерът на опашката, броят на елементите имаме в опашката, е 1. Сега нека Enqueue нещо, и аз нещо като даде това далеч преди една секунда, но ако искаме да се сложи 40 в опашката, където е 40 ще отиде? Ами ние сме били пускането в q.front плюс опашка размер, и така че има смисъл да се действително да се сложи 40 тук. Сега забелязвам, че най- някакъв момент, отиваме за да стигнем до края на нашата масив във вътрешността на р, но това избледнели 28 и 33-- те са в действителност, технически открити пространства, нали? И така, ние може eventually-- това правило на добавяне тези две together-- ние в крайна сметка може Трябва да Mod от размера на капацитет така че можем да обгърне. 

Така че, ако можем да стигнем до елемент номер 10, ако сме заместването му в елемент номер 10, щяхме всъщност го опълчи локация 0. И ако щяхме да масив location-- ме извините, ако ги добавя заедно, и стигнахме до номер 11 ще бъде, когато ние ще трябва да се сложи това, което не съществува в този array-- тя ще се случва извън границите. Бихме могли моден от 10 и сложи то в населено място масив 1. Така че това е начина, опашки работят. Те винаги ще премине от лявата надясно и евентуално обгърне. И знаеш ли, че те са пълно ако размери, че червеното поле, става равен на капацитета. И така, след като сме добавили 40 до опашката, добре, какво трябва да направим? Е, най-старият елемент в опашката все още е 19, така че ние не искаме да се промени предната част на опашката, но сега имаме два елементи в опашката, и така искаме да увеличим нашата размер 1-2. 

Това е доста много, че с работа с масиви базирани опашки, и подобно на стека, има също така за прилагане на опашка като свързан списък. Сега, ако тази структура от данни тип Изглежда ли ви познато, то е. Това не е единично свързан списък, това е двойно свързан списък. И сега, като се отмени, тя е действително възможно да се приложат опашка като единично свързан списък, но Мисля, че от гледна точка на визуализация, тя действително може да помогне, за да видите това като двойно свързан списък. Но това определено е възможно да се направите това като единично свързан списък. 

Така че нека да разгледаме какво е това може да изглежда така. Ако искаме да enquue-- така че сега, отново сме превключване на свързан списък базиран модел тук. Ако искаме да Enqueue, искаме да се добави нов елемент, добре какво трябва да направим? Ами, на първо място, защото ние сме като към края и отстраняване от започваше, ние вероятно Искам да се поддържа указатели както на главата и опашката на свързан списък? Опашката е друг термин за края на свързан списък, последният елемент в свързан списък. И това вероятно ще, отново, за да ни бъде от полза ако те са глобални променливи. Но сега, ако искаме да се добави нова елемент какво трябва да направим? Това, което ние просто [? Малък?] или динамично разпредели нашия нов възел за себе си. И тогава, точно както когато ние добавяме всеки елемент за двойно свързан списък, ние, Просто трябва да се справи of-- тези последните три стъпки тук са само всичко за преместване на указатели в правилната посока така че елементът получава добавя към веригата без да се скъса веригата или вземане на някаква грешка или има някаква авария чрез което се случи случайно сираци някои елементи на нашата опашка. Ето какво това може да изглежда така. Искаме да добавите елемента 10 до края на опашката. Така че най-старият елемент тук е представена от главата. Това е първото нещо, което ще се постави в този хипотетичен опашка тук. И опашката, 13, е най- Наскоро добавя елемент. И така, ако искаме да Enqueue 10 в тази опашка, ние искаме да го кажем след 13. И така, ние ще динамично разпредели пространство за нов възел и се проверява за нищожна да се уверите, ние нямаме недостатъчност с памет. След това ние ще поставяйте 10 в този възел, и сега ние трябва да бъдем внимателни за това как можем да организира указатели така че ние не се прекъсне веригата. 

Можем да зададете 10 в предишния поле до точка обратно към старата опашката, и тъй като '10 ще бъде нова опашка в някакъв момент По времето, когато всички от тях вериги са свързани, нищо ще дойде След 10 в момента. И така 10 следващата показалка ще сочи към нула, и след това, след като правим това, след като сме свързан 10 назад към веригата, можем да вземем старата главата, или, извинението ми, старата опашката на опашката. Старият края на опашката, 13, и да го насочите към 10. И сега, в този момент, ние имаме enqueued броя 10 в тази опашка. Всичко, което трябва да направим сега, е просто придвижете опашката да сочи към 10 вместо до 13. 

Dequeuing е всъщност много подобен на мак от комин, който е реализирана като свързан списък ако сте виждали видеото на купчини. Всичко, което трябва да направите е да започнете в започващ, намери втория елемент, освободи първия елемент, и след това се премести на главата да сочи към втория елемент. Вероятно по-добре да го визуализира само за да бъде допълнително ясно за това. Така че тук е нашата опашка отново. 12 е най-старата елемент в нашата опашката, главата. 10 е най-новият елемент в нашата опашка, нашата опашка. 

И така, когато искаме да dequeue елемент, ние искаме да се премахнат най-старият елемент. И така, какво ще правим? Ами ние зададете прекосява показалка който започва в главата, и ние го премести така, че да точки на втория елемент на този queue-- нещо като казва Trav равнява Trav стрелката, например, ще се движат Trav там, за да сочи към 15, които, след като сме dequeue 12, или след като се премахне 12, воля стане най-после старият елемент. 

Сега ние имаме задържане на първия елемент чрез ръководителя на показалеца и вторият елемент чрез TRAV показалка. Ние вече могат свободно главата, а след това можем да казват нищо не идва преди 15 вече. Така че ние можем да променим 15 на предишния указател да сочи към нула, и ние просто се движат главата над. И там да отидем. Сега имаме успешно dequeued 12, а сега има друга опашка от 4 елемента. Това е почти всичко, има за опашки, както масив основа и свързан списък на базата. Аз съм Дъг Лойд. Това е CS 50.