| home page - news - syllabus - topics - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
| Introduction - Correctness of Algorithms - Analysis of Algorithms - ADTs, Stacks, Queues - Dictionaries - Searching and Sorting - Graph Algorithms |
| ADTs, Stacks, Queues |
When developing large systems it is important to design in a way that supports modularity: the system should be decomposed into components that can be designed, implemented, and (initially) tested independently before they are combined.
In general you should focus on what services the other functions and collections of data in the system are supposed to provide instead of how they are supposed to provide them. It is therefore important to develop a specification of requirements for each component of your system.
We have already seen specifications of requirements of individual functions or procedures — we have given these by listing a “precondition” and a “postcondition.” Specifications in working systems are only slightly more extensive (they also typically describe any exceptions that should be raised as part of proper error checking).
An abstract data type is, effectively, a requirements specification for a collection of data. We will consider several abstract data types (or “ADTs”) and implementations for them during the rest of this course.
Notes providing an introduction to abstract data types are now available.
A stack is an abstract data type that provides access to data in a “last-in, first-out” manner. It works somewhat like a stack of plates does in a kitchen: The plate that you can see, or remove, is always the last one that was added to the pile.
Of course we typically do not want to access data in a last-in, first-out kind of way. However, stacks do have a variety of important applications. We will study properties of stacks, as well as their implementations and applications, during the second lecture on this topic.
Notes based on the discussion of stacks in lectures and an exercise based on this material are available online.
In contrast, a queue is an abstract data type that provides access to data in a “first-in, first-out” kind of way. It works like the line or “queue” that you stand in while waiting to buy food or coffee at MacEwan Hall.
We will study properties, implementations and applications of queues during the third lecture on this topic.
While the textbook does discuss abstract data types, it does not include as much material about the specification of ADTs in real programs, or about implementations and applications of stacks and queues, as some other books provide. (On the other hand, the brief introduction to stacks and queues in Chapter 10 of the textbook is very readable, and should be looked at).
The following references were consulted when preparing lectures on this topic:
Frank M. Carrano and Janet J. Prichard
Data Abstraction & Problem Solving with Java:
Walls & Mirrors
Second Edition, Pearson Education, 2006
Unfortunately this edition of the book is not yet available in the library. However an older edition of a similar book (concerning C++) is available. This might include similar useful information about ATDs.
Mark Allen Weiss
Data Structures & Problem Solving Using Java
Third Edition, Pearson Education, 2006
A copy of this text is available on reserve in the library.
“Algorithms in Java” CD
This is distributed along with copies of the course textbook that are available at the bookstore. It provides numerous examples of Java interfaces (effectively, specifications of ADTs) and their implementations. In particular, it includes examples for the kinds of stacks and queues that are discussed in lectures and the textbook.
Sun’s Tutorial on the Java “Collections” Framework
The “Collections” API is part of the standard distribution of Java. This provides numerous (more extensive and complicated) examples of interfaces that describe the kinds of ADTs that we will consider in CPSC 331.
After studying this topic in CPSC 331 (including working through the exercises that are provided) students should understand and be able to do the following.
Students should understand the definition and the purpose of an “abstract data type.” You should also be familiar with the use of “interfaces” to include ADTs in Java programs, and the use of “implements” clauses to relate classes to interfaces.
Students should be able to read, and write, reasonably simple interfaces in Java.
Students should understand the definition and properties of a stack.
Students should be able to produce classes that implement stacks in Java in several ways, and students should understand the relatives strengths and weaknesses of these implementations.
Students should be able to use the Java Collections framework to solve a problem that involves the creation and manipulation of a stack.
Students should understand the definition and properties of a (simple) queue.
Students should be able to produce classes that implement queues in Java in several ways, and students should understand the relative strengths and weaknesses of these implementations as well.
Students should be able to use the Java Collections framework to solve a problem that involves the creation and manipulation of a queue.
What is an abstract data type? What is a data structure? How are these related?
What is an interface? How is this related to an abstract data type?
Why are abstract data types — and interfaces — useful?
What is a stack? What is a queue? How are these different? What physical objects resemble these?
Describe (at least) two ways to implement a stack. How are these implementations (and their efficiency) different?
Describe an interesting problem that can be solved using as stack.
Describe (at least) two ways to implement a queue. How are these implementations (and their efficiency) different?
Describe an interesting problem that can be solved using a queue.
Other reference material that you may find and use might refer to “stacks” and “queues” that are very different from the types that are discussed in class. How (in particular) is this the case?
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W07/topics/intro_to_ADTs.html |