Abstract Data Type (ADT)

· a collection of data and

· operations allowed on that data

The type is abstract because knowledge of what uses an object has (its operations)

is separated from knowledge of how the object does the task.

Client-Supplier Relationship

The design and implementation of ADTs can be approached from two points of view:

supplier -- developers of the ADT services.

client -- users of ADT services

Client-supplier relationship:

  ________________ ________________ 
 | | | |
 | Client |===USES===>| Supplier |
 | | | Services |
 |________________| |________________|
 (ADT user) (ADT)

The client should be able to

· accomplish their own tasks,

· use the supplier ADT without effort to understand its internal details,

· have a sufficient, but not overwhelming, set of operations. (the interface)

The supplier is concerned with:

· efficient and reliable algorithms and data structures,

· convenient implementation,

· easy maintenance.

The client-supplier contract:

A precise description of a supplier's interface forms a contract between clients and supplier.

The contract:

· gives the responsibilities of the client. The preconditions of the operations to be satisfied (the operations are called correctly).

· gives the responsibilities of the supplier. The postconditions of the operation (what the operation will deliver).

Data Abstraction

When developing programs, use abstraction to reduce complexity.

Abstraction ignores details and concentrates on essentials.

what vs. how?

Decompose

A large, complex system can be understood by decomposing it into smaller modules.

Each module should

· hide its complexity inside

· be simple to understand from the outside

· have a simple interface so that the module can be used without knowing what is inside

Abstraction deals with logical properties, not with details

Procedural abstraction:

The logical properties of an action rather than the details of how the action is implemented.

Data abstraction:

The logical properties of data rather than the details of how the data are represented.

Procedural abstraction:

· Divide a problem into tasks.

· Give each task a name and state its requirements.

· Do not worry about how the task is to be accomplished until its time to code.

· Typically each task becomes an interface to a method (with a method name, parameters, assumptions, etc.)

· Programs that call the interface do not need to know the underlying implementation details.

· The internal implementation can be changed without affecting the caller.

Concrete Data Structures

· The structure of data and its values are visible to other parts of the program.

· Any statement in the program can directly access and modify the elements of the array.

· The values and their representations are explicit while the operations on the values are implicit.

Abstract Data Structures

· Have data and operations.

· The data are hidden.

· The data values can only be accessed by public operations.

· The interface is known, but not the implementation.

· The operations are explicit while the values are defined implicitly in terms of the operations.

· A number of representations of the values may be possible.

Abstraction supports information hiding

· Implementation is hidden behind an interface

· The interface remains unchanged, even if the implementation changes.

Information hiding is related to encapsulation

· The data and the operations that manipulate the data are all combined (encapsulated) in one place.

· The only way to change the abstract data structure state is by its operations.

· Program changes to the abstract data structure class do not require changes to other programs that use the structure.

Abstract Data Types

· There is only one instance of an abstract data structure.

· To create multiple instances of an abstract data structure define an abstract data type (ADT).

Type:

a category of entities sharing common characteristics

Any entity of a certain type has all the characteristics of that type:

· The values that can be held

· The operations that can be applied to add or modify values

· An abstract data structure is an instance of the ADT.

· Operations are also needed for the creation and destruction of instances of the ADT.

· All operations (except new) must have a reference identifier (a pointer) to the particular instance to be operated upon.

ADTs are defined by their interfaces

To specify an ADT:

· name the ADT.

· identify the types (primitive data types or other ADTs) used as parameters or return values of the operations.

· specify the semantics (or meaning) of the operations.

Java Classes

A Java class is similar to a user-defined type.

Implement ADTs as Java Classes

The class and its methods should be documented with preconditions, and postconditions.

Do not use public data fields in the class.

Include, as appropriate, private methods to aid in implementation.

Design Criteria for ADT (Class) Interfaces

Use the following design criteria for evaluating ADT (class) interfaces.

Cohesion:

All operations must logically fit together to support a single, coherent purpose. The ADT (class) should describe a single abstraction.

Simplicity:

Avoid needless features. The smaller the interface the easier it is to use the ADT (class).

No redundancy:

Avoid offering the same service in more than one way; eliminate redundant features.

Atomicity:

Keep independent features separate. All operations should be primitive, that is, not be decomposable into other operations also in the public interface.

Completeness:

All primitive operations that make sense for the abstraction should be supported by the ADT (class).

Consistency:

Provide a set of operations that are internally consistent in

· naming convention (e.g., in use of prefixes like "set" or "get", in capitalization, in use of verbs/nouns/adjectives),

· use of arguments and return values (e.g., order and type of arguments),

· behavior (i.e., make operations work similarly).

Reusability:

Do not customize ADTs (classes) to specific clients, but make them general enough to be reusable in other contexts.

Robustness with respect to modifications:

Design the interface of an ADT (class) so that it remains stable even if the implementation of the ADT changes.

Convenience:

Where appropriate, provide additional operations (e.g., beyond the complete primitive set) for the convenience of users of the ADT (class). Add convenience operations only for frequently used combinations after careful study.

Linear Data Structures

Stacks and queues are linear data structures, they form a straight line. i.e., a stack or queue grows in just one direction.

Queue

A first-in-first-out (FIFO) sequential data structure in which elements are added at the back and elements are removed from the front.

Add new element to the end of the line (enqueue)
Remove the first element from the start of the line (dequeue).

Method descriptions for the Queue Class

// Precondition: None

// Postcondition: The Queue object has been initialized and is empty

public Queue()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: The number of elements in this Queue object

// has been returned

public int size()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: “true” returned if there are no elements in Queue

// “false” returned if there are elements

public boolean isEmpty()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: A reference to element has been inserted

// at the back of the Queue.

public void enqueue(Object element)

// --------------------------------------------------------------

// Precondition: This Queue is not empty.

// Postcondition: The element at the front of this Queue

// has been removed and a reference to the

// element was returned.

public Object dequeue()

// --------------------------------------------------------------

// Precondition: This Queue is not empty.

// Postcondition: A reference to the element at the front of the

// Queue has been returned.

public Object front()

// --------------------------------------------------------------

Stack

Stacks are a Last-In-First-Out (LIFO) structure. The most-recently-added item (the one on top) is the first one to get removed.

Add new element to the top of the stack (push)
Remove the top element from the stack (pop)

Method descriptions for the Stack Class

// Precondition: None

// Postcondition: The Stack object has been initialized and is empty

public Stack()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: The number of elements in this Stack object

// has been returned

public int size()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: “true” returned if there are no elements in Stack

// “false” returned if there are elements

public boolean isEmpty()

// --------------------------------------------------------------

// Precondition: None

// Postcondition: Element reference has been inserted at the top

// of this stack and returned.

public Object push (Object element)

// --------------------------------------------------------------

// Precondition: This Stack is not empty.

// Postcondition: Element reference to the top element

// of this Stack is returned and removed from Stack.

public Object pop()

// --------------------------------------------------------------

// Precondition: This Stack is not empty.

// Postcondition: Element reference to the top element

// of this stack is returned.

public Object peek()

// --------------------------------------------------------------

After defining the ADTs (for queue and stack), the next step is implementation (coding).

The implementation is totally separate from the ADT.

The ADT descriptions should and desired behavior should stay constant.

The program code, program language and its implementation can change.

Now let’s investigate 2 methods of implementing a queue and a stack.

o Arrays (fixed size, contiguous storage – index used to locate storage locations)

o Nodes (dynamic size, discontinuous storage -- pointers used to locate next storage location)