PDA

Просмотр полной версии : Вычисление размера двунаправленной очереди.



Tim
28.03.2004, 13:44
Есть двунаправленная очередь. Для ее элементов определены операции копирования, сравнения. Для очереди определены методы: взять эелемент справа, взять элемент слева, добавить элемент справа, добавить элемент слева. Необходимо вычислить количество элементов в очереди, при условии, что нет возможности выделить память под все элементы очереди, т.е нельзя вытаскивать элементы из очереди пока она не опустеет и считать их в процессе, зато есть возможность выделить память под конечное количеств своих элементов.

Naeel Maqsudov
28.03.2004, 18:19
Два способа с ходу:

А)
Предлагаю определить в очереди метод поиска следующего элемента от заданного,
Тогда выдаляя память всего под один элемент можно будет пройти весь список до конца.

Б)
Если можно определить понятие терминального элемента, то можно зациклить очередь и подсчитать количество элементов в цикле.
Т.е. добавляем некий терминальный элемент в конец. Снимаем элементы с начала очереди и добавляем их обратно в эту очередь, но с противоположного конца. И так повторяем до тех пор, пока не будет снят терминальный элемент. Элементы подсчитаны, а очередь после подсчета будет возвращена в исходное состояние.

Может еще что придумаю потом...

Tim
29.03.2004, 11:08
Да, с терминальным элементом и зацикливанием, пожалуй, подойдет. Сенк`ю.

Naeel Maqsudov
02.04.2004, 08:59
Есть еще более гениальное решение. Если узнавать длину надо часто, то стоит добавить списку такое свойство как Длина. При инициализации списка обнулять длину, а в каждом методе добавления/удаления элементов соответственно увеличивать/уменьшать значение этого свойства. Тогда вообще ничегго не надо считать. Всегда под рукой будет актуальная длина.

ЗЫ
Надо еще позаботиться о потокозащищенности, если это будет использоваться в много поточной программе.