6.001 recitation 11 3/21/07 stack, queue problemsDr. Kimberle Koile 2We'll implement stacks and queues using the ADT, mutable-list, described in the accompanyinghandout. Here's an example.(let* ((e (make-element 4)) (x (make-mutable-list e e)))x)(add-to-front! x 5)stacks and queuesUsing the procedures for a new data type called mutable-list, provided in the accompanyinghandout, write the following procedures.stack and queue problems1. Define set-last! which modifies the first or last pointers of a mutable-list to point at the new elements. set-first! is defined for you. (Recall that the car of a mutable-list is a tag, so the first list element is actually the cadr.) (define (set-first! m-l e) ;; type: mutable-list, <element|null> unspecified (if (mutable-list? m-l) (set-car! (cdr m-l) e) (error "not a mutable list"))) (define (set-last! m-l e) ;; type: mutable-list, <element|null> unspecifiedstack and queue problems2. Define set-prev! and set-next! that change the prev or next field of a mutable-element. (define (set-prev! element prev) ;; type: element, <element|null> unspecified (define (set-next! element next) ;; type: mutable-list, <element|null> unspecifiedstack and queue problems3. Complete the definition for add-to-front! which takes any value and adds a new element tothe front of the list containing that value. Then define add-to-back! which does the same for theback of the list. (define (add-to-front! lst item) ;; type: mutable-list A unspecified (let ((e (make-element item))) (cond ((not (mutable-list? lst)) (error "not a mutable list")) ((empty-mutable-list? lst) (set-first! lst e) (set-last! (define (set-next! element next) ;; type: mutable-list, <element|null> unspecifiedstack and queue problems4. Complete the definition for add-to-front! which takes any value and adds a new elementcontaining that value to the front of the list. (define (add-to-front! lst item) ;; type: mutable-list A unspecified (let ((e (make-element item))) (cond ((not (mutable-list? lst)) (error "not a mutable list")) ((empty-mutable-list? lst) (set-first! lst e) (set-last! lst e)) (elsestack and queue problems5. Write add-to-back! which takes any value and adds a new element containing that value tothe back of the list. (define (add-to-back! lst item) ;; type: mutable-list A unspecifiedstack and queue problems6. Complete the definition for remove-from-back! which removes the last element and returns it. (define (remove-from-back! lst) ;; type: mutable-list A (let ((e (make-element item))) (cond ((not (mutable-list? lst)) (error "not a mutable list")) ((empty-mutable-list? lst) (error "list is empty")) ((single-entry? lst)stack and queue problems7. Write remove-from-front! which removes the first element and returns it. (define (remove-from-front! lst) ;; type: mutable-list Astack and queue problems8. Write push! and pop! to use the mutable list as a stack.9. Write enqueue! and dequeue! to use the mutable list as a queue.stack and queue problems10. Using either a stack or a queue (or both!) define a procedure rpn-calc that takes asimple arithmetic expression in postfix notatino and evaluates it. You may assume aprocedure list->mutable-list which takes a Scheme list and returns the correspondingdoubly-linked list.e.g. (rpn-calc '(1 2 +) 3 (rpn-calc '(5 1 2 + - 10 + 6 / 3 *)) 6stack and queue problems11. Can you define rpn-calc without using any mutating
View Full Document
Unlocking...