Двусторонняя очередь - я переусложненный это снова?


Я работаю над реализацией двусторонняя очередь как двусвязный список (для личного обогащения), и я был интересно, если кто-единомышленников взглянуть на мой конструктор/деструктор и пустые функции, чтобы увидеть, если я на правильном пути. Она должна быть самодостаточной достаточно самостоятельно (я надеюсь).

    DeQueue::DeQueue() {
        // set up the sentinels
        head = new QueueItem();
        tail = new QueueItem();

        head->next = tail;
        tail->last = head;

        head->data = NULL;
        tail->data = NULL;
        tail->next = head->last = NULL;
    }

   DeQueue::~DeQueue() {
    QueueItem* current = head;
    QueueItem* next;
    current = current->next;
    for (;current != tail; current = current->next){
        delete current->last;
    }
    delete current;
    }

    bool DeQueue::Empty() {
        return tail->last == head;
    }

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

Редактировать: деструктор теперь движется вперед один узел, удаляет, что за этим стоит, потом движется дальше. Звучит как лучший подход?



802
7
задан 29 сентября 2011 в 07:09 Источник Поделиться
Комментарии
1 ответ

Я бы сделал так, что у вас есть только один sentanal.

Затем этот список пуст, когда головы и хвоста в один и тот же объект.

DeQueue::DeQueue()
// set up the sentinels
: head(new QueueItem()) // prefer to use initialize list.
, tail(head) // Make sure your declarations are in the correct order.
{

head->next = head; // Circular linked list.
head->last = head;

head->data = NULL; // No data in the fake node.
}

Ваш цикл удаления на самом деле не двигаться:

while(current->next != head)
{
delete current->next; // your deleting the element
// But not moving the the current item
// So the loop will not exit.
}

DeQueue::~DeQueue()
{
// Delete from the head.
// Just slowly loop over the nodes deleting them as you go
while(head != tail)
{
QueueItem* old = head;
head = head->next;

delete old;
}
// Delete the sentanal object created in the constructor.
delete tail;
}

// Simplify empty.
bool DeQueue::Empty()
{
return tail == head;
}

4
ответ дан 29 сентября 2011 в 08:09 Источник Поделиться