ДАГ 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.