Transcript Abstract Data Type

Introduction to Objects and
Encapsulation
Computer Science 4
Mr. Gerb
Reference:
Objective: Understand Encapsulation and abstract
data types
Object-Oriented Programming
• Became popular in the 1980s
– We used to see programs as sequences of steps
– OOP sees them as collections of objects and
operations on those objects.
• Object-Oriented Languages
– Smalltalk (one of the first)
– C++ (still the most popular)
– Java (one of the most recent)
What is an Object-Oriented
Language?
• Allows the user to define objects
– Objects contain data
– Objects contain operations called methods to manipulate that
data
• Supports three capabilities:
– Encapsulation - Can offer users objects and methods without
providing access to underlying data.
– Polymorphism - Objects can define their own behavior for a
method.
– Inheritance - Can create subclasses with all the methods and
data of their superclasses.
• We will discuss polymorphism and inheritance later
Why is encapsulation important?
• Supports data abstraction - The separation
of a data type’s operations (what it can do)
from its implementation (how it does it).
• Can change the way a data structure is
implemented without affecting its users
– To improve efficiency, for example
– There may be thousands of users
For example - Your library
• Defined by its operations
– Checkout/checkin a book
– Pay an overdue fine
• Library can change the computer program it
uses to store what books are checked out
– You might not know it
– The operations above stay the same
Abstract Data Type vs.
Data Structure
• An abstract data type is defined by its interface
– Specifies which operations it offers.
– Does not specify how its data is stored
– Also does not specify how the operations work.
• Data structure
– How an abstract data type is implemented
– Specifies how the data is stored
– Specifies how the operations are implemented
Encapsulation and OOP in Java
• Objects
– Programmers define classes
• Abstract data types
– Public methods
– Parameter and return types
• Data structures and implementation
– Private data
– Body of public methods
– Private methods
Example: Strings
• Abstract type
–
–
–
–
Create a string
Concatenate two strings
Find a substring
Compare two strings
• Data Structure / Implementation
– Contiguous 1 byte storage cells? (I guess...)
– I don’t need to know that to use strings.
We will study data types in two
steps
1. Define an abstract data type (ADT)
2. Study the various data structures that can be
used to implement them.
• Some ADTs we will study: Unsorted lists,
sorted lists, stacks, queues, priority queues,
sets and maps
• Some data structures we will study: Arrays,
linked lists, binary trees, hash tables, heaps
Types of operations on an
abstract data type
• Constructor - Makes an instance of the ADT
• Observer - (a.k.a. accessors) Gives info
about the state of the ADT
• Modifier- (a.k.a. mutators or transformers)
change the state of ADT
• Iterators - Allows the components of the
ADT to be processed in a sequence
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year
Create a new class
Enroll a student
Add a student to a class
Tell whether a student is in a class
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class
Enroll a student
Add a student to a class
Tell whether a student is in a class
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student
Add a student to a class
Tell whether a student is in a class
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class
Tell whether a student is in a class
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class - Observer
Tell whether a class is full
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class - Observer
Tell whether a class is full - Observer
Drop a student from a class
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class - Observer
Tell whether a class is full - Observer
Drop a student from a class - Modifier
Alphabetical listing of all students
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class - Observer
Tell whether a class is full - Observer
Drop a student from a class - Modifier
Alphabetical listing of all students - Iterator
List of all classes offered
An ADT for a School Schedule
• Operations (which type are each?):
–
–
–
–
–
–
–
–
–
Start a new school year - Constructor
Create a new class - Modifier
Enroll a student - Modifier
Add a student to a class - Modifier
Tell whether a student is in a class - Observer
Tell whether a class is full - Observer
Drop a student from a class - Modifier
Alphabetical listing of all students - Iterator
List of all classes offered - Iterator
Summary
• Object-oriented languages support encapsulation,
polymorphism and inheritance
• Encapsulation supports data abstraction
• Two levels of data types
– Abstract data types - Operations
– Data structures - Storage and implementation
• Types of operations: Constructors, observers,
modifiers, iterators