Clojure swap! atom dequeuing

(defn dequeue!
  [queue]
  (loop []
    (let [q     @queue
          value (peek q)
          nq    (pop q)]
      (if (compare-and-set! queue q nq)
        value
        (recur)))))

(def queue (atom clojure.lang.PersistentQueue/EMPTY))
(swap! queue conj :foo)
(swap! queue conj :bar)
(seq @queue)
(dequeue! queue)
(seq @queue)

Using ref would be a simpler option:

(defn dequeue!
  "Given a ref of PersistentQueue, pop the queue and change the queue"
  [queue-ref]
  (dosync
    (let [val (peek @queue-ref)]
      (alter queue-ref pop)
      val)))

(let [q (ref clojure.lang.PersistentQueue/EMPTY)]
           (dosync (alter q conj 1 2 3)
                   (alter q conj 5))
           (fu/dequeue! q)
           => 1
           (seq @q)
           => (2 3 4 5))