Scheme中栈(Stack)的实现

DeathKing posted @ 2013年11月06日 22:18 in Scheme with tags Scheme lisp stack data structure 数据结构 , 1895 阅读

最近在学习《数据结构与算法分析》,由于老师是用C语言授课,而C语言实现各种数据结构和算法早就已经被写烂了。恰巧在学习Scheme,就试下如何用Scheme来实现这些数据结构和算法。

一个优雅的实现

下面的这段代码是坦佩雷理工大学的Juha Heinanen教授或者是Pertti Kellom教授编写的,看到下面的代码,我基本上没有再实现一次的欲望了。这个博文,就姑且来剖析一下这段代码是如何实现栈的。

;;;;
;;;; A stack implementation.
;;;;

(define (make-stack) 
  (define stack '()) 
  (define (empty?) (null? stack)) 

  (define (top) 
    (if (null? stack) 
        (error "Stack is empty -- TOP"
               stack) 
        (car stack))) 

  (define (push! object) 
    (set! stack (cons object stack)) 
    object) 

  (define (pop!) 
    (if (null? stack) 
        (error "Stack underflow -- POP!"
               stack) 
        (let ((object (car stack))) 
          (set! stack (cdr stack)) 
          object))) 

  (define (dispatch op . args) 
    (case op 
      ((empty?) (apply empty? args)) 
      ((top) (apply top args)) 
      ((push!) (apply push! args)) 
      ((pop!) (apply pop! args)) 
      (else 
        (error "Unknown stack operation --"
          " DISPATCH" op)))) 
  dispatch) 

栈内容

(define stack '()) 

栈内容是一个状态量。在这个实现中,变量stack代表了栈内容。最初,栈为空,故stack与空表`()进行了绑定。

谓词:栈是否为空

(define (empty?) (null? stack)) 

简单判断stack是否为空表即可。

元素入栈

(define (push! object) 
  (set! stack (cons object stack)) 
  object)

注意这个操作需要改变状态量,也就是因为引入了赋值而带来了副作用。函数push!会将新入栈元素和原栈堆给cons起来,并让新入栈的元素作为car部分,这是为了方便后面的出栈操作。

元素入栈操作push!返回新入栈的元素。

元素弹出

(define (pop!) 
  (if (null? stack) 
      (error "Stack underflow -- POP!"
              stack) 
      (let ((object (car stack))) 
         (set! stack (cdr stack)) 
         object))) 

显然空表无法弹出。为了弹出栈顶元素,首先先让一个局部变量obejectstackcar部分绑定(注意到stackcar部分就是栈顶元素),然后再将stack赋值为原stackcdr部分,再返回局部变量object,这就实现了元素的弹出。

返回栈顶元素

(define (top) 
  (if (null? stack) 
      (error "Stack is empty -- TOP"
             stack) 
      (car stack))) 

注意到栈顶元素就是stackcar部分,实现top过程就非常容易了。这个过程甚至不涉及到任何状态操作。

消息分派(实现面向对象机制)

(define (dispatch op . args) 
  (case op 
    ((empty?) (apply empty? args)) 
    ((top) (apply top args)) 
    ((push!) (apply push! args)) 
    ((pop!) (apply pop! args)) 
    (else 
      (error "Unknown stack operation --"
             " DISPATCH" op))))

这个stack实现最妙的部分就在此处。dispatch函数实现了一个简单但是有效的面向对象编程机制,对堆栈的操作实质上是对这个dispatch发送了一个“消息”,dispatch中得case来判断执行什么操作。

由于Scheme的闭包性,它的状态量(OO中的成员变量)和操作函数(OO中的方法)都封装在一个黑盒子中(其实一个lambda就是一个context),非常美妙。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter