Staqueue.clj

;This week's challenge—not directly related to BFS—is to implement a queue using two stacks.

;Queues are a first-in-first-out data structure that we just saw used as a "next to visit" data store in breadth-first search.

;Stacks are a last-in-first-out data structure used in depth-first search, and can often be used to implement recursive algorithms iteratively (because the call stack is, itself, a stack).

;For this problem, you are to create a queue using two stacks. So your Queue will support the operations:

    ;enqueue(item), which inserts an item into the queue
    ;dequeue(), which removes and returns the oldest item in the queue

;Your two Stacks (which your programming language may have available already, otherwise you can create your own pretty easily) have the following operations:

    ;push(item), which inserts an item at the top of the stack
    ;pop(), which removes and returns the top item of the stack


(defprotocol Queue
  "First in First out"
  (enqueue [this el] "Adds an element to the queue")
  (dequeue [this] "Removes first added element and returns it"))


(deftype QStack [s1 s2]
  Queue
  (enqueue [this el] 
           "Empties the second stack completely onto the first one and then pushes onto the first stack
           A new QStack with an empty second stack is returned"
           (let [v1 (loop [v1 s1 v2 s2]
                      (if (seq v2) 
                        (recur (conj v1 (peek v2)) (pop v2))
                        v1))]
             (QStack. (conj v1 el) [])))
  (dequeue [this]
           "Empties the first stack completely onto the second stack and then pops the second stack
           Returns a vector containing the popped value and a new QStack with an empty first stack"
           (let [v2 (loop [v1 s1 v2 s2]
                      (if (seq v1)
                        (recur (pop v1) (conj v2 (peek v1)))
                        v2))]
             [(peek v2) (QStack. [] (pop v2))])))