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)))))
Hackerrank a tale of two stacks
Hackerrank a tale of two stacks
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)))))