33 lines
957 B
Racket
33 lines
957 B
Racket
#lang racket
|
|
;; Invariants:
|
|
;; The elements in the queue are (append front (reverse back)).
|
|
;; Front is always non-empty (except for the empty queue).
|
|
(struct queue (front back))
|
|
|
|
(define empty (queue '() '()))
|
|
|
|
(define (push x q)
|
|
(if (null? (queue-front q))
|
|
(queue (reverse (cons x (queue-back q))) '())
|
|
(queue (queue-front q) (cons x (queue-back q)))))
|
|
|
|
(define (empty? q)
|
|
(null? (queue-front q)))
|
|
|
|
(define (pop q)
|
|
(cond [(empty? q) (error 'pop "the queue is empty")]
|
|
[(not (null? (queue-front q)))
|
|
(if (null? (rest (queue-front q)))
|
|
(queue (reverse (queue-back q)) '())
|
|
(queue (rest (queue-front q)) (queue-back q)))]
|
|
[else (queue (reverse (queue-back q)) '())]))
|
|
|
|
(define (first q)
|
|
(cond [(empty? q) (error 'first "the queue is empty")]
|
|
[(car (queue-front q))]))
|
|
|
|
;; Example:
|
|
(first (pop (pop (for/fold ([q empty]) ([x '(1 2 3 4)])
|
|
(push x q)))))
|
|
;; => 3
|