Очередь

Реализация с помощью динамического списка

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

Первый элемент стека – вершина списка. Если в стеке наверх положили элемент, то мы его добавляем перед первым элементом в списке – операция записи в стек.

Операция чтения элемента из стека соответствует выполнению двух операция со списком:

1. Выборка первого элемента.
2. Удаление первого элемента.

Признаком пустого стека является пустой (нулевой) указатель. Признаком полного стека является ошибка при выделении памяти для добавления элемента в список.

Очередь - это структура, функционирующая по принципу FIFO (first input, first output).

Запись элементов производится с одной стороны, чтение – с другой.

Для очереди определены две операции:

1. Чтение.
2. Запись.

Их описание полностью соответствует операциям для стека, а алгоритмы отличаются в соответствии с правилом FIFO.

Очередь может быть реализована массивом или динамическим списком.

Дата добавления: 2014-01-15