AP Computer Science - Mr. Merlis
> Labs 10-12

Data Structures – LinkedList, Queue, Stack 

This series of labs and the next will investigate, use and/or implement the following data structures:

Lists (sequential elements)	{5,8,10,3,7,8,3,10}
Sets (unique elements)	{5, 8, 10, 3, 7}
Maps (associated pairs)	(1,2), (2,5), (3,2) } first elements form a set
Trees (branching hierarchy)
Hash Table (keyed access)

These are general names and are referred to as ADT’s (abstract data types).  Each one has at least one implementation in the Java.util package.  We will also implement very specialized data types using the built-in types.  The types of lists that you need to know are listed here:

List -random access (indexed), implemented as

    arrays – may contain primitive data types
    2-d arrays – may contain primitive data types
    ArrayList – must contain objects   

List – linked, implemented as a doubly linked list

    LinkedList – must contain objects
    ListNode – AP class for the exam (BP p. 119), creating linked lists from scratch 

List - special access

    queue – FIFO – we will implement with the ArrayList class (BP p. 124-5)
    stack – FILO – we will implement with the ArrayList class (BP p. 123)
    priority queue – two implementations
        ArrayPriorityQueue
        HeapPriorityQueue 

The context

For all the data structure assignments we will be using music CD’s, news stories and commercials  as the data and be performing operations in the context of a radio station.  We will be considering scheduling, taking requests, retrieving the desired music, and so on.s

---

Lab 10 – storing and reading in the data

-->You will need a total of five classes for this lab. 3 object classes, 1 app, and also EasyReader.

Write the class Song as a data storage unit.  It should have the following fields

    private String itsTitle;        // the name of the song
    private String itsArtist;   // the artist or group that performs the song
    private int itsTrack;       // the track number on itsCD
    private String itsCD;       // the name of the CD that contains this song

Also include accessors for each instance variable as well as a 4-param constructor

Write the class CD.  It should have private instance variables

    private LinkedList itsContents;     // holds a list of the Song’s on the CD
    private String itsName;             // the name of the CD

The CD class should also have a printContents.  Use a ListIterator to traverse itsContents. 
Note: The CD does NOT know its own author.

Finally write a class, CDReader, that will use the EasyReader class to read your data file.  The file should have the following format

Name of CD
Artist
number of songs
Song title
Song title
Song title
…. 

Declare a CD.  For each CD, read in the name, artist and number of songs.
In a loop, create a song with a constructor that has all four fields as parameters.  Add it to the contents of the CD.   

Finally, write an application program (Lab10) that uses the above classes to read your data file and print out all the CD’s and their contents

---

Lab 11: Queues

Copy the implementation of the Queue class from here (taken from Be Prepared, Litvin, p. 124) into a new Queue class.

Write an application program (Lab11) that reads your data file and gets the contents of all the CD’s, making a master list of songs by adding them all together (try addAll() from the LinkedList class).   Using a Random object, choose ten songs at random and put them in a queue.  Print out the titles as the songs are chosen.  Perhaps put in a message “…enqueueing songname”. 

These are songs that have been requested and must be played in the order chosen.   “Play the songs” back by dequeueing all the entries.  Again print an appropriate message.

Extra Credit – since it is inefficient to use random access

(like we do in the choosing of the song above in a LinkedList),

use the toArray() method to make the list faster to access.

---

Lab 12: Stacks

Copy the implementation of the Stack class from here (taken from Be Prepared, Litvin, p. 124) into a new Stack class.

Copy your Lab11 and rename it as Lab12.  Revise the program to work with stacks instead of queues.  Again choose 10 songs at random, but add them to a Stack this time.  These are songs that are to be played during a segment of the programming and will be played by taking the top one off the stack each time.  

“Play the songs” back by popping all the entries.