How to destroy a queue efficiently?

Question

I implemented a queue data structure of my own. I implemented the queue using unidirectional linked list. And it is implemented in a class definition. The head of the linked list is pointing to the front of the queue and the tail of the linked list is pointing to the end of the queue. Note, I kept the tail only to make the push operation in O(1) time.

Now the push function of the class dynamically allocates memory for a value and then pushes it to the end of list. And the pop function frees the memory allocated for the value at the front.

When the queue is being destructed (Goes out of the scope) I wanted to free the allocated memory, and so I wrote a destructor for the queue. My destructor traverses the whole linked list and deletes each element of the linked list. The time complexity of this is O(n). Is there any way to reduce the time complexity of the queue? Is it possible to destroy the queue in O(1)? If I had only deallocated the head of the linked list, the rest elements of the linked list will not be deleted, and as the head will be deleted, there will be no way to delete the other elements of the linked list. How is the STL queue's destructor is implemented? Does it destroys the whole queue in O(1) or O(n)?

Here's the code of the destructor of 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;
}

If you use a linked list I think O(N) is the best you can get. If you implement it over something similar to a `std::vector` you can get O(1) amortized for push and pop and O(1) free as well. — Winestone, Apr 21 '17 at 08:28
@Winestone for any non-trivial value_type, vector destruction will be O(N). If you have n objects, you need n calls to the destructor. — juanchopanza, Apr 21 '17 at 08:31
@juanchopanza You are correct, I assumed a queue of `int`'s or something. — Winestone, Apr 21 '17 at 08:32
I think it takes as long as a single free call, which takes something like [this](http://stackoverflow.com/questions/282926/time-complexity-of-memory-allocation) much time — Winestone, Apr 21 '17 at 08:54

eerorika · Accepted Answer · 2017-04-21T10:48:27.407

Is it possible to destroy the queue in O(1)?

Not if you intend to keep using a linked list. O(n) is optimal asymptotic complexity for destruction of a linked list (or any node based data structure).

Also not if you store objects with non-trivial destructors. You cannot call N destructors in constant time.

If you choose another data structure to implement your queue, then perhaps. A dynamically growing array (i.e. a vector) can be destroyed in constant time, if the elements are trivially destructible.

How is the STL queue's destructor is implemented? Does it destroys the whole queue in O(1) or O(n)?

std::queue is just a wrapper for a lower level container. Its destructor simply destroys the underlying container, that you have chosen. The complexity is whatever the complexity of that container's destructor is. O(n) for any container of objects with non-trivial destructor, and for all std::deque or std::list, O(1) for std::vector of elements with trivial destructor.

Here, the complexity is descibed in terms of calls to free or whatever deallocates the memory. The complexity of free itself might not be guaranteed to be constant.

How to destroy a queue efficiently?

1 Answers1