Очередь в виде двусвязного списка.

[dimorik]

Друзья, просветите пожалуйста может ли очередь быть задана в виде двусвязного списка? Как это? Я без проблем могу реализовать как очередь так и двусвязный список в отдельности, но чтоб очередь в виде двусвязного списка - не понимаю как это. Может кто знает. Подскажите....

[ozo]

Конечно же может :

Queue{
 public:
  void Push( int value ){
    list.push_back( value );
  }
  int Pop(){
    int result = *list.begin();
    list.erase( list.begin() );
    return result;
  }
 protected:
  std::list< int > list;
};

И да, шаблоны наше всё, но для примера сойдёт

[dimorik]

Спасибо.. буду разбираться.. а еще примеры есть с коментариями?

[MadReason]

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

[MaTBeu]

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

[MadReason]

так не сказано что в каждом узле

будет указатель не только на следующий, а и на предыдущий узел

поэтому можно на "крайние" элементы поставить заглушки в виде NIL. либо хранить их адреса в переменных предназначенных для этого, если писать в виде класса, то будет даже симпатично смотреться

[MaTBeu]

Сообщение от MadReason

так не сказано что в каждом узле

поэтому можно на "крайние" элементы поставить заглушки в виде NIL. либо хранить их адреса в переменных предназначенных для этого, если писать в виде класса, то будет даже симпатично смотреться

Собственно, а что вы думаете представляет собой двухсвязный список?

[MadReason]

"кучку" элементов, каждый из которых содержит блок данных и два указателя на соседние элементы. разве я не прав?
разница в том что можно его сделать кольцевым или линейным, о чем я тоже уже говорил

[MaTBeu]

Кольцевой список может быть и односвязным и двухсвязным, как и линейный. Если говорят про связность списков, то имеют ввиду количество ссылок у каждого узла списка.

[MadReason]

"кучку" элементов, каждый из которых содержит блок данных и два указателя на соседние элементы. разве я не прав?
разница в том что можно его сделать кольцевым или линейным, о чем я тоже уже говорил

p.s.
сори за флуд, я не удержался от этого сообщения (