;;;
;;; 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)))