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