The Staqueue, Coding for Interviews Issue #20

staqueue.clj

;; Building a functional queue using two stacks

;; We'll use vectors for our stacks, 'push' == conj
(def ^:private push conj)

;; We'll need be able to fill one stack from another
(defn ^:private refill
  [s1 s2]
  (if (empty? s1)
    s2
    (recur (pop s1) (push s2 (peek s1)))))

;; A functional queue needs three operations:
;; - enqueue, add an item to the back of the queue
;; - dequeue, remove an item from the front of the queue
;; - front, see what's at the front of the queue
(defprotocol Queue
  (enqueue ^Queue [this x])
  (dequeue ^Queue [this])
  (front [this]))

;; Here's a functional queue implemented with two stacks
(defrecord StackBasedQueue [s1 s2]
  Queue
  (enqueue [this x]
    (update-in this [:s1] push x))
  (dequeue [this]
    (cond (seq s2) (StackBasedQueue. s1 (pop s2))
          (seq s1) (StackBasedQueue. [] (pop (refill s1 s2)))
          :else this))
  (front [this]
    (peek (if (empty? s2) (refill s1 s2) s2))))

(defn squeue []
  "Creates an empty stack-based queue"
  (->StackBasedQueue [] []))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Let's give our queue a try

(squeue)
;;=> #queue.StackBasedQueue{:s1 [], :s2 []}

;; Add an item to a queue
(enqueue (squeue) :a)
;;=> #queue.StackBasedQueue{:s1 [:a], :s2 []}

;; Add a few items to a shopping list
(def shopping
  (-> (squeue) (enqueue :eggs) (enqueue :bread) (enqueue :milk)))
;;=> #'queue/shopping

;; What's the state of our stacks?
shopping
;;=> #user.StackBasedQueue{:s1 [:eggs :bread :milk], :s2 []}
;;
;; enqueue stack has all of our items, dequeue stack hasn't yet been used

;; Which item is at the front of the queue?
(front shopping)
;;=> :eggs

;; Say we bought eggs, lets remove them from the queue
(def shopping
  (dequeue shopping))
;;=>#'queue/shopping

;; Which item is at the front of the queue now?
(front shopping)
;;=> :bread

;; What's the state of our stacks now?
shopping
;;=> #user.StackBasedQueue{:s1 [], :s2 [:milk :bread]}
;;
;; enqueue stack is empty since items were transferred to the dequeue stack

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Now for some timing

;; Let's build a queue of 10,000 integers
(def q1 (reduce enqueue (squeue) (range 10000)))

;; The first dequeue is expensive since we need to fill the dequeue stack
(dotimes [_ 5]
  (time (dotimes [_ 100]
          (dequeue q1))))
;;"Elapsed time: 377.974372 msecs"
;;"Elapsed time: 177.143243 msecs"
;;"Elapsed time: 176.567245 msecs"
;;"Elapsed time: 174.074123 msecs"
;;"Elapsed time: 172.318019 msecs"

(def q2 (dequeue q1))

;; The second dequeue is cheap (pop straight off the dequeue stack)
(dotimes [_ 5]
    (time (dotimes [_ 100]
            (dequeue q2))))
;;"Elapsed time: 0.118309 msecs"
;;"Elapsed time: 0.02452 msecs"
;;"Elapsed time: 0.018881 msecs"
;;"Elapsed time: 0.018625 msecs"
;;"Elapsed time: 0.018744 msecs"