Реализация класса для работы с очередью в С++

Очередь — структура данных, представляющая собой список элементов организованных по принципу «первый пришел — первым вышел». Новые элементы добавляются в конец списка, и по мере выхода из очередь первых элементов, добавленный элемент смещается ближе к началу очереди. 

queue_example

Задача состоит в том, чтобы организовать класс для работы с очередью. Очередь будет представлена в статическом массиве целых чисел. Будут предусмотрены такие функции, как добавление элемента в конец, добавление перед i-тым элементом («для тех, кто якобы занимал очередь еще вчера»), получение значений элементов, удаление i-того элемента и функция для вытаскивания/выхода из очереди. Все эти функции будут в классе queue.

Опишем интерфейс класса queue в файле queue.h:

Приступим к описанию методов класса queue в файле queue.cpp.   Начнем с конструктора:

При создании нового объекта класса queue в конструкторе будут устанавливаться параметры по умолчанию. Первый элемент (start) всегда будет равен 99, так как размер массива составляет 100 элементов, индексация в массиве с 0 до 99. Последний (end), когда элементов в очереди нету, тоже равен 99, так как очередь при создании объекта пуста, и индекс нового элемента будет равняться индексу первого элемента (start).

Модификаторы и селекторы комментировать не буду. И так ясно, что модификатор — изменяет свойство, а селектор — возвращает значение свойства.

Метод add(int d) в качестве формального параметра d принимает числовое значение, которое необходимо добавить в конец очереди:

Так как индексы массива находятся на промежутке от 0 до 99,  и с добавлением нового элемента в очередь свойство end уменьшается на единицу (this->set_end(this->get_end()-1)), когда будет добавлен элемент в нулевой индекс (end=0), переменная end примет значение -1, что будет означать, что массив переполнен. В случае переполнения нашего статического массива array функция вернет значение -1, в случае успешного добавление элемента – 1.

С добавлением элемента не в конец очереди немного сложнее:

Функция принимает два формальных параметра: d — число, которое будет добавлено в очередь, и p — позиция, куда будет добавлен новый элемент. Возможно такая ситуация, когда у нас в очереди 3 элемента, end = 96, а мы по ошибке вызвали функцию с такими параметрами — add(5,97), получится такая ситуация:

99 98 97 96 95
2 4 1 5

Получается, что 96 элемент останется пустой, указатель end сместится на 95, при добавлении нового элемента нами только что добавленный элемент 5 перезапишется. Для этого вводится такая проверка:

И получается, что при попытке добавить элемент за пределы end, переменной p  присваивается текущее значение  переменной end и элемент просто добавится в конец:

99 98 97 96 95
2 4 1  5

При добавлении элемента куда-нибудь внутрь, например на место 97-го, нам понадобится сдвинуть все элементы вправо (уменьшить индекс на единицу), чтобы освободить 97-е место. За это отвечает оставшийся код функции.

Метод get() без формального параметра возвращает значение первого элемента в очереди, а get(int p), возвращает значение элемента p (array[p]):

Для удаления элементов из массива опишем функцию del(int i), которая в качестве формального параметра принимает индекс элемента, который необходимо удалить. При удалении элемента необходимо сместить все правостоящие (индекс которых меньше, чем индекс удаляемого) влево и сместить указатель end (увеличить его на единицу)

Для выхода из очереди (например, когда вы обслужили клиента и он уходит из очереди) опишем функцию take(), которая забирает элемент из массива, смещает все элементы и возвращает значение забранного элемента. Под словом «забирает» имеется ввиду удаляет.

Если вызвать функцию take с формальным параметром take(int p), то функция заберет из очереди элемент  в позиции p

Ну и для отображения текущего состояние объекта опишем функцию print():

Для того чтобы протестировать наш класс, в файле main.cpp я набросал такой код:

В итоге мы получаем такое вот консольное приложение:

queue