Лабораторная работа «Стек, очередь и дек»
Это прямое раскрытие раздела «Стеки, очереди, деки» рабочей программы. Классические источники по структурам данных также относят стек и очередь к базовым структурам; в приложенной книге Тюкачева и Хлебостроева они рассматриваются наряду со списками, деревьями и графами.
Цель: понять различие LIFO и FIFO и научиться отделять абстрактную структуру данных от её физической реализации.
Требование: не использовать ООП.
Первая часть — стек:
function stackCreate() {
return [];
}
function stackPush(stack, value) {}
function stackPop(stack) {}
function stackPeek(stack) {}
function stackIsEmpty(stack) {}
После реализации:
-
проверить правильность скобочной последовательности;
-
преобразовать или вычислить выражение в обратной польской записи;
-
показать последовательность содержимого стека после каждой операции.
Вторая часть — очередь. Наивную очередь через постоянный shift() разрешается сначала показать как простую реализацию, после чего студент должен сделать очередь с индексом головы:
function queueCreate() {
return {
data: [],
head: 0
};
}
Третья часть — дек:
-
добавление слева;
-
добавление справа;
-
удаление слева;
-
удаление справа;
-
проверка палиндрома.
Прикладная задача для бизнес-информатики: моделирование очереди заявок клиентов. Каждая заявка представляет запись:
{
id: 101,
arrivalTime: 15,
serviceTime: 4
}
Нужно определить среднее время ожидания.
Индивидуальные варианты: изменение числа операторов, порядка поступления, времени обслуживания, политики приоритетов.