Даг LLOYD: Значи, ако сте гледав видеото на магацинот,
Ова е веројатно нема да се чувствуваат како малку на дежа ву.
Тоа се случува да биде многу сличен концепт, само со мала пресврт на неа.
Ние се случува да се зборува сега за редици.
Па редица, сличен на магацинот, е друг вид на податоци структура
кои може да се користат да се одржи податоци на организиран начин.
Сличен на магацинот, тоа може да се спроведе
како низа или поврзано листа.
За разлика од магацинот, правилата дека ние ги користиме за да се утврди
кога работите ќе се додаде и отстранети од редица се малку различни.
>> За разлика од магацинот, кој е структура LIFO,
трае, а прв, редот е правилото FIFO структура, FIFO, прво, а прв.
Сега редици, најверојатно имаат аналогија редици.
Ако некогаш сте биле во ред на забавен парк или во банка,
таму е вид на правичност спроведување структура.
Првиот човек во ред на банката е првата личност
кој добива да разговарам со судбината.
>> Тоа ќе биде еден вид на трка до дното, ако единствениот начин
ќе морате да разговарам со судбината на банката треба да биде последниот човек во линија.
Сите секогаш би сакал да биде последниот човек во линија,
и лицето кое го имаше првиот кој е на чекање за некое време,
може да има со часови, и часови и часови
пред тие да имаат шанса да се, всушност, повлече пари во банка.
И така редици се вид на правичност спроведување структура.
Но, тоа не мора да значи дека Купишта се лоша работа, само
дека редици се уште еден начин да го направи тоа.
Па повторно на ред е прв дојден, прв надвор, наспроти магацинот кој трае во,
Првиот надвор.
Сличен на магацинот, имаме две операции
дека ние може да се изврши на редици.
Имињата се Стави во ред, што е за да додадете нов елемент до крајот на дното,
и dequeue, што е да се отстрани од најстарите
елемент од предниот дел на дното.
Значи ние се случува да додадете елементи кон крајот на дното,
и ние ќе треба да се отстранат елементите од предниот дел на дното.
Повторно, со стек, бевме додавање елементи на врвот на магацинот
и отстранување на елементи од врвот на магацинот.
Така е и со Стави во ред, тоа е додавање на На крајот, отстранување од напред.
Па најстара работа таму секогаш е следното нешто
да излезе ако се обидеме и dequeue нешто.
>> Значи, повторно, со редици, можеме да низа базирани имплементации
и врзан-листа врз имплементации.
Ние ќе започнеме повторно со низа базирани имплементации.
Дефинирање на структурата изгледа прилично слични.
Имаме уште една низа има вредност од типот податоци,
па тоа може да се одржи произволни типови на податоци.
Ние сме повторно ќе се користи цели броеви во овој пример.
>> И исто како и со нашите низа-базирана имплементација магацинот,
затоа што ние сме со користење на низа, ние мора да се
имаат тоа ограничување дека С вид на наметнува врз нас, што ние
немаат никаква динамика во нашата способност да расте и да се намали на низата.
Ние треба да одлучат на почетокот она што е максималниот број на работите
дека ние може да се стави во овој редот, а во овој случај,
капацитет ќе биде некои фунти дефинирана константа во нашиот код.
И за целите на оваа видео, капацитетот ќе биде 10.
>> Ние треба да ги пратите на на предниот дел на дното
па знаеме кој елемент сакаме да dequeue,
и ние исто така треба да ги пратите на нешто else-- бројот на елементи
кои ги имаме во нашата задача.
Известување ние не сме следење на крајот од редот, само
големината на задачата.
А причината за тоа се надевам дека ќе стане малку појасно, во еден миг.
Откако ќе се заврши оваа дефиниција за тип,
имаме нов тип на податок повика на дното, што можеме сега
декларираат променливи од тој тип на податок.
И малку збунувачки, решив да се јавите на оваа задача q, буквата
q, наместо на податочен тип q.
>> Значи тука е нашата задача.
Тоа е структура.
Таа содржи три члена или три полиња, низа на капацитет големина.
Во овој случај, капацитет е 10.
И оваа низа е ќе се одржи цели броеви.
Во зелени е пред нашите дното, Следниот елемент што треба да се отстранат, а со црвена боја
ќе биде со големина на задачата, колку елементи се во моментов
постоечките во редот.
Па ако се каже q.front еднаквите 0, а големината q.size еднаква 0--
ние сме поставување на 0-ти во тие области.
И во овој момент, ние сме доста подготвени да почнат да работат со нашите редот.
>> Па првата работа што можеме Стави во ред е да се изврши нешто,
за да додадете нов елемент на крајот од редот.
Па, она што ние треба да се направи во општиот случај?
И оваа функција Стави во ред потреби да го прифати покажувач на нашата листа на чекање.
Повторно, ако се декларирале нашите дното на глобално ниво,
ние не би требало да се направи ова задолжително, но во принцип, ние
Треба да го прифатите покажувачи да структури на податоци
како овој, бидејќи во спротивно, ние сме поминувале value-- сме
поминува во примероци од дното, и така ние не сме, всушност, се менува
на листа на чекање дека имаме намера да се промени.
>> Од друга работа што треба да направите е да се прифати еден елемент на податок на соодветниот тип.
Повторно, во овој случај, тоа е ќе биде цели броеви,
но може да се произволно декларираат податочен тип како вредност
и користете го овој поопшто.
Тоа е елементот што сакаме да Стави во ред, сакаме да го додадете на крајот на редот.
Тогаш ние всушност сакаме да поставите дека податоците во редот.
Во овој случај, ставајќи го во точната локација на нашата низа,
а потоа ние сакаме да ја смените големината на листа на чекање, колку елементи ние
во моментов имаат.
>> Па ајде да започнете.
Еве, повторно, дека општо декларација форма функција
Стави во ред за она што може да изгледа.
И тука ќе одиме.
Ајде Стави во ред на бројот 28 во редот.
Па што ќе правиме?
Па, пред нашата задача е на 0, а големината на нашата листа на чекање
е на 0, и така ние веројатно ќе сакате да се стави бројот 28 во број низа елементи
0, нели?
Па ние сега дека сте сместени во таму.
Па сега се што ни е потребно да се промени?
Ние не сакаме да се промени на предниот дел на дното,
затоа што сакаме да знаеме што елемент ние би можеле да треба да dequeue подоцна.
Така причина имаме пред таму е вид на показател за тоа што е
најстара работа на низата.
И најстара работа на array-- во Всушност, единственото нешто во низа во право
now-- е 28, што е во низа локација 0.
Значи, ние не сакаме да промени тоа зелени број,
затоа што тоа е најстарата елемент.
Наместо тоа, ние сакаме да ја смените големината.
Значи во овој случај, ние ќе прираст големината на 1.
>> Сега општ вид на идеја за тоа каде Следниот елемент се случува да одам во редица
е да додадете оние два броја заедно, пред и големина,
и тоа ќе ви кажам каде што следната елемент на листа на чекање се случува да одам.
Па сега ајде Стави во ред друг број.
Ајде Стави во ред 33.
33 па се случува да одат во Низа локација 0 плус 1.
Значи во овој случај, тоа се случува да се оди во локација низата 1,
и сега на големината на нашата задача е 2.
>> Повторно, ние не се менува на предната страна од нашата листа на чекање,
бидејќи 28 се уште е Најстариот елемент, а ние
сакате to-- кога на крајот се да dequeuing, отстранувања на елементи
од оваа редица, сакаме да знаеме каде најстарата елемент е.
И така ние секогаш треба да се одржи некои показател за каде што е.
Значи тоа е она што на 0 е за таму.
Тоа е она што е таму за пред.
>> Ајде во Стави во ред уште еден елемент, 19.
Сигурен сум дека може да се погоди 19 каде се случува да одам.
Тоа се случува да одат во Низа локација број 2.
Тоа е 0, плус 2.
И сега на големината на нашата задача е 3.
Имаме 3 елементи во неа.
Значи, ако веќе треба да се, и ние нема до сега, Стави во ред уште еден елемент,
тоа ќе оди во локација низа број 3, а големината на нашата листа на чекање
ќе биде 4.
Значи ние сме enqueued неколку елементи сега.
Сега ајде да почнеме да ги отстрани.
Ајде да ги dequeue од задачата.
>> Толку слична на поп, кој е вид на аналогот од тоа за Купишта,
dequeue треба да се прифати покажувачот на queue-- повторно,
освен ако тоа е глобално декларирана.
Сега сакаме да ја промените локацијата на предниот дел на дното.
Ова е местото каде што вид на збор стапува на сцената, тој фронт променлива,
затоа што еднаш ги отстраниме елемент, сакаме
да се движи кон следниот најстарата елемент.
>> Тогаш сакаме да се намали големината на листа на чекање,
и тогаш сакаат да се вратат на вредноста која беше отстранета од задачата.
Повторно, ние не сакаме да само да го исфрли.
Ние се претпоставува дека се вадат тоа од queue-- сме
тоа dequeuing бидејќи ние сме загрижени за тоа.
Затоа сакаме оваа функција за да се вратат еден елемент на податок од типот вредност.
Повторно, во овој случај, вредност не е цел број.
>> Па сега ајде dequeue нешто.
Ајде да се отстрани елементот од задачата.
Ако речеме int x е еднаква & П, симболот q-- повторно тоа е покажувач кон ова н податоци
structure-- она ​​елемент ќе се dequeued?
Во овој случај, затоа што тоа е прв , а прв податочна структура, FIFO,
првото нешто што го стави во овој редот беше 28, и така во овој случај,
ние ќе треба да се земе 28 од на листа на чекање, а не 19, што е она што
ние би го направиле ако ова беше оџак.
Ние ќе треба да се земе 28 од редот.
>> Слично на она што го правевме со магацинот, ние не сме, всушност,
случува да ги избришете 28 од самата листа на чекање,
ние сме само ќе вид на преправаме дека не е таму.
Па затоа се случува да остане таму во меморија, но ние сме само
случува да се вид на го игнорираат со поместување другите две полиња на нашите податоци Q
структура.
Ние ќе треба да се промени на предниот дел.
Q.front е сега се случува биде 1, затоа што тоа е сега
најстарата елемент што ја имаме во нашата на дното, бидејќи ние сме веќе елиминирани 28,
кој беше поранешен најстарата елемент.
>> И сега, ние сакаме да се промени на големината на дното
до два елементи, наместо три.
Сега се сеќавам порано кажав, кога ние сакате да го додадете елементи за да се на листа на чекање,
ние го стави во една локација низа која е збир на предните и големина.
Значи во овој случај, ние сме уште ставање тоа, следниот елемент во редот,
во локација низа 3, и ќе видиме дека во една секунда.
>> Па ние сега сме dequeued нашите Првиот елемент од задачата.
Да го направиме тоа повторно.
Ајде да се отстранат на друг елемент од задачата.
Во случај, сегашниот најстарите елемент е локација низа 1.
Тоа е она што q.front ни кажува.
Дека зелено поле, ни кажува дека тоа е најстарата елемент.
И така, ќе стане 33 х.
Ние само ќе вид заборавајте дека 33 постои во низа,
и ние ќе се каже дека сега, нови најстарата елемент во редот
е на локација низа 2, а големината на дното, бројот на елементи
ние сме во ред, е 1.
Сега ајде да Стави во ред нешто, и јас вид даде оваа далеку пред една секунда,
но ако сакаме да се стави 40 во на дното, каде што имаат 40 случува да се оди?
И ние сме биле тоа ставање во q.front плус редица големина,
и така има смисла да се всушност, да се стави 40 тука.
Сега се забележи дека во одреден момент, ние ќе
да се дојде до крајот на нашата низа во внатрешноста на q,
но дека избледени од 28 и 33-- тие се, всушност, технички
отворени простори, нели?
И така, ние можеби eventually-- тоа правило за додавање
тие две together-- ние на крајот може да треба да МО по големината на капацитетот
за да можеме да се заврши околу.
>> Значи, ако ние се дојде до елемент број 10, ако ние сме
го заменува во елемент бројот 10, би всушност, го стави во низа локација 0.
И ако ние се случува да се Низа location-- извинете,
ако им се собираат заедно, и стигнавме до бројот
11 ќе биде каде што ќе треба да се стави тоа што не постои во овој array--
тоа ќе се случува надвор од границите.
Ние би можеле да се современи за 10 и го стави тоа во низа локација 1.
Па тоа е како редици работат.
Тие секогаш се случува да се оди од лево да се во право, а можеби и се обвиткуваат околу.
А ти знаеш дека тие се целосна ако големината, дека црвено поле,
станува еднаква на капацитет.
И така, по додадовме 40 до на дното, и она што ние треба да направите?
Па, најстарата елемент на листа на чекање се уште 19,
па ние не сакаме да се промени на предниот дел на дното,
но сега имаме два елементи на листа на чекање,
и така сакаме да се зголеми нашата големина од 1 до 2.
>> Тоа е доста тоа со работат со низа базирани редици,
и слични на магацинот, таму е исто така начин
за спроведување на редот како поврзани листа.
Сега, ако оваа податочна структура тип изгледа познато за вас, тоа е.
Тоа не е поединечно поврзани листа, тоа е двојно поврзана листата.
И сега, како настрана, тоа е всушност, е можно да се спроведе
редица како одделно поврзани листа, но Мислам дека во однос на визуелизација,
тоа всушност би можеле да помогнат за да ја видите ова како двојно поврзана листата.
Но тоа дефинитивно е можно да се сторам тоа, како одделно поврзани листа.
>> Па ајде да го погледне во она што ова може да изгледа.
Ако сакаме да enquue-- па сега, повторно сме
менувањето на врзан-листа базирани модел тука.
Ако сакаме да се Стави во ред, ние сакаме за да додадете нов елемент, и
она што ние треба да направите?
Па, прв од сите, бидејќи ние сме додавање на крајот
и отстранување од почеток, ние најверојатно
сакаат да го задржат покажувачи за двете главата и опашката на поврзани листа?
Опашка биде уште еден мандат за крајот на поврзани листа,
последниот елемент во поврзаните листа.
И тие ќе веројатно, повторно, да биде од корист за нас
ако тие се глобални променливи.
Но, сега, ако сакаме да додадете нова елемент на она што го имаме да се направи?
Она што ние само [? Malak?] или динамично распредели нашиот нов јазол за нас самите.
А потоа, исто како кога ќе се додаде кој било елемент на двојно поврзана листа ние,
само треба да се најде решение за of-- оние последните три чекори тука
се само сите за поместување на покажувачи на правилен начин
така што елементот добива додадена на синџирот без кршење на синџир
или да се направат некој вид на грешка или да се има некој вид на несреќа
случи со кое би можеле случајно сираче некои елементи на нашата листа на чекање.
Тука е она што ова може да изгледа.
Ние сакаме да додадете елемент 10 до крајот на оваа задача.
Па најстарата елемент тука е претставена од страна на главата.
Тоа е првото нешто што го стави во овој хипотетички ред тука.
И опашката, 13, е најстариот неодамна додаде елемент.
И така, ако сакаме да Стави во ред 10 во оваа задача, ние сакаме да го стави во 13.
И така ние си оди за да се динамички одвои простор за нов јазол
и да се провери за ништовни да бидете сигурни немаме неуспех сеќавање.
Тогаш ние ќе треба да место 10 во тој јазол,
и сега ние треба да бидат внимателни за тоа како ние го организира покажувачи
па ние не се скрши синџирот.
>> Може да се постави 10 претходното поле до точка назад кон стариот опашка,
а од '10 ќе биде нови задни во одреден момент
од страна на време на сите овие синџири се поврзани,
ништо не се случува да дојде по 10 моментов.
И така 10 следната покажувачот ќе укаже на нула,
а потоа откако ќе го направите тоа, откако ќе ја 10 поврзани наназад во синџирот,
можеме да се земе стариот шеф, или, изговор ми, старата опашката на задачата.
Стариот крај на редот, 13, и да ја направат укажуваат на 10.
И сега, во овој момент, имаме enqueued бројот 10 во оваа задача.
Сите ние треба да направите сега е само се движат опашка да се укаже на 10, наместо до 13.
>> Dequeuing е, всушност, многу сличен на пукање
од магацинот, кој е спроведува како поврзани листа
ако сте виделе видео Купишта.
Сите ние треба да направите е да се започне во почеток, се најде на вториот елемент,
ослободување на првиот елемент, а потоа се пресели на главата
до точка на вториот елемент.
Веројатно е подобро да се визуелизира само за да биде екстра јасни околу тоа.
Значи тука е нашата задача повторно.
12 е најстарата елемент во нашата листа на чекање, на главата.
10 е најновиот елемент во нашата задача, нашите опашка.
>> И така, кога сакаме да dequeue елемент,
ние сакаме да се отстрани најстарата елемент.
Значи она што ќе правиме?
Па ние се постави traversal покажувачот која започнува во главата,
и ние ја преместите, така што тоа укажува на вториот елемент
на овој queue-- нешто велејќи trav еднаква trav стрелката до, на пример,
ќе се движи trav таму да се укаже на 15, кои, откако ќе dequeue 12,
или откако ќе се отстранат 12, ќе стане тогашниот најстарата елемент.
>> Сега ќе го одржи на првиот елемент преку глава покажувач
и вториот елемент преку trav покажувачот.
Ние сега можат слободно главата, а потоа можеме велат дека ништо не доаѓа пред 15 повеќе.
За да можеме да се промени 15 претходното покажувачот да укаже на нула,
а ние само се движат над главата.
И таму ќе одиме.
Сега имаме успешно dequeued 12, и сега ние
имаат уште една редица на 4 елементи.
Тоа е доста на сите таму е да редици,
и низа-базирани и поврзани листа-базирана.
Јас сум Даг Лојд.
Ова е 50 КС.