Hackerrank a tale of two stacks

Challenge

Solution

Custom implementation of a queue. I use a doubly linked list and maintain the front and the back fields of the queue.

;; TOC: >1h
;; Complexity of pop, push and peek: O(1)
(definterface IQueueNode
  (getdata [])
  (getnext [])
  (getprev [])
  (setdata [node-data])
  (setnext [next-ptr])
  (setprev [prev-ptr]))

(deftype QueueNode [^:volatile-mutable data ^:volatile-mutable next ^:volatile-mutable prev]
  IQueueNode
  (getdata [_] data)
  (getnext [_] next)
  (getprev [_] prev)
  (setnext [_ next-ptr] (set! next next-ptr))
  (setprev [_ prev-ptr] (set! prev prev-ptr)))

(definterface IQueue
  (qpush [data])
  (qpop [])
  (qpeek []))

(deftype Queue [^:volatile-mutable front ^:volatile-mutable back]
  IQueue
  (qpush [this new-data]
    (if front
      (let [new-node (QueueNode. new-data back nil)]
        (.setprev back new-node)
        (set! back new-node))
      (let [new-node (QueueNode. new-data nil nil)]
        (set! front new-node)
        (set! back new-node))))
  (qpop [_] (set! front (.getprev front)))
  (qpeek [_] (.getdata front)))


(def q (Queue. nil nil))


(require 'clojure.string)

(dotimes [i (Integer. (read-line))]
  (let [input (map #(Integer. %) (clojure.string/split (read-line) #" "))]
    (case (nth input 0)
      1 (.qpush q (nth input 1))
      2 (.qpop q)
      3 (println (.qpeek q)))))