ДАГ Lloyd: Так що, якщо у Вас є дивився відео на стеку, це, ймовірно, буде почувати себе як трохи дежа вю. Це буде дуже схожою концепції, тільки з невеликою поворот на ньому. Ми будемо говорити зараз про чергах. Так чергу, схожий на стопку, інший вид структури даних що ми можемо використовувати, щоб зберегти дані в організованому порядку. Подібно стеку, він може бути реалізований у вигляді масиву або пов'язаного списку. На відміну від стека, правила що ми використовуємо, щоб визначити, коли речі додав отримати і видаляється з чергу є трохи відрізняється. На відміну від стека, який це структура ЛІФО, останній прийшов, перший, черги 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.