Using Versus Extending an ADT
Note: In this and future labs we make a distinction between using an ADT and extending an ADT. You must be clear on this distinction:
Using an ADT
When asked to use an ADT write a program that is implementation independent, i.e. the program uses only ADT methods (such as those for a stack) and works for either the array or linked implementation of a data structure. Do not change any code in the ADT implementation files such as stack_array.py.
Extending an ADT
When asked to extend an ADT you are going to add new methods to an ADT, meaning that you are going to add code to one or both of the array or linked implementation of a data structure, such as stack_array.py.
The Stack ADT (Abstract Data Type)
A stack is a data structure that follows LIFO (Last In, First Out) rules. Data is added to the top of a stack and removed from the top of a stack. The Stack ADT provides methods for manipulating data in a stack.
A reminder of some important points of ADT use are:
- No matter what the underlying implementation of the stack programs should access a stack only through these methods.
- As a corollary to the first point, the stack can be implemented in any number of ways so long as any given implementation follows the ADT function requirements. The implementation must invisible to the program using the Stack ADT.
- A stack may store any type of data, although all the data it stores should be of the same type.
The following code imports a stack class and the Food class then initializes a stack:1
2
3
4
5from stack_array import Stack
from food import Food
s = Stack()
...
Project References
As we work through the term we will be creating a number of different data structures and adding more functionality to the Food library already written. Making sure that each new project has the latest version of a data structure or Food library is difficult to do if we are reduced to copying and pasting our pydev modules into each new project. Fortunately, Eclipse provides a much better mechanism to reference code. Setting up Project References allows you to link one Pydev project to another, and to use the code from one project in another with the import and from … import * statements already shown. Nothing needs to be changed in your source code.
To make a reference from one project to another in Eclipse, right click on a project name in the Navigator pane. From the resulting pop-up menu click on Properties and then on Project References in the resulting dialog box.
Click on the check box of all projects that you wish to reference from the current project. In this example the project album is already selected, and the project data_structures will be added as a reference. Once this is done all of the classes in both album and data_structures will be available through import statements.
A few things to keep in mind when using project references:
- All referenced projects must be open when attempting to run a program.
- Submit all referenced projects as part of your Eclipse archive (.zip) file when submitting exercises or the markers will not be able to run your programs. You may select multiple projects to include in an Eclipse archive file.
- Do not use the same Pydev module names in two different referenced projects or Eclipse will not know which one an import statement is supposed to be referring to.
- Project references go one way only. If the project stacks references the project data_structures, then data_structures should not reference stacks. Circular references are a very bad idea.
- Upon occasion referenced projects may become ‘out of sync’ with the project that references them. To fix this, right-click on the project and choose Refresh to update Eclipse from the file system.
Array-based Stacks
The file stack_array.py is a text file containing the basic outline of the array-based Stack class. Copy this code into the Pydev module stack_array.py in your login_data_structures project (where login is your Network login). Thus, a student with the Network login barn4520 should name their projects barn4520_Food and barn4520_data_structures.) The Lab Instructor will walk you through this library and discuss its inner workings.
Tasks
(If you were unable to complete Lab 1 correctly, you may use these files: food.py, food_utilities.py, and foods.txt as the basis for your lab. These files will not be available until after the labs for the previous week are completed.)
For the appropriate tasks you may download and use the Food class definition in food.py from Lab 1.
For all of your data structures (stacks, queues, BSTs, etc.), put your code into libraries in your Pydev project login_data_structures.