CSC311: Data Structures
Fall 2007
Programming Project 1
Basic Data Structures: Arrays, Stacks,
Queues, Linked Lists, Deques
Description:
Abstract Data Type (ADT)
is a very important concept and mechanism of object-oriented programming and
design to implement information hiding and encapsulation. ADTs
only define legal operations that can perform on them without specifications of
how these operations are implemented, and these operations can be separately implemented
in any way. In Java, ADTs are usually represented as
interfaces. In this project you will design and implement a specific ADT with
different data structures.
Task:
The ADT Deque is
defined as a Java interface in our textbook (as shown in Page 215). Write a
Java program to implement this ADT with doubly linked list and circular array.
Your program should consist of one interface and two classes:
·
The interface Deque is defined in Page 215,
·
One class implements the
deque ADT with a doubly linked list,
·
One class implements the deque
ADT with an array used in a circular fashion.
Submission:
·
The project will due on
·
Only electronic submission will be accepted.
·
Your submission should include
o
Java source code
o
A
class diagram describing the relationships of the interface and two classes as
required
o
Necessary documentation for the implemented operations