Abstract Data Types

Collections can be implemented in many different ways

An abstract data type (ADT) is an organized collection of information and a set of operations used to manage that information The set of operations defines the interface to the ADT
As long as the ADT fulfills the promises of the interface, it doesn't really matter how the ADT is implemented Objects are a perfect programming mechanism to create ADTs because their internal details are encapsulated
1

Abstraction
Our data structures should be abstractions

That is, they should hide unneeded details

We want to separate the interface of the structure from its underlying implementation This helps manage complexity and makes it possible to change the implementation without changing the interface

What do we mean by makes it possible to change the implementation without changing the interface?
Why is changing the implementation without changing the interface desirable?

What about a stack?

Is a stack an Abstract Data Type (ADT) with a collection of data and operations that are allow on the data? How many operations can we legally perform to manipulate a stack? push & pop Do we care about how these operations are implemented? We only care about the what, not about the how!

A set of operations defines the interface to the ADT. What are they for a stack?

Static vs. Dynamic Structures

A static data structure has a fixed size

This meaning is different from the meaning of the static modifier (variable shared among all instances of a class)
Arrays are static; once you define the number of elements it can hold, the number doesnt change A dynamic data structure grows and shrinks at execution time as required by its contents A dynamic data structure is implemented using links
4

Dynamic Implementations

The representation should facilitate the intended operations and should make them easy to implement.

Classic Data Structures

Classic linear data structures include queues and stacks

Classic nonlinear data structures include trees, binary trees, graphs, and digraphs

Fig. 12.6 a queue data structure

A queue is similar to a list but adds items only to the rear of the list and removes them only from the front It is called a FIFO data structure: First-In, First-Out Analogy: a line of people at a movie ticket window enqueue dequeue

last item in, last item out

first item in, first item out

7

Queues
We can define the operations for a queue
enqueue - add an item to the rear of the queue dequeue (or serve) - remove an item from the front of the queue empty - returns true if the queue is empty

As with our linked list example, by storing generic Object references, any object can be stored in the queue Queues often are helpful in simulations or any situation in which items get backed up while awaiting processing (Jobs waiting their turn to be processed.)
8

Queues
A queue can be represented by a singly-linked list. Operationrs: enqueue add an item to rear dequeue remove an item from front empty returns true if queue is empty Is it more efficient if the references point from front to the rear?

Two representations of same queue

rear info4
null info4

info3
next info3

info2
next info2

front info1
next info1

queue

queue

next rear

next

next

null front

Queues
A queue can be represented by an array What may happen as queue grows via enqueue with no immediately occurring dequeues?

Stacks
A stack ADT is also linear, like a list or a queue

Items are added and removed from only one end of a stack
It is therefore LIFO: Last-In, First-Out Analogies:
a stack of plates in a cupboard a stack of bills to be paid a stack of hay bales in a barn

11

Fig. 12.7 stack data structure

Stacks often are drawn vertically:

push

pop

last item in, first item out

first item in, last item out

12

Stacks
Some stack operations: push - add an item to the top of the stack pop - remove an item from the top of the stack peek (or top) - retrieves the top item without removing it empty - returns true if the stack is empty A stack can be represented by a singly-linked list; it doesnt matter whether the references point from the top toward the bottom or vice versa A stack can be represented by an array, but the new item should be placed in the next available place in the array rather than at the end of the array (What can happen with an array implementation?) 13

Stacks
The java.util package contains a Stack class

Like ArrayList operations, the Stack operations operate on Object references

See (not during class) Decode.java (page 649) which reverses the strings in a message. The words in the message are separated by a single space. The Stack class is used to push the characters of the word onto the stack and then pops the characters out in reverse order.