91.Массивы adt-контейнеров шаблонов.

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.

Связный список

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.

Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

INSERT(ключ, значение)

FIND(ключ)

REMOVE(ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами. В паре (k,v) значение v называется значением, ассоциированным с ключом k.

Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, успешности выполнения данной операции).

В разных реализациях ассоциативного массива семантика и названия операций могут отличаться.

Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный массив, в котором в качестве индексов можно использовать не только целые числа, но и значения других типов, например, строки.

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня, таких как Perl, PHP, Python, Ruby, Tcl, JavaScript и др.

92.Стеки adt-контейнеров шаблонов.

C++ Stack – это адаптер контейнера, предоставляющий функциональность стека, то есть структуру данных FILO (first-in, last-out). Конструкторы создают новый стек

empty истина, если в стеке нет элементов

pop удаляет верхний элемент стека

push добавляет элемент на вершину стека

size возвращает количество элементов в стеке

top возвращает ссылку на верхний элемент стека

Стек

Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:

Push Добавить (положить) в конец стека новый элемент

Pop Извлечь из стека последний элемент

Back Узнать значение последнего элемента (не удаляя его)

Size Узнать количество элементов в стеке

Clear Очистить стек (удалить из него все элементы)

Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE, тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE.

Объявим структуру данных типа stack.

const int MAX_SIZE=1000;

struct stack {

int m_size; // Количество элементов в стеке

int m_elems[MAX_SIZE]; // Массив для хранения элементов

stack(); // Конструктор

~stack(); // Деструктор

void push(int d); // Добавить в стек новый элемент

int pop(); // Удалить из стека последний элемент

// и вернуть его значение

int back(); // Вернуть значение последнего элемента

int size(); // Вернуть количество элементов в стеке

void clear(); // Очистить стек

};

Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0..m_size-1. Элементы, добавленные позже, получают большие номера.