[Powered by Google Translate] [Очередь] [Chris Гербер, Гарвардский университет] Это CS50, CS50.TV] Одним из полезных структуры данных для хранения упорядоченный набор элементов очереди. Он используется, когда элементы должны быть удалены в том же порядке, как они были добавлены. Эта концепция называется FIFO, которое является аббревиатурой первым пришел, первым из. Чтобы помочь себе это, она может быть полезной для фотографии очереди в кассу в магазине. Как люди приходят, они ждут на задней линии. Кассир затем по очереди служит клиентов на фронте, которые затем выйти линию по одному. В компьютерной науке, мы ссылаемся на начало очереди в качестве главы и еще в хвосте. Например, когда мы могли бы использовать это приложение есть лист ожидания для класса учащихся. В качестве места становятся доступными в классе, человек во главе очереди предоставляется возможность записаться в класс. 

Очередь может быть построена с использованием любой коллекции которая хранит данные в целях, таких как массив или связанного списка. Наряду с коллекцией для хранения элементов в очереди, Мы также необходим метод для добавления элементов в конец очереди, которая называется enqueuing, и еще, чтобы удалить элемент из головы очереди, который называется извлечение из очереди. Часто бывает полезно включить другой метод для возврата текущей длины очереди а также метод, чтобы проверить, если очередь пуста. Давайте посмотрим на то, как мы могли бы реализовать в очереди целых чисел в C, с использованием массива для сбора элементов. Во-первых, мы создаем структуру, называемую очередь для хранения наших переменных. Мы будем использовать фиксированный размер индекс 0 массив целых чисел для хранения элементов. Мы также включают переменную головы в котором хранится индекс элемента, который в настоящее время во главе очереди. Третья переменная, называется длиной, будет использоваться отслеживать количество элементов в массиве. В качестве альтернативы, вы можете рассмотреть возможность использования переменной хвост указывать на последний элемент поля в массиве. Перед тем, как писать больше кода, Давайте попробуем наш дизайн. Давайте начнем с пустой массив длиной 0, с головой установлена ​​в 0. Теперь давайте епдиеие 4 значений - 6, 2, 3 и 1. Длина теперь будет 4, и голова будет находиться в точке 0. 

Что произойдет, если мы из очереди значение? Мы будем уменьшить длину до 3, установить голову к 1, и возвращает значение 6. Этот код может выглядеть следующим образом. Здесь мы имеем из очереди функций, которая принимает указатель на очереди - д - и указатель на элемент, который является типом Int. Сначала проверьте длину очереди, чтобы убедиться, это больше, чем 0, обеспечить, чтобы есть элемент, который будет из очереди. Затем мы смотрим в массиве элементов, в положении головы, и установите значение элемента равным значению в этой позиции. Тогда мы меняем голову, чтобы быть следующим индекс % Мощности. Мы затем уменьшить длину очереди на 1. Наконец, мы возвращаем истинную чтобы показать, что из очереди была успешной. Если мы снова из очереди, длина станет 2, голова тоже станет 2, и возвращаемым значением будет 2. 

Что произойдет, если поставить в очередь другого значения, такие как 7? Когда мы были в конце очереди, нам нужно будет обернуть вокруг и сохранить значение в элемент 0 массива. Математически это можно представить, добавляя длину на индекс голову и выполнение модуля использованием очереди мощность. Вот что 2 +2, что на 4% 4, которая равна 0. Переводя эту идею код, который мы эту функцию. Здесь мы видим постановки в очередь функцию, , которая принимает указатель на очереди - Q - и занимает элемент, который будет поставлен в очередь, которая является целым числом. Далее убедитесь, что емкость очереди еще больше, чем текущая длина очереди. Далее, мы храним элемента в массиве элементов по индексу, который определяется руководителем + длина% потенциала очереди. Мы тогда увеличится длина очереди на 1, , а затем вернуться истинные чтобы показать, что функция постановки в очередь был успешным. 

В дополнение к двум функциям мы уже упоминали, Есть два дополнительных функций. Во-первых, это IsEmpty функции, , которая принимает указатель на очереди и проверяет, что длина равна 0. Вторая функция длины, , которая также принимает указатель на очереди и возвращает текущую длину от структуры. Этот краткий обзор показал, одна из возможных реализаций очереди. Одним из ограничений в этой реализации в том, что очередь имеет фиксированный размер максимум. Если мы попытаемся добавить больше элементов, чем может вместить очередь, Мы, возможно, придется проигнорировать запрос и отпустите элемент, или мы, возможно, предпочтут вернуться некоторый тип ошибки. Использование связанного списка, а не массив будет легче динамически размер очереди. Однако, поскольку мы не имеем прямого доступа к элементам связанный список, если мы не будем следить за хвост, мы должны были бы сканировать весь связанный список, чтобы добраться до конца каждый раз. Мы могли бы также рассмотреть возможность использования массива другой тип данных, такие как структуры, создавать очереди более сложные элементы. Вспоминая наш пример класса лист ожидания, эти структуры могут представлять собой отдельные студенты. 

Меня зовут Крис Gerber, и это CS50. [CS50.TV] И возвращается - >> Еще раз. И вернуть истинное чтобы показать, что - очередь была успешной. -% Мощности очереди - Это будет весело в редактирования. [Смех]