title: How to reverse a queue recursively?
body: <p>I have the following class template and I wish to implement the reverse() function recursively without using any external/additional data structures.   </p>
  
  <pre><code>template &lt;class T&gt; struct Node {
  T value; Node&lt;T&gt; ∗next;
  };
  template &lt;class T&gt; class Dynque
  {
  protected :
   Node&lt;T&gt; ∗front;
   Node&lt;T&gt; ∗rear;
  int numItems ; public :
  Dynque();
  Dynque ( Dynque &amp; ) ;
  virtual  ̃Dynque ( ) ;
  virtual void enqueue (T) ; // add an element
  T dequeue();// remove an element from front
  bool isEmpty ( ) ;
  int getNumItems ( ) ;
  void clear (); // remove all elements
  void reverse(); // reverse order of elements
  };
  </code></pre>