title: How to destroy a queue efficiently?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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)?</p>
  
  <p>Here's the code of the destructor of my_queue:</p>
  
  <pre><code>/*
  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-&gt;next;
          delete temp;
      }
      sz = 0;
      tail = NULL;
  }
  </code></pre>