关于双端结构的更多信息,可以参考维基百科的 Double-ended queue 词条 或者任何一本算法/数据结构书籍。
以下是双端队列的实现:
;;; 23-deque.scm
; ptr selector
(define (front-ptr deque)
(car deque))
(define (rear-ptr deque)
(cdr deque))
; ptr setter
(define (set-front-ptr! deque item)
(set-car! deque item))
(define (set-rear-ptr! deque item)
(set-cdr! deque item))
; deque constructor
(define (make-deque)
(cons '() '()))
; deque selector
(define (empty-deque? deque)
(null? (front-ptr deque)))
(define (front-deque deque)
(if (empty-deque? deque)
(error "FRONT-DEQUE called with an empty deque" deque)
(car (front-ptr deque))))
(define (rear-deque deque)
(if (empty-deque? deque)
(error "REAR-DEQUE called with an empty deque" deque)
(car (rear-ptr deque))))
; deque setter
(define (insert-rear-deque! deque item)
(let ((new-pair (cons item '())))
(cond ((empty-deque? deque)
(set-front-ptr! deque new-pair)
(set-rear-ptr! deque new-pair)
deque)
(else
(set-cdr! (rear-ptr deque) new-pair)
(set-rear-ptr! deque new-pair)
deque))))
(define (delete-front-deque! deque)
(cond ((empty-deque? deque)
(error "DELETE-FRONT-DEQUE! called with an empty deque" deque))
(else
(set-front-ptr! deque (cdr (front-ptr deque)))
deque)))
(define (insert-front-deque! deque item)
(cond ((empty-deque? deque)
(insert-rear-deque! deque item))
(else
(set-front-ptr! deque (cons item (front-ptr deque)))
deque)))
(define (delete-rear-deque! deque)
(define (iter deque lst)
(cond ((null? (cdr (cdr lst)))
(set-cdr! lst '())
(set-rear-ptr! deque lst)
deque)
(else
(iter deque (cdr lst)))))
(cond ((empty-deque? deque)
(error "DELETE-REAR-DEQUE! called with an empty deque" deque))
((null? (cdr (front-ptr deque))) ; 长度等于 1
(set-front-ptr! deque '())
deque)
(else
(iter deque (front-ptr deque))))) ; 长度大于 1
;
(define (print-deque deque)
(car deque))
测试:
1 ]=> (load "23-deque.scm")
;Loading "23-deque.scm"... done
;Value: delete-rear-deque!
1 ]=> (define q (make-deque)) ; 创建队列
;Value: q
1 ]=> (insert-front-deque! q 2) ; 插入三个元素
;Value 11: ((2) 2)
1 ]=> (insert-front-deque! q 1)
;Value 11: ((1 2) 2)
1 ]=> (insert-rear-deque! q 3)
;Value 11: ((1 2 3) 3)
1 ]=> (print-deque q)
;Value 12: (1 2 3)
1 ]=> (delete-front-deque! q) ; 从前端删除
;Value 11: ((2 3) 3)
1 ]=> (print-deque q)
;Value 13: (2 3)
1 ]=> (delete-rear-deque! q) ; 从后端删除
;Value 11: ((2) 2)
1 ]=> (print-deque q)
;Value 13: (2)
1 ]=> (empty-deque? q) ; 空队列测试
;Value: #f
1 ]=> (delete-rear-deque! q)
;Value 11: (() 2)
1 ]=> (empty-deque? q)
;Value: #t
前面的双端队列实现虽然能满足功能上的目的,但是它不符合题目『所有操作都必须在 \(\Theta(1)\) 步内完成』的要求,因为在 delete-rear-deque!
过程中,使用了一个 \(\Theta(n)\) 步的遍历操作。
为了让所有操作的复杂度都能达到 \(\Theta(1)\) ,需要修改双端队列的底层实现,从原来的单链表(single linked list)表示改为双链表(double linked list)表示。
首先实现双链表:
;;; 23-double-linked-list.scm
(define (make-double-linked-list)
'())
(define (empty-double-linked-list? lst)
(null? lst))
(define (insert-double-linked-list! lst item)
(cond ((empty-double-linked-list?)
(set! lst (make-node item '() '()))
lst)
(else
测试:
:wq