title: Implementing a more efficient queue
body: <p>I have two queue functions that transforms the queue with enqueue/dequeue, but leaves the original queue unchanged and creates a new queue with the elements removed or added.</p>
  
  <pre><code>type Queue[A] = List[A]
  
      def enqueue[A](e: A, queue: Queue[A]): Queue[A] = queue match {
      case Nil =&gt; List(e)
      case head :: tail =&gt; head :: enqueue(e, tail)
      } 
  
      def dequeue[A](queue: Queue[A]): Option[(A, Queue[A])] = queue match {
      case Nil =&gt; None()
      case head :: tail =&gt; Some((head, tail))
      }
  </code></pre>
  
  <p>However, this is an O(n) running time because it traverses the whole list. </p>
  
  <p>I would like to create a more efficient way of enqueue/dequeue. I thought that creating two lists that would represent the queue. Like <em>front</em>, which would have the elements at the front, and <em>back</em> which can have the back elements in reverse. Then the functions enqueue/dequeue would call use them instead.</p>
  
  <p>I'm looking to see if I am on the right track, or is there a more efficient way of accomplishing this? </p>