; two stacks make a queue

(define sEmpty (list))
(define (sPush s x) (cons x s))
(define (sHead s) (if (null? s) (error 'sHead "oops") (car s)))
(define (sTail s) (if (null? s) (error 'sTail "oops") (cdr s)))
(define (sEmpty? s) (null? s))

(define qEmpty
  (let ((s1 sEmpty) (s2 sEmpty))
    (cons s1 s2)))

(define (enQueue q x)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cons (sPush s1 x) s2)))

(define (qHead q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cond ((and (sEmpty? s1) (sEmpty? s2))
            (error 'qHead "oops"))
          ((sEmpty? s2)
            (let loop ((s1 s1) (s2 s2))
              (if (sEmpty? s1)
                  (sHead s2)
                  (loop (sTail s1) (sPush s2 (sHead s1))))))
          (else (sHead s2)))))

(define (qTail q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cond ((and (sEmpty? s1) (sEmpty? s2))
            (error 'qHead "oops"))
          ((sEmpty? s2)
            (let loop ((s1 s1) (s2 s2))
              (if (sEmpty? s1)
                  (cons s1 (sTail s2))
                  (loop (sTail s1) (sPush s2 (sHead s1))))))
          (else (cons s1 (sTail s2))))))

(define (qEmpty? q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (and (null? s1) (null? s2))))

(define q qEmpty)
(set! q (enQueue q 1))
(set! q (enQueue q 2))
(display (qHead q)) (newline)
(set! q (qTail q))
(set! q (enQueue q 3))
(display (qHead q)) (newline)
(display (qEmpty? q)) (newline)
(set! q (qTail q))
(display (qHead q)) (newline)
(set! q (qTail q))
(display (qEmpty? q)) (newline)

1
2
#f
3
#t