Double-Ended Queue: это звуковая реализация "добавить вперед"?

Question

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

void DeQueue::PushFront(void* item) {
    QueueItem* temp = new QueueItem();
    temp->data = item;
    // Insert the item between the head and the head's next item.
    if (Empty()) {
        head->next = temp;
        tail->last = temp;
        temp->next = tail;
        temp->last = head;
    } else {
        temp->next = head->next;
        temp->last = head;
        head->next->last = temp;
        head->next = temp;
    }
}

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

РЕДАКТИРОВАТЬ: Чтобы избежать путаницы, я знаю, что это было сделано для меня в стандартной библиотеке.Я делаю это как способ научить себя нескольким вещам о языке.

РЕДАКТИРОВАТЬ: Кажется, у меня есть идея.Теперь интересная проблема:

void* DeQueue::PopFront() {
    if (Empty()) return NULL;  // should throw exception instead.
    void* temp = head->next->data;
    head->next->next->last = head;
    head->next = head->next->next;
    // now my node is gone... How do i free the memory
    // of something I've lost the reference to?
    return temp;
}

Answer 1

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

Что касается второго вопроса, чтобы выскочить из списка, вам просто нужно сохранить указатель на узел и вызвать на нем delete, прежде чем вернуться из функции.

Кроме того, вы можете рассмотреть вопрос о разделении проблемы обучения: используйте умные указатели для управления своими ресурсами и изучения алгоритмов, а затем изучите управление памятью (или наоборот)

Answer 2

Ответ на второе редактирование: Вы не можете. Вам придется сохранить ссылку на него.

void* DeQueue::PopFront() {
    if (Empty()) 
        throw logic_error("stack is empty");

    QueueItem* deleteme = head->next; //get node
    void* temp = deleteme->data;

    deleteme->next->last = head;
    head->next = deleteme->next;

    delete deleteme; //delete node
    return temp;
}

Answer 3

Кажется с этим

if (Empty()) {
    head->next = temp;
    tail->last = temp;
    temp->next = tail;
    temp->last = head;

Вы полагаете, что голова и хвост уже указывают на что-то, когда очередь пуста?