Queue.md

Разбор задачи «Queue»

Условие

Вам требуется реализовать класс Queue, аналогичный адаптеру std::queue, являющийся оберткой над некоторым стандартным контейнером и реализующий интерфейс очереди. Класс должен быть шаблонным. Первый шаблонный параметр T — тип хранимых элементов. Второй шаблонный параметр — контейнер, используемый для хранения элементов (по умолчанию — std::deque<T>):

template <typename T, typename Container = std::deque<T>>
class Queue;

Предусмотрите в классе следующее:

1. Конструктор по умолчанию, создающий пустую очередь.
2. Константную функцию front, возвращающую элемент, стоящий в начале очереди.
3. Неконстантную функцию front, возвращающую по ссылке элемент, стоящий в начале очереди (и тем самым позволяющую его изменять).
4. Функцию pop, убирающую элемент из начала очереди (и ничего не возвращающую).
5. Функцию push, кладущую переданный элемент в конец очереди.
6. Функцию size, возвращающую количество элементов.
7. Функцию empty, возвращающую true тогда и только тогда, когда очередь пуста.
8. Операторы == и != для сравнения двух очередей.

Решение

Наш класс будет являться просто обёрткой над контейнером. Все функции нашего класса будут сводиться к вызову соответствующих функций контейнера. Смысл нашего класса в том, что мы ограничиваем публичный интерфейс, оставляя только функции, специфичные для очереди. Например, у нас не будет оператора [] или функций begin и end, так как для очереди они не нужны. Кроме того, некоторые функции у очереди будут называться иначе (push и pop вместо push_back и pop_front), так как для очереди бессмысленно указывать, с какой стороны в неё поступают элементы, и с какой извлекаются.

Конструктор класса Queue можно не писать, так как компилятор предоставит автоматически конструктор по умолчанию.

#include <deque>

template <typename T, typename Container = std::deque<T>>
class Queue {
private:
    Container data;

public:
    const T& front() const {
        return data.front();
    }

    T& front() {
        return data.front();
    }

    void push(const T& elem) {
        data.push_back(elem);
    }

    void pop() {
        data.pop_front();
    }

    size_t size() const {
        return data.size();
    }

    bool empty() const {
        return data.empty();
    }

    bool operator == (const Queue& other) const {
        return data == other.data;
    }

    bool operator != (const Queue& other) const {
        return !operator==(other);
    }
};

Обратите внимание, что операторы == и !=, а также функции size и empty объявлены константными, так как они не меняют очередь. Это позволяет применять их к константным очередям. Также функция front перегружена по константности: для константных очередей элемент возвращается для чтения, а для неконстантных — для записи.