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

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Tim
Сообщения: 8
Зарегистрирован: 19 мар 2004, 11:56
Откуда: Москва

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

Сообщение Tim » 28 мар 2004, 12:44

Есть двунаправленная очередь. Для ее элементов определены операции копирования, сравнения. Для очереди определены методы: взять эелемент справа, взять элемент слева, добавить элемент справа, добавить элемент слева. Необходимо вычислить количество элементов в очереди, при условии, что нет возможности выделить память под все элементы очереди, т.е нельзя вытаскивать элементы из очереди пока она не опустеет и считать их в процессе, зато есть возможность выделить память под конечное количеств своих элементов.
[T.M.]

Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

Сообщение Naeel Maqsudov » 28 мар 2004, 17:19

Два способа с ходу:

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

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

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

Tim
Сообщения: 8
Зарегистрирован: 19 мар 2004, 11:56
Откуда: Москва

Сообщение Tim » 29 мар 2004, 10:08

Да, с терминальным элементом и зацикливанием, пожалуй, подойдет. Сенк`ю.
[T.M.]

Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

Сообщение Naeel Maqsudov » 02 апр 2004, 07:59

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

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

Ответить