title: Queue Algorithms
body: <p>I am trying to make a linked list based queue for fast operations, now that's what i have:</p>
  
  <pre><code>template&lt; typename T, 
            template&lt; typename &gt; class Allocator = default_allocator
  &gt;
  class fast_queue
   {
   public:
    typedef T element_type;
    typedef T* element_ptr;
  
   private:
    typedef struct e_node
    {
     element_type val;
     e_node * next;
    }node_type;
    typedef node_type * node_ptr;
    node_ptr parent;
    node_ptr child;
    int      m_size;
    typedef Allocator&lt; node_type &gt; allocator_type;
  
   public:
    fast_queue()
     : parent( 0 )
     , child( 0 )
     , m_size( 0 )
    {
    }
  
    ~fast_queue() {
     this-&gt;clear();
    }
  
    void push(element_type&amp; i)
    {
     node_ptr n = allocator_type::alloc();
     n-&gt;val = i;
     n-&gt;next = (node_ptr)0;
     if(child) {
      child-&gt;next = n;
     } else {
      parent = n;
     }
     child = n;
     m_size++;
    }
  
    element_type pop()
    {
     element_type ret = parent-&gt;val;
     node_ptr p = parent;
     parent = parent-&gt;next;
     m_size--;
     allocator_type::dealloc(p);
     return ret;
    }
  
    inline int size() const 
    {
     return m_size;
    }
  
    inline bool empty() const
    {
     return (m_size == 0);
    }
  
    void clear() 
    {
     while(!empty()) {
      pop();
     }
     child = 0;
    }
   };
  </code></pre>
  
  <p>Pretty straightforward, now what i'm having a problem with is the clear() function.
  It seems to be taking way too much time deallocating all the nodes in the queue(7 seconds).
  So the question is, what might be a better algorithm? I tried to understand MSVC's implementation of std::deque but the code is so bulky for me to understand.</p>
  
  <p>EDIT:
  The queue should be generic, allowing arbitrary types of data to be queued.
  Here is my testing code (Windows)</p>
  
  <pre><code>DWORD time1 = timeGetTime();
  fast_queue&lt;int&gt; queue;
  
  for(int i = 0; i &lt; 100000; i++) {
      queue.push(i);
  }
  queue.clear();
  cout &lt;&lt; "Test time: " &lt;&lt; (int)(timeGetTime() - time1) &lt;&lt; " milliseconds" &lt;&lt; endl;
  </code></pre>