Связанное представление
Для связанного способа организации очередей достаточно иметь односвязный
список элементов, упорядоченный от начала очереди к концу. Каждый элемент
состоит из двух частей памяти, одна из которых содержит хранимую информацию,
а вторая содержит указатель (связь) на следующий элемент в списке. Если в
очереди хранятся данные, у которых длина информационной части равна L единиц
памяти, то длина каждого элемента очереди будет L+1, где одна единица памяти
содержит указатель на следующий элемент. Очевидно, что если в каждом элементе
на связь тратится намного больше единиц памяти чем на информационную часть,
то использование связанного метода представления очередей не будет
целесообразным, так как большая часть отведенной нам памяти m будет
уходить на организацию связей. И наоборот, чем меньше памяти по сравнению с
информационной частью тратится на связи, тем выгоднее будет использовать этот
метод. В данной работе будем рассматривать случай, когда информационная часть
и отводимая под связь часть имеют одинаковый размер. Тогда m/2 единиц
памяти будет затрачено на связи, т. е. для хранения данных мы можем
использовать только m - m/2 = m/2 единиц памяти.
Предполагаем, что m кратно 2, т. к. иначе один элемент памяти всегда остается
неиспользованным.
Рис.2 Область блуждания:
Обозначим x1 и x2 - текущие длины очередей. F1 и F2 указатели на первые
элементы очередей, R1 и R2 указатели на последние элементы очередей.
При таком представлении в качестве математической модели будем иметь
случайное блуждание по целочисленной решетке в треугольной области
x1+x2<=m/2+1, где x1+x2=m/2+1 - поглощающий экран, попадание на который
означает переполнение одной из очередей, x1 = -1 и x2 = -1 - отражающие экраны, попадание
на которые означает исключение элемента из пустой очереди (Рис.2).
Блуждание начинается в точке x1 = x2 = 0. Необходимо найти - среднее время блуждания при выходе
из начального состояния x1 = x2 = 0 и сравнить его со средним временем блуждания
при последовательном представлении очередей.