polevoi_cpp_2013_spring_lecture_05

Стек (линейный список массив)

вершина

const T& getTop(const St& s)

{

assert(0 != s.m_pHead); return s.m_pHead->m_data;

}

Очередь - операции

•создание

•уничтожение

•добавление элемента

•удаление элемента

•получение значение верхнего элемента

Очередь

голова

pop getTop

push

хвост

isEmpty

Очередь – интерфейс

•create()

•destroy()

•bool isEmpty()

•push(T)

•pop()

•T getTop()

Очередь (в стиле Си)

пример: struct Queue;

bool create(Queue& queue); bool destroy(Queue& queue);

bool isEmpty(const Queue& queue)

bool push(Queue& queue, const T& val) bool pop(Queue& queue);

T getTop(const Queue& queue)

Очередь – реализация

•динамический массив (вставка и извлечение с концов)

•динамический массив (подвижные концы)

•список

Очередь (подвижные концы)

iTail = (iTail + 1) % size; // push

iHead = (iHead + 1) % size; // pop

size – размер буфера

iHead

iTail

Очередь с приоритетом

•<ключ, данные>

•порядок извлечения элементов определяется ключом, а не порядком добавления элементов в очередь

Дэк (двусвязная очередь)

•добавление и извлечение элементов возможна с обоих концов

Сортировка очередью

•наполнить очередь с приоритетом сортируемыми элементами

•извлечь упорядоченные элементы