Даг Lloyd: Так што, калі ў Вас ёсць глядзеў відэа на стэку, гэта, верагодна, будзе адчуваць сябе як трохі дэжа вю. Гэта будзе вельмі падобнай канцэпцыі, толькі з невялікай паварот на ім. Мы будзем казаць цяпер аб чэргах. Так чаргу, падобны на стос, іншы выгляд структуры дадзеных што мы можам выкарыстоўваць, каб захаваць дадзеныя ў арганізаваным парадку. Падобна стэку, ён можа быць рэалізаваны ў выглядзе масіва або звязанага спісу. У адрозненне ад стэка, правілы што мы выкарыстоўваем, каб вызначыць, калі рэчы дадаў атрымаць і выдаляецца з чаргу з'яўляюцца трохі адрозніваецца. У адрозненне ад стэка, які гэта структура ЛИФО, апошні прыйшоў, першы, чэргі FIFO з'яўляецца Структура, FIFO, першы ў першы выйшаў. Цяпер у чаргу, вы, верагодна, ёсць аналогіі з чэргамі. Калі вы калі-небудзь у чарзе ў парк забаў або ў банку, ёсць свайго роду справядлівасці рэалізацыі структуры. Першы чалавек у чарзе ў банк з'яўляецца першым чалавекам, хто атрымлівае, каб пагаварыць з касірам. 

Гэта будзе свайго роду гонкі на дно, калі адзіны спосаб Вы павінны гаварыць з касірам на Банк павінен быў быць апошні чалавек у лініі. Усе заўсёды хочуць каб быць апошнім чалавекам у лініі, і чалавек, які быў там першым хто чакаў некаторы час, можа быць там на працягу некалькіх гадзін, і гадзіны, і гадзіны перш чым яны маюць шанец на самой справе зняць грошы ў банку. І так Чэргі з роду справядлівасць рэалізацыі структуры. Але гэта не абавязкова азначае, што стэкі дрэнна, проста што чэргі яшчэ адзін спосаб зрабіць гэта. Так зноў чэргі першым прыйшоў, першым з, у параўнанні з крамай, які будзе доўжыцца на, першым выйшаў. Падобна стэку, у нас ёсць дзве аперацыі што мы можам выканаць у чарзе. Імёны паставіць у чаргу, якая з'яўляецца даданне новы элемент у канец чаргі, і выдалення з чаргі, якая выдаліць найстарэйшы Элемент з пярэдняй чарзе. Такім чынам, мы збіраемся, каб дадаць элементы на канец чаргі, і мы збіраемся, каб выдаліць элементы ад пярэдняй часткі чарзе. Зноў жа, са стэкам, мы дадавалі Элементы да вяршыні стэка і выдаленне элементаў ад верхняй часткі стэка. Так што з Enqueue, гэта даданне да канец, выдаляючы з фронту. Так найстарэйшых рэчы ў там заўсёды побач, што каб выйсці, калі мы паспрабуем і з чаргі нешта. 

Такім чынам, яшчэ раз, з чэргамі, мы можам рэалізацыі масіваў на аснове і звязаныя-спіс, заснаваны рэалізацый. Мы пачнем зноў масіў на аснове рэалізацыі. Вызначэнне структуры выглядае вельмі падобна. У нас ёсць яшчэ адзін масіў ёсць з значэння тыпу дадзеных, таму ён можа трымаць адвольныя тыпы дадзеных. Мы зноў збіраемся выкарыстоўваць цэлыя лікі ў гэтым прыкладзе. 

І гэтак жа, як з нашым Рэалізацыя стэка на базе масіва, таму што мы выкарыстоўваючы Масіў, мы абавязкова ёсць гэта абмежаванне, што З роду з навязвае нам, што мы не маюць ніякага дынамізм ў нашых здольнасць расці і змяншацца масіў. Мы павінны вырашыць, у пачатку якое максімальную колькасць рэчаў што мы можам паставіць у гэта Чаргу, і ў гэтым выпадку, Аб'ём б некаторыя фунт вызначаецца канстанта ў нашым кодзе. А для мэтаў гэтага відэа, магутнасць будзе 10. 

Мы павінны сачыць за пярэдняя частка чарзе так што мы ведаем, які элемент мы хочам, каб з чаргі, і мы таксама павінны сачыць за Што else-- колькасць элементаў што мы маем у нашай чаргі. Звярніце ўвагу, мы не адсочваць у канец чаргі, проста памер чаргі. І прычына для гэтага, мы спадзяемся, стаць трохі ясней ў дадзены момант. Пасля таго, як мы скончылі гэта вызначэнне тыпу, у нас ёсць новы тып дадзеных называецца чарзе, якія мы цяпер можам аб'яўляць зменныя гэтага тыпу дадзеных. І некалькі цьмяна, я вырашыў назваць гэтую Чарга Q, ліст в замест тыпу дадзеных в. 

Дык вось наш чарзе. Гэта структура. Ён змяшчае тры члена або тры Поля, масіў памеру ёмістасці. У гэтым выпадку, магутнасць складае 10. І гэты масіў збіраецца правесці цэлых лікаў. У зялёны фронт нашай чарзе, Наступны элемент павінен быць выдалены, а ў чырвоным будзе памер чарзе, колькі элементаў у цяперашні час існуючых у чарзе. Так што, калі мы гаворым q.front роўна 0, і памер q.size роўная 0-- мы ўкладваем у 0s гэтых абласцях. І ў гэты момант, мы ў значнай ступені гатовыя прыступіць да працы з нашай чаргі. 

Такім чынам, першая аперацыя, мы можам выканаць, каб паставіць у чаргу нешта, дадаць новы элемент у канец чаргі. Ну што ж, мы павінны зрабіць у агульным выпадку? Ну гэтая функцыя ў чаргу патрэбы прыняць паказальнік на нашай чаргі. Зноў жа, калі мы абвясцілі наша чарга ў глабальным маштабе, мы не павінны былі б зрабіць гэта абавязкова, але ў цэлым, мы трэба прыняць паказальнікі да структур дадзеных як гэта, таму што інакш, мы міма value-- мы перадаючы копіі чарзе, і такім чынам, мы на самай справе не мяняецца чаргу, што мы маем намер змяніць. 

Іншая справа, што трэба зрабіць, гэта прыняць элемент дадзеных адпаведнага тыпу. Зноў жа, у гэтым выпадку, гэта будзе цэлыя лікі, але вы маглі б адвольна абвясціць тып дадзеных у якасці значэння і выкарыстоўваць гэта ў цэлым. Гэта элемент, мы хочам паставіць у чаргу, мы хочам, каб дадаць у канец чаргі. Тады мы сапраўды хочам, каб размясціць гэтыя дадзеныя ў чарзе. У гэтым выпадку, змясціўшы яго ў правільнае размяшчэнне нашага масіва, і то мы хочам, каб змяніць памер чарзе, колькі элементаў мы У цяперашні час ёсць. 

Такім чынам, давайце пачнем. Тут, зноў жа, што агульная Функцыя Форма дэкларацыі за тое, што паставіць у чаргу можа выглядаць. І тут мы ідзем. Давайце ў чаргу лік 28 у чарзе. Так што мы будзем рабіць? Ну, перад нашай чарзе 0, і з памерамі нашай чарзе ў стане 0, і так мы, верагодна, хочаце, каб пакласці лік 28 у масіў колькасці элементаў 0, праўда? Такім чынам, мы ў цяперашні час размешчаны, што там. Так што цяпер нам трэба змяніць? Мы не хочам, каб змяніць фронт чарзе, таму што мы хочам ведаць, што элемент мы, магчыма, спатрэбіцца з чаргі пазней. Так што прычына ў нас ёсць фронт ёсць з'яўляецца свайго роду індыкатарам што найстарэйшы рэч у масіве. Ну самы стары рэч у array-- ў Фактычна, адзіная рэч, у масіве права now-- 28, які з'яўляецца на месцы масіва 0. Такім чынам, мы не хочам, каб змяніць гэтую зялёную нумар, таму што гэта самы стары элемент. Хутчэй за ўсё, мы хочам, каб змяніць памер. Такім чынам, у гэтым выпадку, мы будзем павялічыць памер 1. 

Цяпер наогул-то ідэі, дзе Наступны элемент будзе ісці ў чарзе гэта дадаць гэтыя два нумары разам, пярэдні і памер, і што скажу вам, дзе наступны элемент у чарзе будзе ісці. Так што цяпер давайце ў чаргу іншы нумар. Давайце ў чаргу 33. Так 33 будзе ісці ў Масіў месца 0 плюс 1. Такім чынам, у гэтым выпадку, гэта будзе перайсці ў месцы масіва 1, і ў цяперашні час памер нашага чарзе 2. 

Зноў жа, мы не мяняем пярэдняя нашай чарзе, таму што 28-ранейшаму найстарэйшы элемент, і мы хачу, мэтай якіх, калі мы ў канчатковым выніку атрымаць каб выманне з чаргі, выдаленне элементаў з гэтай чарзе, мы хочам ведаць, дзе самы стары элемент. І таму мы заўсёды павінны падтрымліваць некаторыя паказчыкам, дзе гэта. Дык вось тое, што 0 ёсць для. Гэта тое, што фронт там. 

Давайце ў Дадае яшчэ адзін элемент, 19. Я ўпэўнены, што вы можаце здагадацца, дзе 19 будзе ісці. Гэта збіраецца ісці ў Масіў месца № 2. Гэта плюс 2 0. І ў цяперашні час памер нашага чарзе 3. У нас ёсць 3 элемента ў ім. Так што, калі мы павінны былі, і мы не збіраемся каб прама цяпер, у чаргу яшчэ адзін элемент, яна будзе ісці ў месцы масіва Колькасць 3, а памер чарзе нашай будзе 4. Такім чынам, мы ў чарзе некалькі элементаў у цяперашні час. Зараз давайце пачнем, каб выдаліць іх. Давайце з чаргі іх з чаргі. 

Так падобна на поп, які з'яўляецца свайго роду аналага гэтага для стэкаў, з чаргі неабходна прыму ў паказальнік на queue-- раз, калі гэта не глабальна абвешчаныя. Цяпер мы хочам, каб змяніць месцазнаходжанне у пярэдняй частцы чарзе. Гэта дзе ён накшталт ідзе у гульню, што пярэдняя пераменная, таму што як толькі мы прыбіраем элемент, мы хочам каб перанесьці яго на наступны найстарэйшы элемент. 

Затым мы хочам, каб паменшыць памер чарзе, і то мы хочам, каб вярнуць значэнне які быў выдалены з чаргі. Зноў жа, мы не хочам, каб проста выкінуць яго. Мы, верагодна, здабываюць гэта ад queue-- мы знаходзімся выманне з чаргі, таму што мы клапоцімся пра яго. Такім чынам, мы хочам, каб гэтая функцыя вяртала элемент дадзеных з значэння тыпу. Зноў жа, у гэтым выпадку значэнне цэлы лік. 

Так што цяпер давайце з чаргі нешта. Давайце выдаліць элемент з чаргі. Калі мы кажам, INT х роўны & Q, Ампэрсанд q-- яшчэ раз, што гэта паказальнік на гэты в дадзеных structure-- які элемент збіраецца быць з чаргі? У гэтым выпадку, так як ён з'яўляецца першым увайшоў, першым выйшаў структуры дадзеных, FIFO, Першае, што мы ўкладваем у гэта Чарга была 28, так што ў гэтым выпадку, мы збіраемся ўзяць 28 з чаргу, не 19, гэта тое, што мы зрабілі б, калі гэта было стэк. Мы збіраемся ўзяць 28 з чаргі. 

Падобна таму, што мы зрабілі з стэк, мы на самай справе не збіраецеся выдаліць 28 ад самага чарзе, мы толькі збіраемся роду з прыкінуцца, што гэта не існуе. Так што збіраецца застацца там ў памяці, але мы проста збіраецца роду ігнаруюць яго, перамяшчаючы іншыя два полі нашага кв дадзеных Структура. Мы збіраемся змяніць фронт. Q.front цяпер збіраецца быць 1, таму што гэта цяпер найстарэйшы элемент у нас у Чаргу, таму што мы ўжо выдаленыя 28, які быў былы найстарэйшым элементам. 

А цяпер, мы хочам змяніць памер чарзе двух элементаў замест трох. Цяпер успомніце, раней я сказаў, калі мы Каб дадаць элементы ў чаргу, мы ставім яго ў месцы масіва які з'яўляецца сумай пярэдняй і памеру. Такім чынам, у гэтым выпадку, мы да гэтага часу пакласці гэта, наступны элемент у чарзе, ў месцы масіва 3 і мы ўбачым, што ў секунду. 

Такім чынам, мы ў цяперашні час з чаргі нашай Першы элемент з чаргі. Давайце зробім гэта зноў. Давайце здымем іншы Элемент з чаргі. У выпадку, цяперашні найстарэйшых элемент размяшчэнне масіў 1. Вось што кажа нам q.front. Гэта зялёны скрыню кажа нам, што гэта самы стары элемент. І так, х стане 33. Мы проста выгляд забудзьцеся што 33 існуе ў масіве, і мы будзем казаць, што цяпер, то Новы найстарэйшы элемент у чарзе знаходзіцца ў месцазнаходжанні рашоткі 2, і памеру чарзе, колькасць элементаў у нас у чарзе, 1. Зараз давайце ў чаргу нешта, і я накшталт даў гэта далёка секунду назад, але калі мы хочам, каб пакласці 40 Into The Чаргу, дзе гэта 40 пойдзе? Ну, мы былі пакласці яе у q.front плюс памер чарзе, і таму мае сэнс, каб на самай справе паставіць 40 тут. Зараз звернеце ўвагу, што ў некаторая кропка, мы ідзем каб дабрацца да канца наш масіў ўнутры Q, але знік з 28 і 33-- яны на самой справе, тэхнічна адкрытыя прасторы, правільна? І так, мы можам eventually-- гэтае правіла дадання гэтыя два together-- мы ў канчатковым выніку можа трэба мод памерам ёмістасці так што мы можам абгарнуць вакол. 

Так што, калі мы атрымліваем элемент № 10, калі мы замяніўшы яго ў элемент нумар 10, мы б на самай справе паклаў яго ў масіў размяшчэння 0. І калі мы збіраемся Масіў location-- прабачце, калі мы дадалі іх разам, і мы атрымалі на нумар 11 будзе, дзе мы павінны былі б паставіць яго, што не існуе ў гэтым array-- яна будзе выходзіць за межы. Мы маглі б мода на 10 і паставіць гэта ў месцы масіва 1. Дык вось, як чарзе працуюць. Яны заўсёды будуць ісці злева направа і, магчыма, абгарнуць вакол. І вы ведаеце, што яны поўным аб'ёме, калі памер, што чырвонай скрынцы, становіцца роўным ёмістасці. І так пасля таго як мы дадалі 40 да Чаргу, добра, што мы павінны рабіць? Ну, самы стары элемент у чарзе яшчэ 19, такім чынам, мы не хочам, каб змяніць фронт чарзе, але цяпер у нас ёсць два элементы ў чарзе, і таму мы хочам, каб павялічыць наш памер ад 1 да 2. 

Гэта даволі шмат, яго працы з масівамі на аснове чэргаў, і падобны на стэк, ёсць таксама спосаб ажыццявіць чаргу ў якасці звязанага спісу. Цяпер, калі гэтая структура дадзеных тыпу выглядае знаёмым для вас, гэта так. Гэта не односвязанны спіс, гэта ўдвая звязаны спіс. А цяпер, як у бок, гэта на самай справе можна рэалізаваць чэргі ў односвязный спіс, але Я думаю, што з пункту гледжання візуалізацыі, гэта на самай справе можа дапамагчы, каб паглядзець гэта як двойчы звязанага спісу. Але гэта, безумоўна, можна зрабіць гэта як односвязный спіс. 

Такім чынам, давайце паглядзім на што гэта можа выглядаць. Калі мы хочам, каб enquue-- так што цяпер, раз мы пераход на звязаны спіс тут на аснове мадэлі. Калі мы хочам, каб паставіць у чаргу, мы хочам каб дадаць новы элемент, а тое, што нам трэба рабіць? Ну, у першую чаргу, таму, што мы дадаем у канец і выдаленне ад пачатак, мы, верагодна, хочаце захаваць паказальнікі на абодва галава і хвост сувязнога спісу? Хвост з'яўляецца іншы тэрмін для канец звязанага спісу, апошні элемент ў звязаным спісе. І гэта будзе магчыма, зноў, быць карысным для нас калі яны з'яўляюцца глабальнымі зменнымі. Але цяпер, калі мы хочам, каб дадаць новы элемент, што мы павінны рабіць? Тое, што мы проста [? Малако?] Або дынамічна вылучыць наш новы вузел для сябе. А потым, як і калі мы дадаем любы элемент двойчы звязанага спісу мы, проста трэба адсартаваць of-- гэтыя апошнія тры крокі тут проста ўсё пра перасоўванне ўказальнікі ў правільным шляху так, што элемент будзе дададзены ланцуг без разрыву ланцугу або зрабіць нейкі памылцы або якія маюць нейкія аварыі адбылося ў выніку чаго мы выпадкова сіротам некаторыя элементы нашай чаргі. Вось тое, што гэта можа выглядаць. Мы хочам, каб дадаць элемент 10 у канцы гэтай чарзе. Такім чынам, самы стары элемент тут прадстаўлена галавы. Гэта першае, што мы ставім у гэтым гіпатэтычным чарзе тут. І хвост, 13, з'яўляецца найбольш нядаўна дадалі элемент. І таму, калі мы хочам, каб паставіць у чаргу 10 у гэтая чаргу, мы хочам, каб пакласці яго пасля 13 гадоў. І таму мы збіраемся, каб дынамічна вылучыць месца для новага вузла і праверыць нуль, каб пераканацца, мы не маем правал памяці. Тады мы ідзем да размясціць 10 у гэтым вузле, і зараз мы павінны быць асцярожныя, аб тым, як мы арганізуем паказальнікі такім чынам, мы не разарваць ланцуг. 

Мы можам ўсталяваць 10 ў папярэдняе поле пазначыць вярнуцца да старога хвост, і так '10 будзе Новы хвост нейкі момант да таго часу, усе гэтыя ланцугі звязаныя, нічога не прыйдзе пасля 10 прама цяпер. І так 10 у наступным паказальнік будзе паказваць на нуль, а затым, пасля мы зробім гэта, пасля таго як мы 10 падлучаны таму ў ланцугу, мы можам узяць старую галаву, або, прабачце я, стары хвост чаргі. Старая канец чаргі, 13 і каб яна паказвала на 10. А цяпер, у гэты момант, у нас ёсць ў чаргу лік 10 у гэтай чарзе. Усё, што мы павінны зрабіць цяпер, гэта проста перанесьці хвост паказваюць на 10 замест 13. 

Выманне з чаргі на самай справе вельмі падобны на выскокваюць з чаркі, якая рэалізаваны ў выглядзе звязанага спісу калі вы бачылі відэа стэкі. Усё, што мы павінны зрабіць, гэта пачаць на пачынаючы, знайсці другі элемент, вызваліць першы элемент, а затым перамесціце галаву каб паказаць на другі элемент. Напэўна лепш візуалізаваць яго проста быць вельмі зразумела. Дык вось наша чарга зноў. 12 з'яўляецца найстарэйшым элементам ў нашай чарзе, галавы. 10 з'яўляецца найноўшым элементам ў нашай чарзе, наш хвост. 

І таму, калі мы хочам каб з чаргі элемент, мы хочам, каб выдаліць самы стары элемент. Дык што ж нам рабіць? Ну, мы павінны ўсталяваць паказальнік абыходу які пачынаецца ў галаве, і мы перамясціць яго так, каб ён паказвае на другі элемент гэта нешта queue-- кажучы TRAV Trav роўная стрэлку побач, напрыклад, будзе рухацца TRAV ёсць, каб паказаць на 15, якая, пасля таго як мы з чаргі 12, або пасля таго як мы выдаліць 12, будзе стаць тое найстарэйшы элемент. 

Цяпер у нас ёсць ўлада над першым элемент з дапамогай паказальніка галавы а другі элемент з дапамогай паказальніка Trav. Цяпер мы можам бясплатна галаву, і тады мы можам кажуць нічога не прыходзіць да 15 больш. Такім чынам, мы можам змяніць папярэдняе 15 паказальнік, каб паказаць на нуль, і мы проста перанесьці галаву над. І мы ідзем. Цяпер у нас ёсць паспяхова з чаргі 12, а цяпер мы ёсць іншы чарзе 4 элементаў. Гэта даволі шмат, усё ёсць у чэргах, і на аснове масіва і звязанага спісу на базе. Я Дуг Лойд. Гэта CS 50.