;;;
;;; A naive implementation of stack.
;;; (all operations have constant time complexity)
;;;
;;; A stack is modeled as a list of elements,
;;; with both insertion and removal performed
;;; on one end of the list.
;;;
(defun make-stack ()
"Create an empty stack."
nil)
(defun stack-empty-p (S)
"Check if stack S is empty."
(null S))
(defun stack-top (S)
"Top element of stack S."
(first S))
(defun stack-push (S X)
"Push X into stack S."
(cons X S))
(defun stack-pop (S)
"Pop stack S."
(rest S))
;;;
;;; A naive implementation of priority queue
;;; (insertion has linear time complexity)
;;;
;;; A priority queue is modeled as a list of pairs.
;;; The first component of each pair is a key value,
;;; while the second is an element.
;;;
(defun make-priority-queue ()
"Create an empty priority queue."
nil)
(defun priority-queue-empty-p (Q)
"Check if priority queue Q is empty."
(null Q))
(defun priority-queue-top (Q)
"Return the element in priority queue Q with the lowest key value."
(second (first Q)))
(defun priority-queue-remove (Q)
"Remove the lowest-key element from priority queue Q."
(rest Q))
(defun priority-queue-insert (Q X K)
"Insert element X with key value K into priority queue Q."
(if (and (not (null Q)) (<= (first (first Q)) K))
(cons (first Q) (priority-queue-insert (rest Q) X K))
(cons (list K X) Q)))