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 lab on object-oriented programming, can often be developed most 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 two frequently encountered data structures that Scheme happens not to supply as built-ins: stacks and queues.
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 spring-loaded 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:
create
Create a new, empty stack object.
empty
Determine whether the stack is empty; return true if it is and
false if it is not.
push
Add a new element at the top of a stack.
pop
Remove an element from the top of the stack and return it. (This operation
has a precondition: It cannot be performed if the stack is empty.)
top
Return the element at the top of the stack (without removing it from the
stack). (This operation, too, can be performed only if the stack is not
empty.)
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 make-stack; this constructor takes no
arguments and returns an empty stack. The object will protect access to a
single field, stk, which will contain all of the elements that
are currently in the stack, assembled into a list. Here is the code:
(define make-stack
(lambda ()
(let ((stk '()))
(lambda (message . arguments)
(cond ((eq? message 'empty?) (null? stk))
((eq? message 'push!)
(if (null? arguments)
(error 'stack "method PUSH!: An argument is required")
(set! stk (cons (car arguments) stk))))
((eq? message 'pop!)
(if (null? stk)
(error 'stack "method POP!: The stack is empty")
(let ((removed (car stk)))
(set! stk (cdr stk))
removed)))
((eq? message 'top)
(if (null? stk)
(error 'stack "method TOP: The stack is empty")
(car stk)))
(else (error 'stack "unrecognized message")))))))
Since the field 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 new local variable is created for
stk each time make-stack is invoked. Thus, a
program can arrange for the construction of any number of stacks, which can
be pushed and popped independently.
Documents on the World Wide Web usually contain special strings, called tags, that serve as instructions to the browser about what the document contains, how it is structured, and how the text should be displayed. In many cases, tags occur in pairs: The opening tag marks the beginning of a region of text that constitutes some natural unit within the document structure or should be displayed in some special way, and closing tag marks the end of that region.
An opening tag is a sequence of letters and digits enclosed between a
less-than character at the beginning and a greater-than character at the
end. For instance, "<html>" is the opening tag for a
document that contains hypertext markup, and "<title>"
is the opening tag for the title of such a document. The corresponding
closing tags look almost the same, but a closing tag has a slash character
after the less-than character: "</html>",
"</title>".
Create a new stack and name it tags. Push onto this stack the
opening tag "<html>". Next, push
"<head>", the tag that begins the header of a hypertext
document, and then "<title>". Now pop the stack. The
tag that appears is the one that must be matched first by a closing tag in
order for the tags to be correctly nested. Pop the stack two more times and
confirm that the stack is a ``last-in, first-out'' data structure.
Netscape and other browsers use a stack of tags like this one -- a stack
containing tags that must eventually be matched but have not been matched
yet -- to determine whether the HTML document to be displayed is
correctly constructed. Write a Scheme procedure
correctly-nested? that takes a list of HTML
opening and closing tags and determines whether they are correctly nested.
> (correctly-nested? '("<html>" "<head>" "<title>" "</title>"
"</head>" "<body>" "<b>" "</b>" "</body>" "</html>"))
#t
> (correctly-nested? '("<html>" "<head>" "</html>" "</head>"))
#f
Some authors add a sixth operation to the definition of the stack ADT:
size, which returns the number of elements in the stack. Extend the
Scheme implementation of make-stack above so that the stacks
it constructs will accept the message size and perform this
operation when it is received.
Sometimes we want a data structure that provides access to its elements on ``first-in, first-out'' basis, rather than the ``last-in, first-out'' constraint that a stack imposes. (For example, it might be prudent to treat that pile of unpaid bills a little differently, adding new elements at the bottom of the pile rather than the top, Paying off the most recent bill first, as in a stack, can make one's other, older creditors a little testy.)
Such a structure is called a queue. Like a line of people waiting for some service, a queue acquires new elements at one end (the rear of the queue) and releases old elements at the other (the front). Here is the abstract data type definition for queues, with the conventional names for the operations:
create
Create a new, empty queue object.
empty
Determine whether the queue is empty; return true if it is and
false if it is not.
enqueue
Add a new element at the rear of a queue.
dequeue
Remove an element from the front of the queue and return it. (This
operation cannot be performed if the queue is empty.)
front
Return the element at the front of the queue (without removing it from the
queue). (Again, this operation cannot be performed if the queue is empty.)
The implementation of queues in Scheme is somewhat trickier than the
implementation of stacks. Again, we'll keep the elements of the queue in a
list. However, it turns out that the enqueue operation can be
slightly faster if we represent an empty queue by a list containing one
element, a ``dummy header,'' and store the actual queue elements after this
header, oldest first. The dummy header is not inserted by enqueue
and cannot be removed by the dequeue. It is not there to provide a
value, but just to keep the list from becoming null, so that one can always
apply the set-cdr! procedure to it without first testing to
see whether it is null. The fact that the underlying list never becomes
completely null is an invariant of this implementation of queues.
The other novel feature of this implementation is that we'll actually be
accessing the list through two different fields, front and
rear. The front field always contains the entire
list structure, beginning with the dummy header; (cdr front)
is the list of the actual elements of the queue, and (cadr
front) is the first real element of the queue (when it is not
empty). The rear field, on the other hand, is always a
one-element list; it contains the last element of the queue, except when
the queue is empty, in which case the rear field contains the
dummy header.
The following box-and-pointer diagram shows a queue into which the symbols
a, b, and c have been enqueued, in
that order:
Here is the constructor for queue objects:
(define make-queue
(lambda ()
(let* ((front (list 'dummy-header))
(rear front))
(lambda (message . arguments)
(cond ((eq? message 'empty?) (null? (cdr front)))
((eq? message 'enqueue!)
(if (null? arguments)
(error 'queue "method ENQUEUE!: An argument is required")
(begin
; Attach a new cons cell behind the current rear
; element.
(set-cdr! rear (list (car arguments)))
; Advance REAR so that it is once more a list
; containing only the last element.
(set! rear (cdr rear)))))
((eq? message 'dequeue!)
(if (null? (cdr front))
(error 'queue "method DEQUEUE!: The queue is empty")
; Recover the first element of the queue (not including
; the dummy header).
(let ((removed (cadr front)))
; Splice out the element to be dequeued.
(set-cdr! front (cddr front))
; If you just spliced out the last element of the
; queue, reset REAR so that it holds the dummy
; header.
(if (null? (cdr front))
(set! rear front))
removed)))
((eq? message 'front)
(if (null? (cdr front))
(error 'queue "method FRONT: The queue is empty")
(cadr front)))
(else (error 'queue "unrecognized message")))))))
Add to the queue an additional method, activated by the print
message, that displays each of the elements of the queue on a separate line
(without actually removing any of them from the queue). Make sure not to
print the dummy header.
Using deep recursion, write a procedure
that creates an empty queue, then traverses a tree of symbols and puts each
symbol that it encounters into the queue, and finally uses the
print method added in the previous exercise to display the
contents of the queue.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/stacks-and-queues.html
created April 28, 1997
last revised June 21, 1998
Henry Walker (walker@math.grin.edu) and John David Stone (stone@math.grin.edu)