6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 11.2.4 Stack Implementation Strategy Having defined a set of operations on our abstraction, and a contract on the behavior of the abstraction and its associated operations, we can actually implement this aDt. Our first strategy will be to treat a stack as a list 6 001 SICP Slide 11. 2.5 Stack Implementation Strategy For example, this list could represent a stack, where a is the implement a stack as a list most recent thing pushed onto the stack, with earlier pushed elements consecutively arrayed down the list Then to insert and delete elements from the stack, we simply iHiv add things to the front of the list, or take the cdr of the list we will insert and delete items off the front of the stack Stack Implementation Slide 11.2.6 So here is an implementation that uses lists to incorporate this idea. Note how the constructor and predicate simply build on (define (empty-stack? stack) (nu11? stack)) the underlying use of a list (define (insert stack elt) (cons elt stack) Insertion simply conses a new element onto the existing stack E《emty-t (or list), returning a new list with that element at the top of the tack underflow delete) stack(or front of the list) Notice the defensive programming used for deletion or checking the top, in which we ensure we have a legal structure error stack underflow -top") before attempting to access the list structure. If we do, then we either use car to get a pointer to the first element, or we cdr to get a pointer to everything but the first element Check to convince yourself that the contract holds for stacks, by building on the contract for list operations6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 11.2.4 Having defined a set of operations on our abstraction, and a contract on the behavior of the abstraction and its associated operations, we can actually implement this ADT. Our first strategy will be to treat a stack as a list. Slide 11.2.5 For example, this list could represent a stack, where a is the most recent thing pushed onto the stack, with earlier pushed elements consecutively arrayed down the list. Then to insert and delete elements from the stack, we simply add things to the front of the list, or take the cdr of the list. Slide 11.2.6 So here is an implementation that uses lists to incorporate this idea. Note how the constructor and predicate simply build on the underlying use of a list. Insertion simply conses a new element onto the existing stack (or list), returning a new list with that element at the top of the stack (or front of the list). Notice the defensive programming used for deletion or checking the top, in which we ensure we have a legal structure before attempting to access the list structure. If we do, then we either use car to get a pointer to the first element, or we use cdr to get a pointer to everything but the first element. Check to convince yourself that the contract holds for stacks, by building on the contract for list operations