CMSI 2120: Welcome to Week 03
This Week's Agenda
For this week, here's the plan, Fran…
- Discuss Lafore chapter two reading
- Arrays
- Dividing up a program
- Arrays of ordered data
- Logarithms
- Discuss Bloch items 12 & 14 ~
need to know
, composition vs. inheritance - Continue with Bootcamp
- More Java Basics
- Computer Architecture
- Garbage Collector
- Memory and management
- Abstract data types
- Sequential Lists
- Arrays revisitied
- Stacks and Queues
- In-class Exercise
Lafore, Chapter Two
Chapter two in the textbook deals with a very basic data structure the array.
This is usually defined as a contiguous set of values that can be controlled and maintained using a set
of [usually] integer indexes [sometimes called indices
]. For now, I'll highlight some of
the concepts from the book that are important as an introduction. We will get into the nitty-gritty in
a little while. [Show chapter two highlights from Lafore]
Bloch, Items 12 & 14
Item 12 deals with the idea of information hiding, which is more formally known as ENCAPSULATION. This is one of the main principles of Object Oriented Programming, since the idea is to keep the information in the object private and only allow users of the object to have access to the information in specific ways that the programmer controls. [Show item 12 starting on page 48 of Bloch]
Item 14 presents a gotcha
with OOP, related to the idea of INHERITANCE. This is
the mechanism we've seen that allows a class to be extended by another class. Inheritance is a
powerful way to achieve code reuse, but it is not always the best tool for the job. It is safe to use
inheritance within a package, where the subclass and the superclass implementation are under the control
of the same programmers. It is also safe to use inheritance when extending classes specifically designed
and documented for extension.
However, used inappropriately, it leads to fragile software. Inheriting from ordinary concrete classes across package boundaries, however, is dangerous. A subclass depends on the implementation details of its superclass for its proper function. The superclass's implementation may change from release to release, and if it does, the subclass may break, even though its code has not been touched. As a consequence, a subclass must evolve in tandem with its superclass, unless the superclass's authors have designed and documented it specifically for the purpose of being extended. [Show item 14 starting on page 57 of Bloch]
Java Bootcamp, Part Deux
This week we will continue with more live coding using Dr. Toal's Java Bootcamp page from last week. Then we'll take a look at some Java Basics before getting into some things we'll need to know about the inner workings of the computer and memory. Rest assured, these topics are all needed for understanding Data Structures as a topic, because [as you will see]…
EVERYTHING uses Data Structures!
Computer Architecture
Currently, nearly every computer in the world uses an architecture known as the Von Neumann
Architecture
. It looks like this:
Used from Wikipedia Commons and copied the idea from Dr. Forney
Quick Quiz: what are the 3 steps in the Von Neumann Architecture?
Here's another one with a bit more detail, a slightly different perspective:
Used from Wikipedia Commons
There are three main components to this architecture:
- The Central Processing Unit [CPU] is the brain. It controls the entire process including the three steps. There are several smaller components to the CPU: the Arithmetic Logic Unit [ALU] part of the CPU processes common math operations; the Control Unit [CU] part directs instructions and manages interactions with memory.
- The Main Memory [Random Access Memory or RAM] is the computer's short term memory. All programs and their data which are active in the computer are stored here, including the operating system as well as any other applications [web browsers, text editors, spreadsheets, games] that are running on the computer at any given time.
- Input/Output Devices [I/O] are basically everything else: keyboards, screens, networking connections, WiFi connections, mice, external projectors, speakers, EVERYTHING.
The CPU is constantly running, fetching, decoding, and executing instruction after instruction.
Memory and Memory Management
The main memory of the computer is used to hold running machine code and any data used by the program
(e.g., call stack, variables, objects, you name it). Digital information is stored, at its smallest
constituent level, in bits: magnetic low and high, as represented by 0 and 1, respectively. Bits are
strung together to store more information. There are 8 bits in one byte. Main memory consists of
large "banks" of bytes organized to be able to store and retrieve information quickly. These banks
consist of contiguous blocks of bytes organized in a sequential addressing system. Different computers
will have different byte groupings depending on hardware organizations. These are usually referred
to as words
. Many current processor architectures have 64-bit words; however, the actual size
will vary based on the CPU architecture.
A word is an architecture-dependent number of bytes that represents the maximum number of bits that the
CPU can process at one time. The word size
is the number of bytes in one word per system. For
example, a 32-bit system has 4 bytes in 1 word; i.e., the 32-bit architecture can process 32 bits at
once. The word size is limited by the hardware and operating system of the computer.
Main memory is then indexed by memory address, which are numerical orderings of the words in the RAM. Typically, addresses are 1 byte apart, with a maximum address decided by the computer architecture. For example, if our addresses start at 0x000...0 (i.e., 0), then 0x000...8 (i.e., 8) would be the address 8 bytes [one word or 64 bits] away.
Here's a picture, again ripped of from Dr. Forney due to time constraints:
OK, it should be clear that 1) there is a finite amount of memory in the computer; 2) all our programs and data are stored in main memory; and 3) there are many programs running at the same time. So, we have to efficiently manage memory, so that each program gets it's proper time to execute, and the programs don't step on each others' data. For Java, the Java Virtual Machine [JVM] handles most of these tasks for us. Lucky us!
The first thing to look at is the way we ADDRESS how data is stored. When we declare a variable, we
tell the computer Yo! Make me a space for this thing, and I'm going to refer to it by this token
called 'bozo'
. The computer then reserves a space for us. The amount of space reserved depends
on the type of data we told it we will put there. This works both for primitives like int,
double, boolean, and so forth, as well as for objects that we define. So, every time we
define a variable, it gets an address, so that the CPU can find it again when it needs to. Picture
your house, having an address, so that when FedEx comes to drop off a package, they know where to go.
Usually it would be a number [like the CPU does] but after time your delivery person might learn your
name, so they would know the token
that represents the address.
Why Do We Care?!?
|
The reason this is important is because in For example, the JVM can detect errors during the operation that will Another thing that the JVM can do for us is clean up areas of memory that are no longer being used by the
program so that they can be used again. With some compiled languages it is possible to create a |
The Garbage Collector
Since we only have so much memory to use, we have to find a way to free up space that we used but that
isn't needed any longer. This activity is performed by the garbage collector
in the JVM. In
the olden days when velociraptors roamed the earth, programmers had to keep track of this stuff by
themselves, and if they blew it, they would have a memory leak
, a blatant misnomer since the
memory wasn't actually leaking, it was the FREE SPACE that was getting filled up.
Anyhow, with Java we don't have to worry about that [mostly] because Java has a most excellent and bodacious garbage collector. To understand the GC, consider the life and scope of a variable. Here is an example:
1 public class Whoops {
2 public static void main (String[] args) {
3 int i = 5;
4 if (i < 6) {
5 int whoops = 6;
6 }
7 System.out.println(whoops);
8 }
9 }
Note that this won't compile, because at line 7, the variable whoops has gone out of
scope since it was only valid inside the if block where it was defined.
Garbage collection for local variables is quite simple: allocate the memory when the variable is in
scope, then deallocate when it is out of scope. For this reason, local variables are allocated in a
special area of memory called the stack
[since we push and pop scopes from the stack as well as
each scope's associated local variables].
Local variables are great for storing small amounts of information like counters and flags, but what about large objects? The problem is that large memory allocation can be computationally expensive, and so we want to do that as few times as necessary, then re-use what we've allocated. This provides the motivation for heap allocation and references. In Java, non-primitives have memory reserved in a special area of memory called the heap. Every object in the heap must be accessed by a reference, which is simply a stored memory address that points to an object's location in the heap.
How do we know the difference between what's on the stack and what's on the heap? Well the obvious
answer is, if it's a primitive type it's probably on the stack. However, the even easier way to
tell is, if we use the new operator keyword to make whatever the thing is, we allocate
space on the heap, and the token we use refers to that area, which is why it's known as a
reference. The reference is stored in the stack, which is how the GC can tell if
there are still references to the object.
When the GC determines that there are no remaining references to an object's token, it cleans that space up and releases it back to the heap to be used again by something else.
Quick Quiz: what will the following code [blatantly ripped off from Dr. Forney to save time] display?
public class ReferenceExample {
public int field;
ReferenceExample( int i ) {
field = i;
}
public void transferFrom( ReferenceExample other, int j ) {
field += other.field;
other.field = j;
j = 0; // [?] Does this do anything?
}
public static void main( String[] args ) {
int j = 5;
ReferenceExample a = new ReferenceExample( 1 );
ReferenceExample b = new ReferenceExample( 2 );
a.transferFrom( b, j );
// [?] What gets printed below?
System.out.println( a.field );
System.out.println( b.field );
System.out.println( j );
}
}
Now, explain the result…
REMEMBER: Java methods pass and return by value [copies of arguments and return values are made];
so, rather than pass in big objects that would need to be copied, we pass small references to the
object in the heap. Thus, the value of the reference to other in the method
transferFrom() points at the stored object, which is a ReferenceExample object called
b. However, the reference to the integer j, which is a primitive, is only acted
upon locally INSIDE the method and hence upon return its value is still 5
.
Abstract Data Types
FINALLY, OUR FIRST REAL DATA STRUCTURE! WOOOOHOOOOOOOO!!
……But first, a word from our sponsor, Definition Man…
An Abstract Data Type [ADT] is a defined type that describes how data will be stored and tells what operations can be done on that data or using that data. It is abstract because it is viewed from the perspective of the user. It is then up to the user of that ADT, or to the language itself, to implement the concrete data structures for that ADT. One example that is right in line with what we'll look at next can be found here.
An important thing to remember is that we will be using data structures to define other data structures! For example, we will use an array data structure to define a list data structure. Let's see how that works.
Sequential Lists
OK, so what's a list
? Think about when you have several things to do during the day. You
might keep track of them by making a list. What about a series of steps to perform some task? Or
what about this set of web pages that have <ol> lists all over the place?
In Java, a list is an ADT in which data is stored in an ordered sequence. The data
is allowed to contain duplicate values. A contiguous or sequential list is an
implementation of the list ADT such that elements maintain a specific order in relation to one another.
In general, most Java data collections
support several basic types of actions, to wit:
- Retrieval: find out if an element is in the collection [
find()] - Retrieval: find and return an element at a given position in the collection
[
get()] - Insertion: add an element to the collection [
append(),insert(),prepend(), orinsertAt()] - Deletion: remove an element from the collection [
removeAt()]
Sequential lists are one such structure. This structure has a LOT in common with an Array, but there are some other things of which to be aware. For one thing, Arrays are declared to be a fixed size, while sequential lists may grow and shrink as needed. Second, items in lists must be shifted around to maintain some idea of relational order – alphabetical, numeric, ascending/descending. etc.
Even so, an Array can be a good start to creating a list. Arrays are objects, so they are references and the actual storage is on the heap. Arrays in Java are homogeneous, so ever element in the array must be of the same type. An array can be dynamically allocated, meaning you can determine its initial size at run-time and THEN declare the array of that size. So, you can do things like the following:
int[] myArray; // declare an integer array
int[] myArray2; // declare another integer array
int[] myArray3 = new int[57]; // declare another int array of specific size
int[] myArray4 = { 2, 3, 5, 7, 11, 13, 17, 19, 23 }; // declare another int array and initialize it
int count = 23; // set a specific size
myArray = new int[count]; // RE-declare the int array to have size = 23
// this is *dynamically* allocated
myArray2 = new int[29]; // RE-declare the int array to have size = 29
REMEMBER that you CANNOT insert something into an array dynamically or automatically. What
I mean is, if you have an array containing { 2, 3, 5, 7 } and I want to insert the value
11 at the front, I have to go through lots of gyrations to make that happen with an
array. Simply inserting the value at myArray[0] will over-write the value at
that location! Caveat Emptor!
Be sure to read the chapter about arrays in the textbook for more information. It tells you about how to insert and delete, how to create, initialize, and access elements, and several other items of interest including ordering and searching.
Sequential List Implementation
Another nice thing about Java [and many other languages] is that because these data structures are
so commonly used, the language API has a very large collection of pre-made ADTs. They call it the
Java Collection Framework
and you can read about it at the top of the Java Collection API
page here and
here.
Designing a Class: Walkthrough
OK then, so let's make a list. We can do this by making an interface that will
specify the operations [behaviors] we need for a list to have. Be sure and read [later on but at
some point in the semester] the section in Effective Java
about preferring interfaces. Here
is the interface code:
public interface IntListInterface {
int getValueAtIndex( int index );
boolean append( int valueToAdd );
boolean insertValueAtIndex( int value, int index );
int removeValueAtIndex( int index );
}
First, a couple of words about this code. One, it's an interface which means you have to
implement the guts of the methods yourself when you implement the interface. Two, both
the methods getValueAtIndex() and removeValueAtIndex() return the integer
value, the difference being that one just hands back the value leaving the list content unchanged,
while the other removes the value and hands it back so the list content is different. Three, the
append() and insertValueAtIndex() methods return booleans, which will be
true if the operation is successful; they COULD return void [which means
returning nothing at all], but you would have no way of knowing if the operation was successful in
that case.
Next we need to design the class which will implement the interface. This is done with a simple
Java class. Let's start by thinking of what we need to keep track of in the list. It's a list of
integers, or int
items, so we'll need an array that contains those. We also need some idea
of how big it is, which will also help us determine if it is empty [or full]. So, here we go:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
…
}
Next, we need a constructor, one of those special methods that get called when we call the
new
operator to instantiate the class:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
…
}
And of course, we need to implement the required methods, since we are implementing the interface with our class. Let's start with an easy one, returning a value from the list. Things to keep in mind here are: 1) what if the list is empty; 2) what if the value isn't there; and 3) what if the value isn't there AND the list is empty.
Yes, I realize that number 3) is covered by number 1), and that we don't care WHAT is at the index that we're requesting so number 2) is superfluous, but that's just to prove a point – when you are designing classes [or programs, or ANYTHING for that matter], you need to be a bit pragmatic about thinking of all possibilities, at least to start with, then rule out the ones that are not germain.
OK, so here's some code for this, [which we'll change later per Uncle Bob]:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
if( size == 0 ) {
return -1;
} else if( index > size ) {
return -1;
} else if( index < 0 ) {
return -1;
} else {
return theList[index];
}
}
…
}
OK, so far so good [or SFSG
as we say in the trade…]
There's a big BUT in this code, though. We're checking to see if the list is empty, and
that's good, but we're returning a magic number
, a value of negative one, which really has
no meaning unless we define it. There's nothing really WRONG with this, but it can be done better
by using Exceptions, which Java provides for us. So, instead of return -1; we can
throw an exception:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
if( size == 0 ) {
throw new ArrayIndexOutOfBoundsException( "The list is empty!" ); // maybe not the best...
} else if( index > size ) {
throw new ArrayIndexOutOfBoundsException( "The index value is too large" );
} else if( index < 0 ) {
throw new ArrayIndexOutOfBoundsException( "The index value is too small");
} else {
return theList[index];
}
}
…
}
In fact, we can even define our own exception class to reflect the fact that the errors pertain to a list class:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
private class ListException extends Exception {
public ListException( String m ) {
super( m );
}
}
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
return theList[index];
}
…
}
So, now we can find something in the list, but we need to be able to put something INTO the list
so there will be something to actually find. So we need to do our insert
method, which is
called append():
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
private class ListException extends Exception {
public ListException( String m ) {
super( m );
}
}
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
return theList[index];
}
public boolean append( int valueToAdd ) {
if( size <= theList.length ) {
theList[size] = valueToAdd;
size++;
return true;
} else {
// what should we do here, if there's no room?
}
}
…
}
Well, this is going pretty well. We can actually take a breather at this point, and write some
test code to check things out! There are a couple of ways to do this activity. We can either
write a separate class, a TestIntList class, or we can simply put a small testing
main() directly into the IntList class itself. For easy reading, let's
do the second option:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
private class ListException extends Exception {
public ListException( String m ) {
super( m );
}
}
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
return theList[index];
}
public boolean append( int valueToAdd ) {
if( size < theList.length ) {
theList[size] = valueToAdd;
size++;
return true;
} else {
// what should we do here, if there's no room?
}
return false;
}
// we've gotta have these to actually get things to compile
public int removeValueAtIndex( int index ) {
return -1;
}
public boolean insertValueAtIndex( int value, int index ) {
return true;
}
public static void main( String[] args ) {
IntList list = new IntList();
list.append( 2 );
list.append( 3 );
list.append( 5 );
list.append( 7 );
System.out.println( list.getValueAtIndex( 3 ) ); // should return the value 7
System.out.println( list.getValueAtIndex( 18 ) ); // just to see what happens
}
}
OK, now we know things are working, so let's move on to the next method to implement. I choose to
do the removeValueAtIndex() method. This one has something interesting to do! When
we appended something into the list, it went in at the end, so that was trivial. However, because
when you take something out that isn't at the end, you have to move the rest of the list up
to fill the empty location [slot
], so this gets just a bit more complex. So, we can write
[make up on the spot] a helper method
to do the moving around for us. Let's call it the
holeFiller() method, and it looks like this:
private void holeFiller( int index ) {
for( int i = index; i < size - 1; i++ ) {
theList[i] = theList[i+1];
}
}
We make this method private because we don't want anyone or anything else to access
it, ONLY the things in our IntList class. So, we can add that right in:
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
private class ListException extends Exception {
public ListException( String m ) {
super( m );
}
}
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
return theList[index];
}
public boolean append( int valueToAdd ) {
if( size < theList.length ) {
theList[size] = valueToAdd;
size++;
return true;
} else {
// what should we do here, if there's no room?
}
return false;
}
private void holeFiller( int index ) {
for( int i = index; i < size - 1; i++ ) {
theList[i] = theList[i+1];
}
size--;
}
// we've gotta have these to actually get things to compile
public int removeValueAtIndex( int index ) {
return -1;
}
public boolean insertValueAtIndex( int value, int index ) {
return true;
}
public static void main( String[] args ) {
IntList list = new IntList();
list.append( 2 );
list.append( 3 );
list.append( 5 );
list.append( 7 );
System.out.println( list.getValueAtIndex( 3 ) ); // should return the value 7
System.out.println( list.getValueAtIndex( 18 ) ); // just to see what happens
}
}
So now we have a way to move things around when we take something out of the list, so now we can
implement the removeValueAtIndex() method which becomes trivial. Note that I've also
added in a few extra test lines in the main():
public class IntList implements IntListInterface {
private int[] theList;
private int size;
private static final int STARTING_SIZE = 19; // defines starting size; don't worry, we'll deal
private class ListException extends Exception {
public ListException( String m ) {
super( m );
}
}
public IntList() { // doesn't HAVE to be declared public, but doesn't hurt
theList = new int[STARTING_SIZE];
size = 0;
}
public int getValueAtIndex( int index ) {
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
return theList[index];
}
public boolean append( int valueToAdd ) {
if( size < theList.length ) {
theList[size] = valueToAdd;
size++;
return true;
} else {
// what should we do here, if there's no room?
}
return false;
}
private void holeFiller( int index ) {
for( int i = index; i < size - 1; i++ ) {
theList[i] = theList[i+1];
}
size--;
}
public int removeValueAtIndex( int index ) {
int value = theList[index];
try {
if( size == 0 ) {
throw new ListException( "The list is empty!" );
} else if( index > size ) {
throw new ListException( "The index value is too large" );
} else if( index < 0 ) {
throw new ListException( "The index value is too small");
}
}
catch( ListException le ) {}
holeFiller( index );
return value;
}
// we've gotta have this to actually get things to compile
public boolean insertValueAtIndex( int value, int index ) {
return true;
}
public static void main( String[] args ) {
IntList list = new IntList();
list.append( 2 );
list.append( 3 );
list.append( 5 );
list.append( 7 );
System.out.println( list.getValueAtIndex( 3 ) ); // should return the value 7
list.append( 11 );
list.append( 13 );
list.append( 17 );
list.append( 19 );
System.out.println( list.getValueAtIndex( 7 ) ); // should return the value 19
System.out.println( list.removeValueAtIndex( 3 ) ); // should return the value 7
System.out.println( list.getValueAtIndex( 3 ) ); // should return the value 11
System.out.println( list.getValueAtIndex( 18 ) ); // just to see what happens
}
}
The last piece of the puzzle to add is to implement the insertValueAtIndex() method.
It is much the same as the removeValueAtIndex() method, only instead of moving the
values down in the array [toward the 'end'], you move them up [toward the 'beginning'].
Of course, you need to check that there is enough space. However, you can also increase the size of
the list when you are out of room. Since this is going to be the week's in-class exercise, I'll
stop now on that.
Another thing that you may notice is that there is quite a bit of repeating code. For example,
all the error checking that is done in the two index methods getValueAtIndex() and
removeValueAtIndex() is exactly the same. This is another place where we can simply
make up a new helper method
to check the index, and replace the duplicate code with a call
to the new method. Also, in that code, we are throwing an ArrayIndexOutOfBounds exception when
the list is empty, which isn't really correct. It is MUCH better to throw an appropriate
exception instead.
Part of the in-class exercise will also be to find a better exception, or to
make one of your own. This process is known in the industry as refactoring. It
is something you should consider doing whenever you reach a point that everything is working and
all your tests are passing – stop and re-visit your code, see if there is duplication you
can remove, variable names that you can clean up, or other code smells
[as Uncle Bob calls
them] that you can get rid of.
Stacks
OK, Definition Man, what's a stack
?
Think of a stack as like a stack of trays in the cafeteria, or perhaps the stack of soup bowls when
you go to SoupPlantation for dinner. You can only take one off the top of the stack – you
can't take one off the middle without moving all the ones on top first, which they won't let you do
in the restaurant. When they add more bowls to the stack the put them on top, and the last one in
becomes the first one out. This is known as LIFO
, an acronym meaning Last In First Out
.
A stack data structure is exactly the same – a LIFO structure. We speak of push()
and pop() operations for a stack, but really those are just the same as having our
sequential list structure but only allowing things to be appended to the end or removed from the
end of the internal array, which makes the implementation easy [easier than the list, anyhow].
Here is a graphic to help 'splain it, Lucy…
The implementation is straightforward now that we've done a sequential list. You can get rid of
the methods that are there except for the append() method, but replace the two methods
getValueAtIndex() and removeValueAtIndex() with the methods peek()
and pop(), respectively. Change the append() method to be push()
instead, and voílá, you have a stack!
Queues and Deques
OK, Definition Man, what's a queue
? For that matter, what's a deque
?
A queue is like the line at the supermarket or waiting to get into the movies or
the drag races or your favorite concert [mosh pit notwithstanding…]. You know the drill:
you get in line behind someone, and then someone else gets in line behind you. As each person is
served at the front of the line, the line moves up, so you get closer and closer to the front, your
anticipation grows, you get more excited, until finally you're at the front and find out that the
tickets are all sold out. Heavy sigh, bummer, dude
…
Seriously, though, the queue data structure is exactly that, a queue or line that gets added to at
the back and removed from the front, or added to one end and removed from the other end. This is
why it's known as First In First Out
or FIFO
. Here's an example for that:
Again, implementation is straightforward now that we've done a sequential list. You can get rid of
the methods that are there except for the prepend() method, but replace the two methods
getValueAtIndex() and removeValueAtIndex() with code that will remove the
last value at the end of the list instead, and voílá, you have a queue!
Once you have a working queue class, you can easily extend that to make a Deque class.
Despite the fact that it is pronounced like DECK
as in cards, the deque is really a queue
that allows insertion and removal at BOTH ends. So, to make a deque implementation, you would need
to extend your Queue class and add back the method append() [sounds familiar??], and
a method getFront() [or some such name] to pull the item off the front of the queue.
REMEMBER that a good way to do this stuff is to define interfaces which you then implement in your class code. This way when you change YOUR code to do the implementation differently the rest of the world doesn't have to change THEIR code, as long as they continue to implement the interface according to its specifications.
In-class Assignment #3
Your mission [should you decide to accept it], is to implement the
insertValueAtIndex()method in the list class.
You must do the following:
- Make sure that if there isn't enough room in the list already, the size of the list gets expanded
by the amount of the
STARTING_SIZEvalue. - Then, also add a method
checkIndex()to validate an index value, and re-factor your code. - Also, add a new method
prepend(), which adds a value at element zero of the list, moving all the other values to make room. - If you have time, make yourself another exception class, give it the name
EmptyListException, and add it into your code. - Write tests in a
main()method to test everything out, using one or more of the ways that were shown in class. - Be sure to check everything into your GitHub repo in the classwork03 folder when you are done.
Homework Assignment #2
Homework #2 is due next week, and I know homework #3 isn't due for a while, but i wanted to give you a heads-up and a reminder on the homework assignments that you will be doing this semester. They are all available from the syllabus page of course, but just to make sure I'm reminding you here as well.
Thanks to the Department of Redundancy Department……
Week Three Wrap-up
That's probably enough for the this week. Next week, we'll get into linked lists and iterators!