Главная > Без рубрики > Вычисление размера двунаправленной очереди

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


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

Как бы вы её решили?

Реклама
  1. Serger
    22.04.2010 в 11:14

    ограничения не совсем понятны

  2. Serger
    22.04.2010 в 12:59

    Всё, понял. Наверное, только расширив методы дополнительным счётчиком. Но, видимо, это не разрешается.

    А под этим что подразумевается?
    «зато есть возможность выделить память под конечное количеств своих элементов.»

    • Сергей Елин
      22.04.2010 в 13:59

      Можешь сделать буффер для… чего угодно =)

  3. marx
    22.04.2010 в 13:32

    в цикле брать слева и вставлять справа, считать пока не провернется =) т.е. самый первый взятый элемент запоминаем и сравниваем с ним остальные, когда снова он попался, значит прошли всю.

    при этом видимо придется получить read+write lock на эту очередь, чтобы другие ее не поменяли =)

    • Serger
      22.04.2010 в 13:43

      А если в очереди есть дублирующиеся ссылки?

    • Serger
      22.04.2010 в 13:44

      >Для ее элементов определены операции КОПИРОВАНИЯ, сравнения.
      Тем более — при совпадении значений — мало того, что длина не посчитается, так ещё и испортится!

    • Сергей Елин
      22.04.2010 в 14:01

      Не вариант потому что символ может повторятся в очереди.

      • Сергей Елин
        22.04.2010 в 14:04

        символ == элемент. Чтобы было совсем весело представьте, что очередь из long. Любое из возможных чисел может быть в очереди, то есть не может однозначно считаться терминалом.

  1. No trackbacks yet.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s