A fifo queue in emacs lisp using a cyclic doubly linked list.

dll-fifo.el

;; FIFO queue implementation using cyclic doubly linked lists
;;
;; This data structure is a bit overkill for a queue,
;; but it has many other uses

;; a doubly linked list cell look like (val . (prev-cell next-cell))
;;
;; a FIFO queue object looks like ('fifo . cyclic-doubly-linked-list)
;;
;; An empty FIFO queue would be: ('fifo . nil)

;; example useage:
;; (let ((my-fifo (fifo '(1 2))))
;;   (print (fifo-pop my-fifo)) ;; => 1
;;   (fifo-push my-fifo 3)
;;   (print (fifo-pop my-fifo)) ;; => 2
;;   (print (fifo-pop my-fifo))) ;; => 3


(defun dll (list)
  "Create a doubly linked list with LIST's elements."
  (let* ((dll (cons (pop list) (cons nil nil)))
         (prev dll))
    (dolist (v list)
      (let ((next (cons v (cons nil nil))))
        (dll-set-next prev next)
        (dll-set-prev next prev)
        (setq prev next)))
    dll))

(defun dll-nth-node (dll n)
  "Get Nth node of the doubly linked list DLL.

N may be negative to look backwards."
  (let ((node dll))
    (dotimes (i (abs n))
      (setq node
            (if (< n 0)
                (car (cdr node))
              (cdr (cdr node)))))
    node))

(defun cyclic-dll (list)
  "Make a cyclic doubly linked list from LIST."
  (let* ((x (dll list))
         (end (dll-nth-node x (1- (length list)))))
    (dll-set-next end x)
    (dll-set-prev x end)
    x))

(defun fifo (list)
  "Create a new FIFO queue containing LIST initially."
  (let ((f (cons 'fifo nil)))
    (dolist (e list)
      (fifo-push f e))
    f))

(defun fifo-push (fifo elem)
  "Push ELEM onto the back of FIFO."
  (if (cdr-safe fifo)
      (let ((n (dll (list elem))))
        (dll-set-next (dll-prev (cdr fifo)) n)
        (dll-set-prev n (dll-prev (cdr fifo)))
        (dll-set-prev (cdr fifo) n)
        (dll-set-next n (cdr fifo))
        fifo)
    (setcdr fifo (cyclic-dll (list elem)))))

(defun fifo-pop (fifo)
  "Pop and return the first element off FIFO."
  (let ((val (car-safe (cdr-safe fifo)))
        (dll (cdr fifo)))
    (if (eql dll (dll-next dll))
        (setcdr fifo nil)
      (dll-set-next (dll-prev dll) (dll-next dll))
      (dll-set-prev (dll-next dll) (dll-prev dll))
      (setcdr fifo (dll-next dll)))
    val))

(defun fifo-length (fifo)
  "Return the number of elements in FIFO."
  (let* ((dll (cdr fifo))
         (next (dll-next dll))
         (len (if next 1 0)))
    (while (and dll next (not (eql dll next)))
      (incf len)
      (setq next (dll-next next)))
    len))