46. Адаптеры последовательного контейнера: стек и очередь; очередь с приоритетами.

Адаптеры контейнеров часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека предоставляет stack, queue и priority_queue через адаптеры, которые могут работать с различными типами последовательностей.

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (last in ­ first out) или FILO (first in ­ last out). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке указатель на следующий элемент стека)? также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память.Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek). При проталкивании (push) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным. При удалении элемента (pop) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается. Пример: stack<vector<int> > - целочисленный стек, сделанный из vector stack<deque<char> > - символьный стек, сделанный из deque.

Реализация:

template <class Container>
class stack {
friend bool operator==(const stack<Container>& х, const stack<Container>& y);
friend bool operator<(const stack<Container>& х, const stack<Container>& y);
public:
    typedef Container::value_type value_type;
    typedef Container::size_type size_type;
protected:
    Container c;
public:
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    value_type& top() { return c.back(); }
    const value_type& top() const { return c.back(); }
    void push(const value_type& х) { с.push_back(х); }
    void pop() { c.pop_back(); }
 };

template <class Container>
bool operator==(const stack <Container>& х, const stack<Container>& y)
    { return х.с == у.с;}

template <class Container>
bool operator<(const stack<Container>& х, const stack<Container>& y) 
    { return х.с < у.с; }

**Очередь** — абстрактный тип данных с дисциплиной доступа к элементам FIFO (First In — First Out).

Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди, не путать с обозначением, принятым для двусторонней очереди: deque), при этом выбранный элемент из очереди удаляется. Очевидный минус: размер очереди ограничен. Плюсы: простота работы и некая экономия памяти. Список: динамически выделяем место под новые элементы, освобождаем из­под ненужных. Практически во всех развитых языках программирования реализованы очереди. В STL присутствует класс queue<>, определенный в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в стеках. Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.

Реализация:

template <class Container>
class queue {
    friend bool operator==(const queue<Container>& х, const queue<Container>& y);
    friend bool operator<(const queue<Container>& х, const queue<Container>& y);
public:
    typedef Container::value_type value_type;
    typedef Container::size_type size_type;
protected:
    Container c;
public:
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    value_type& front() { return c.front(); }
    const value_type& front() const { return c.front(); }
    value_type& back() { return c.back(); }
    const value_type& back() const { return c.back(); }
    void push(const value_type& х) { с.push_back(х); }
    void pop() { с.pop_front(); }
};

template <class Container>
    bool operator==(const queue<Container>& х, const queue<Container>& y) 
    { return х.с == у.с;}

template <class Container>
    bool operator<(const queue<Container>& х, const queue<Container>& y) 
    { return х.с < у.с; }

Очередь с приоритетом — абстрактный тип данных, поддерживающий две обязательные операции — добавить элемент и извлечь максимум/минимум. Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множества. Основные методы, реализуемые очередью с приоритетом, следующие: ­ insert(ключ, значение) — добавляет пару (ключ, значение) в хранилище; ­ extract_minimum() — возвращает пару (ключ, значение) с минимальным значением ключа, удаляя её из хранилища. При этом меньшее значение ключа соответствует более высокому приоритету. В некоторых случаях более естественен рост ключа вместе с приоритетом. Тогда второй метод можно назвать extract_maximum(). Есть ряд реализаций в которых обе основные операции выполняются в худшем случае за время, ограниченное O(log n), где n — количество хранимых пар. В качестве примера очереди с приоритетом можно рассмотреть список задач работника. Когда он заканчивает одну задачу, он переходит к очередной — самой приоритетной (ключ будет величиной, обратной приоритету) — то есть выполняет операцию извлечения максимума. Начальник добавляет задачи в список, указывая их приоритет, то есть выполняет операцию добавления элемента.

Реализация:

template <class Container, class Compare = less<Container::value_type> > 
class priority_queue { 
public:
    typedef Container::value_type value_type;
    typedef Container::size_type size_type;
protected:
    Container c;
    Compare comp;
public:
    priority_queue(const Compare& х = Compare()) : c(), comp(х) {}
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last,
        const Compare& х = Compare()) : c(first, last), comp(x) 
        { make_heap(c.begin(), с.end(), comp); }
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    const value_type& top() const { return c.front(); }
    void push(const value_type& х) {
        c.push_back(х);
        push_heap(c.begin(), c.end(), comp);
    }
    void pop() {
        pop_heap(c.begin(), c.end(), comp);
        с.рор_bасk(); 
    } 
};