queue.clj

(definterface INode
  (getNext [])
  (setNext [n])
  (getPrev [])
  (setPrev [n]))

(deftype Node
  [data
   ^:unsynchronized-mutable prev
   ^:unsynchronized-mutable next]
  INode
  (getNext [_] next)
  (setNext [_ n] (set! next n))
  (getPrev [_] prev)
  (setPrev [_ p] (set! prev p)))

(definterface IQueue
  (pop [])
  (push [v]))

(deftype Queue
  [^:unsynchronized-mutable ^INode head
   ^:unsynchronized-mutable ^INode tail]
  IQueue
  (pop [_]
    (when-let [n tail]
      (let [prev (.getPrev n)]
        (set! tail prev)
        (when (= n head)
          (set! head prev))
        (.data n))))

  (push [_ v]
    (if-not head
      (let [n (Node. v nil nil)]
        (set! head n)
        (set! tail n))
      (let [n head n' (Node. v nil n)]
        (.setPrev n n')
        (set! head n')))))