Реализация с помощью динамического спискаСтек реализуется с помощью однонаправленного списка. Однонаправленного списка достаточно, т.к. операции чтения и записи выполняются с одной стороны набора данных. Первый элемент стека – вершина списка. Если в стеке наверх положили элемент, то мы его добавляем перед первым элементом в списке – операция записи в стек. Операция чтения элемента из стека соответствует выполнению двух операция со списком:
Признаком пустого стека является пустой (нулевой) указатель. Признаком полного стека является ошибка при выделении памяти для добавления элемента в список.
25) Линейные структуры данных. Структура «Очередь»
Запись элементов производится с одной стороны, чтение – с другой. Для очереди определены две операции:
Их описание полностью соответствует операциям для стека, а алгоритмы отличаются в соответствии с правилом FIFO. Очередь может быть реализована массивом или динамическим списком.
S – максимальное количество элементов очереди.
f, l -= указатели на i-й и последний элементы очереди. f будет указывать на 1-й элемент очереди, l – на свободное место после последнего элемента. При очереди массив закольцован. Процесс записи массивов в очередь можно представить следующим образом (l указывает на свободную переменную).
|
Очередь - это структура, функционирующая по принципу FIFO (first input, first output).
Для реализации массивом необходим массив и четыре переменные:
y – состояние очереди.
