Связанное представление

Для связанного способа организации очередей достаточно иметь односвязный список элементов, упорядоченный от начала очереди к концу. Каждый элемент состоит из двух частей памяти, одна из которых содержит хранимую информацию, а вторая содержит указатель (связь) на следующий элемент в списке. Если в очереди хранятся данные, у которых длина информационной части равна L единиц памяти, то длина каждого элемента очереди будет L+1, где одна единица памяти содержит указатель на следующий элемент. Очевидно, что если в каждом элементе на связь тратится намного больше единиц памяти чем на информационную часть, то использование связанного метода представления очередей не будет целесообразным, так как большая часть отведенной нам памяти m будет уходить на организацию связей. И наоборот, чем меньше памяти по сравнению с информационной частью тратится на связи, тем выгоднее будет использовать этот метод. В данной работе будем рассматривать случай, когда информационная часть и отводимая под связь часть имеют одинаковый размер. Тогда m/2 единиц памяти будет затрачено на связи, т. е. для хранения данных мы можем использовать только m - m/2 = m/2 единиц памяти.
Предполагаем, что m кратно 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 и сравнить его со средним временем блуждания при последовательном представлении очередей.