Fundamentals of Computer Science 1 (CS151 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
An abstract data type is a set of values and operations on those values, considered independently of the ways in which those values might be represented and the operations implemented in actual programs. Separating the definition of an abstract data type from its implementation is a technique that has been found to be especially useful in the development of large software systems.
Objects produced by a constructor procedure, such as the switches in the readingon objectoriented programming, can often be developed efficiently from the definition of an abstract data type, with the advantage that other procedures that take such objects as arguments cannot operate on them or modify them in any way not considered by the definition of the abstract data type. As a result, the methods of such an object can often be implemented in such a way as to preserve certain simplifying invariants  conditions that are known to be true at the beginning and end of the execution of each method. Relying on such invariants often allows the programmer to dispense with some precondition tests in the methods, because the invariants imply that the preconditions will be met whenever the method is called.
As illustrations of the use of abstract data types in the development of programs, we consider a frequently encountered data structures that Scheme happens not to supply: the stacks.
Conceptually, the stack abstract data type mimics the information kept in a pile on a desk. Informally, we first consider materials on a desk, where we may keep separate stacks for bills that need paying, magazines that we plan to read, and notes we have taken. We can perform several operations that involve a stack:
These operations allow us to do all the normal processing of data at a desk. For example, when we receive bills in the mail, we add them to the pile of bills until payday comes. We then take the bills, one at a time, from the top of the pile and pay them until the money runs out.
When discussing these operations, it is conventional to call the addition of an item to the top of the stack a push operation and the deletion of an item from the top a pop operation. (These terms are derived from the workings of a springloaded rack containing a stack of cafeteria trays. Such a rack is loaded by pushing the trays down onto the springs; as each diner removes a tray, the lessened weight on the springs causes the stack to pop up slightly.)
Here is a more formal definition of the stack ADT: A stack is a data structure containing zero or more elements, on which the following operations can be performed:
This abstract data type definition says nothing about how we will program the various stack operations; rather, it tells us how stacks can be used. We can infer some limitations on how we can use the data. For example, stack operations allow us to work with only the top item on the stack. We cannot look at elements farther down in the stack without first using pop operations to clear away items above the desired one.
A push operation always puts the new item on top of the stack, and this is the first item returned by a pop operation. Thus, the last piece of data added to the stack will be the first item removed.
We can implement stacks in Scheme as objects that respond to the messages
':empty?
, ':push!
, ':pop!
, and
':top
. The create operation will correspond to the
constructor procedure makestack
, which takes no arguments and
returns an empty stack.
But how do we store the values in the stack? We use a list. The front
element of the list represents the top of the stack. To push something
on the stack, we cons it at the front of the list. To pop the stack, we
take the cdr of the list. Since we want to change the stack, we keep
a reference to the list in a vector, which we call stk
.
(define makestack (lambda () (let ((stk (vector null))) (lambda (message . arguments) (cond ((eq? message ':empty?) (null? (vectorref stk 0))) ((eq? message ':push!) (if (null? arguments) (error "stack:push!: an argument is required") (vectorset! stk 0 (cons (car arguments) (vectorref stk 0))))) ((eq? message ':pop!) (if (null? stk) (error "stack:pop!: the stack is empty") (let ((lst (vectorref stk 0))) (vectorset! stk 0 (cdr lst)) (car lst)))) ((eq? message ':top) (if (null? stk) (error "stack:top: the stack is empty") (car (vectorref stk 0)))) (else (error "stack: unrecognized message")))))))
Since the vector stk
is allocated during the definition
process, outside of the lambda
expression for the procedure
being returned, it will persist as part of the object between operations on
that object. Further, note that a different static variable is created each
time makestack
is invoked. Thus, a program can arrange for
the construction of any number of stacks, which can be pushed and popped
independently.
Stacks are useful when it is necessary to interrupt or postpone part of a computation until some simpler or more urgent computation has been completed  some description of the unfinished computation can be pushed onto a stack to make room for the simpler or more urgent one. When the latter is finished, we pop the stack to recover and resume the unfinished computation.
For example, suppose that we have a tree of numbers and we want to find the sum of all the numbers in the tree. One approach is to issue a recursive call every time we identify a nonempty subtree:
(define sumall (lambda (tr) (cond ((number? tr) tr) ((null? tr) 0) ((pair? tr) (+ (sumall (car tr)) (sumall (cdr tr)))) (else (error "sumall:" "invalid argument")))))
This is an elegant solution, but the fact that computing a result may require two recursive calls, or one, or none can be confusing. We could avoid this confusion by building up the sum as a running total, adding in the numbers one by one and considering only one subtree at any given time.
We can manage this by maintaining a stack that will at all times contain the subtrees whose contents we have not yet added to the running total. Initially, we'll set up the stack so that it contains the whole tree as its only element. Subsequently, at each step, we pop one subtree off this stack. If it is null, we discard it without changing the running total. Otherwise, it must have a car and a cdr. The cdr is a subtree that we aren't ready to consider yet, so we push it onto the stack. The car might be a number and might be another tree of numbers. If it's a number, we add it to the running total and continue to the next step; if it's a tree of numbers, we push it onto the stack and proceed to the next step (without changing the running total). When the stack becomes empty, everything has been added to the running total, so we stop and return the accumulated value. In Scheme:
(define sumall (lambda (tr) (let ((todo (makestack))) (todo ':push! tr) (let kernel ((sofar 0)) (if (todo ':empty?) sofar (let ((current (todo ':pop!))) (cond ((number? current) (kernel (+ current sofar))) ((null? current) (kernel sofar)) ((pair? current) (push (car current)) (push (cdr current)) (kernel sofar)) (else (error "sumall:" "invalid argument")))))))))
The idea of storing subproblems that we can't address immediately and recovering them later, when we're in a better position to solve them, is a useful programming strategy  keep an eye out for appropriate occasions to use it.
April 28, 1997 [John Stone and/or Henry Walker]
May 1, 2000 [John Stone]
http://www.cs.grinnell.edu/~stone/courses/scheme/stacks.xhtml
Thursday, 3 May 2001 [Samuel A. Rebelsky]
set!
with
similar calls to vectorset!
.
sumall
to permit
more general trees.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 6 09:31:11 2003.
The source to the document was last modified on Thu Jan 16 11:59:38 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Readings/stacks.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu