如何有效地销毁队列？

Question

我实现了自己的队列数据结构。我使用单向链接列表实现了队列。并在类定义中实现。链接列表的头指向队列的前面，链接列表的尾部指向队列的末尾。注意，我保留尾巴只是为了在O(1)时间内执行推送操作。

现在，类的push函数动态地为值分配内存，然后将其推送到列表的末尾。pop函数释放分配给前面值的内存。

当队列被解构时(超出作用域)，我想释放分配的内存，因此我为队列编写了一个析构函数。我的析构函数遍历整个链接列表并删除链接列表中的每个元素。它的时间复杂度是O(n)。有没有办法降低队列的时间复杂度？在O(1)中是否有可能销毁队列？如果我只取消了链表的头目，链表的其余部分便不会被删除，而由于总目会被删除，便没有办法删除链表的其他元素。如何实现STL队列的析构函数？它会破坏O(1)或O(n)中的整个队列吗？

下面是my_queue的析构函数的代码：

/*
Node is a struct which is the nodes of the linked list.
It has two attributes: val(of type char) and next(of type node*)
*/
my_queue :: ~my_queue(){
    node * temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        delete temp;
    }
    sz = 0;
    tail = NULL;
}

Answer 1

在O(1)中是否有可能销毁队列？

如果您打算继续使用链接列表，则不会。O(n)是销毁链表(或任何基于节点的数据结构)的最优渐近复杂度。

如果使用非平凡的析构函数存储对象，也不会。不能在恒定时间内调用N个析构函数。

如果您选择另一个数据结构来实现您的队列，那么也许。一个动态增长的阵列(即向量)可以在恒定时间内销毁，如果元素是微不足道的破坏。

如何实现STL队列的析构函数？它会破坏O(1)或O(n)中的整个队列吗？

std::queue只是一个低级容器的包装器。它的析构函数只会破坏您选择的底层容器。不管容器的析构函数有多复杂，它的复杂性都是什么。对于任何具有非平凡析构函数的对象容器，对于所有std::deque或std::list，对于具有平凡析构函数的元素的std::vector，O(1)。

在这里，通过调用free或任何释放内存的方法来减少复杂性。free本身的复杂性可能不能保证是恒定的。