Last active
August 29, 2015 13:56
-
-
Save joelittlejohn/9296517 to your computer and use it in GitHub Desktop.
The Staqueue, Coding for Interviews Issue #20
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; 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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment