Last week, we saw how the
Balance class represented an example of abstraction.
Balanceclass defines public methods so that other programs written by anyone, anywhere, at anytime before or after it can rely on its functionality as long as they know how to interface with it.
The public methods of the
Balance class represent a functional abstraction since they allow clients to use the
Balance class without understanding its implementation details.
How does functional abstraction apply to collection types like ArrayIntList?
ArrayIntList class defines public methods, such as
indexOf, that allow other programmers (clients) to use the
ArrayIntList class without understanding its implementation details.
Earlier, we defined
ArrayIntList as a collection that can be used to store a list (ordered sequence) of integer data and introduced the concept of a class invariant.
- ArrayIntList class invariant
i-the item in the list is always stored at
The wording is deliberate: the list concept is separate from the underlying
elementData array. The other indices of the
elementData may contain any values. An
ArrayIntList implements the list concept with an
ArrayIntList is an example of data abstraction.
- ArrayIntList data abstraction
- The separation of the list concept (client view) from the underlying array (implementer view).
- Abstract data type (ADT)
- The concept of a list as an ordered sequence with operations such as
- Data structure
- The underlying array that the implementer must maintain so that the client can use
ArrayIntListas a list.
ArrayIntList is a Java class that binds these two concepts: the list abstract data type that informs the client how to use the class and the array data structure that actually provides the behaviors for the class’s public methods. Next, we’ll introduce the idea of different abstract data types and see what happens. In the coming weeks, we’ll see how (and why) we might also want to switch out the data structure too.
The list abstract data type represents an ordered sequence of elements.
addan element to any given index in the list (shifting right subsequent elements as necessary).
getto return the element at any given index in the list.
removethe element at any given index in the list (shifting left subsequent elements as necessary).
sizeto return the number of elements in the list.
In this lesson, we’ll contrast lists with stacks and queues. Stacks and queues are simpler than lists: in fact, lists can do everything that stacks can do and also everything that queues can do too.
It might seem a bit unintuitive why programmers would prefer data types that do fewer things rather than data types that do more things.
From a functional abstraction perspective, why might we prefer a simpler ADT?
Defining a public method is a commitment. If a public method lets “other programs written by anyone, anywhere, at anytime before or after it” to rely on its functionality, then that places a burden on the implementer to maintain that method and improve it. This burden increases program complexity and limits opportunities to improve performance. Related to this idea, a concept in software design that we’ll explore at the end of the course is deep classes: classes that provide few public methods, but a lot of functionality.
Java provides classes and interfaces for many different collections and abstract data types in the
java.util package. To use them, add an
import statement to the top of each Java file.
java.util package represents abstract data types as interfaces and concrete implementations as classes. For example, instead of declaring
ArrayIntList list = new ArrayIntList();, the better approach is to use the interface type
List on the lefthand side of the assignment statement.
List<String> list = new ArrayList<String>();
This line of code creates a new
ArrayList<String> (righthand side) and assigns it to a local variable of type
List<String> (lefthand side). We’ll later see that there are other ways of implementing the
List interface with different tradeoffs, so it’s useful to write client code using the general interface type where possible so that the implementation can be changed if necessary later on.
To store a list of integers using Java’s
ArrayList class, we might write the following line of code.
List<int> list = new ArrayList<int>();
This doesn’t work because Java disallows primitive types such as
double from being used as the specialized type. Instead, specialized types need to be classes such as
String. Java provides wrapper classes to represent primitive values as objects. For example, the wrapper class for
int is called
Integer. We can declare a list of integers as follows.
List<Integer> list = new ArrayList<Integer>();
Java will conveniently convert between the primitive type and the wrapper class automatically most of the time, so we can use the primitive type everywhere else.
List<Integer> list = new ArrayList<Integer>(); list.add(1); int first = list.get(0);
The stack abstract data type allows adding and removing elements from the “top” of the stack. Imagine a stack of plates. The most common of way of interacting with the stack of plates is to add a plate to the top or remove a plate from the top.
pushan element to the top of the stack.
popto remove and return the top element from the stack.
peekto return but not remove the top element from the stack.
sizeto return the number of elements in the stack.
Consider the following code snippet.
Stack<String> stack = new Stack<String>(); stack.push("puppy"); stack.push("cat"); stack.push("dog"); System.out.println(stack.pop());
The first element removed by
stack.pop() is “dog” since “dog” was at the top of the stack.
Which element would be removed by a second pop operation?
The next element removed by
stack.pop() would be “cat” since “cat” is on top of “puppy” in the stack.
There’s one weird detail about stacks in Java. Stacks are an abstract data type, so they aren’t necessarily tied to one specific data structure implementation. Unfortunately, Java’s
Stack class has a critical design flaw: it’s a class, not an interface. This means that the left hand side and right hand side of an assignment statement will both be declared with the
Stack class, rather than using an interface type.
- The Java
Stackclass has many other methods beyond
isEmpty, but they’re off-limits for this course since they aren’t part of the stack ADT. (Poor design!)
Because stacks add to the top and remove from the top, we consider them last-in, first-out (LIFO) structures. In other words, the most recently-pushed element is the element that will be the first to be removed.
While stacks are last-in, first-out (LIFO), queues are first-in, first-out (FIFO). Whereas stack operations only allow changes to the top, queue operations allow changes to the “front” and the “back” of the queue. Imagine people waiting in the checkout line at the grocery store. When someone wants to checkout, they’re added to the back of the queue (which might be empty). The first person to checkout is the person at the front of the line.
addan element to the back of the queue.
removeand return the element at the front of the queue.
peekto return but not remove the element at the front of the queue.
sizeto return the number of elements in the queue.
Consider the following code snippet.
Queue<String> queue = new LinkedList<String>(); queue.add("puppy"); queue.add("cat"); queue.add("dog"); System.out.println(queue.remove());
The first element removed by
queue.remove() is “puppy” since “puppy” was at the front of the queue.
This time, Java got the design right for queues.
Queue is an interface in Java, which means that we can’t instantiate it directly. Instead, we need to use an implementation such as
LinkedList that also implements the
This is the powerful idea behind ADTs. By declaring an object such as a
LinkedList as the interface type
Queue, we’re signalling to the human reading the program that we intend to use this object in queue-like ways, rather than all of the possible ways that we might use a list.