Структуры и алгоритмы обработки данных, часть 4

9.  Какие характеристики стека вам известны?

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

push

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

pop

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

back

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

size

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

clear

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

10.  Какие характеристики дека вам известны?

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front

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

push_back

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

pop_front

Извлечь из дека первый элемент

pop_back

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

front

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

back

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

size

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

clear

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

11.  Какие характеристики очереди вам известны?

Очередью (aнгл. queue) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.