Skip to content

Instantly share code, notes, and snippets.

@asethia

asethia/QueueViaStacks.scala

Created July 30, 2018 19:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save asethia/e46f4938109bc72cbdeabd2f56c7c5bb to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save asethia/e46f4938109bc72cbdeabd2f56c7c5bb to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. asethia created this gist Jul 30, 2018.
    28 changes: 28 additions & 0 deletions QueueViaStacks.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,28 @@
    /**
    * Implement a MyQueue class which implements a queue using two stacks.
    * Time Complexity
    * Enqueue O(1), DeQueue O(n) if dequeue called after each enqueue
    * Space complexity O(n)
    * Created by Arun Sethia on 7/30/18.
    */
    case class QueueViaStacks(stack: List[Int], queue: List[Int] = Nil) {

    def enQueue(elem: Int) = QueueViaStacks(elem :: stack, queue)

    def deQueue() = {
    queue match {
    case Nil if (!stack.isEmpty) => {
    val newQueue = stack.foldLeft(List.empty[Int])((a, b) => b :: a)
    println(s"dequeue :${newQueue.head}")
    QueueViaStacks(Nil, newQueue.tail)
    }
    case Nil if (stack.isEmpty) => {
    throw new UnsupportedOperationException("queue is empty")
    }
    case h :: _ => {
    println(s"dequeue ${h}")
    QueueViaStacks(stack, queue.tail)
    }
    }
    }
    }