University of North Carolina at Asheville
CSCI 202: Introduction to Data Structures
Lab 07: Linked Stacks, Queues, and Lists
Introduction
In this lab you will finish a partially written Java GUI application
that introduces the use of linked structures. In particular,
you will be asked to write new class definitions for the Stack
Queue and List classes that you wrote in
Lab 04, Lab 05,
and Lab 06.
For this lab you will in fact re-implement each of these data types
as a linked list. The basic building block of a linked list
is a node, which is a data structure containing both a
value and a link to the next node in the list.
The special value null in a link field of a node indicates
that this is the last node in the list. A linked list is just a chain
of nodes, with a null link in the last node.
In the figure below, each
box depicts a node whose two compartments contain the value and link
respectively. The electrical-ground symbol is used to indicate the
null link in the last (rightmost) node.
Access to the list is provided by an external
reference to the first node, which is depicted as the leftmost
arrow in the figure above. In contrast, the links stored
in the nodes themselves are called internal references.
In this lab, the Stack, Queue, and List
classes will each define a private Node class (actually
a so-called inner class) to represent their linked-list nodes.
The instance variables in each class will include an
external reference to the first node. (As you will see, the Queue
and List
classes will also include an external reference to the last
node.)
For maximum generality, each
Node will store a value of type Object,
which automatically includes objects of any class in Java.
Once again the GUI framework has already been created and tested,
and partially written source files for the new Stack,
Queue, and List classes will also be provided to you.
Your task is to implement several essential methods in each class,
which are presently only stubs. The GUI demo application will need
correct versions of all these methods to work properly.
Instructions:
To complete this project, follow the steps listed below:
-
Launch the NetBeans IDE and
select the File/New Project... option to create a new project
named Lab07. Define the project to be a
Java Application and be sure to create the
Lab07 project folder in your csci/202/labs directory.
Otherwise accept all the default settings
so that NetBeans automatically writes a class named lab07.Main
for you. As usual, the source file for this class will be in
Lab07/src/lab07.
-
Download the following files into your Lab07/src/lab07 project
folder. As you have seen before, NetBeans will detect these
files and automatically include them in your project.
-
Open the file lab07.Main and add the following lines of code
into its main() method:
DisplayFrame frame = new DisplayFrame();
frame.setVisible(true);
-
For a quick overview of all these classes: the only task of the
main() method in lab07.Main is to create a
DisplayFrame, which is the main application window for this
project. The DisplayFrame in this project introduces a new
feature, namely a tabbed pane. In this lab you will be developing
Stack, Queue, and List classes within a single GUI
framework, so the central display area is now a JTabbedPane
rather than a JPanel. This tabbed pane contains three
separate display panels, namely StackPanel, QueuePanel,
and ListPanel. Each panel creates and displays a single instance
of the matching data type. Note that each panel operates independently
of the others.
-
The Stack class as defined in
Stack.java already contains a fully
implemented method
called
render(), which the StackPanel uses to render the
Stack in its display area.
However, it contains only
stubs of the following methods, all of which are essential for
the application to work correctly:
- public void push(Object value)
- public Object pop( )
- public boolean isEmpty( )
- public int size ( )
- public void removeAll()
You now need to implement each of these methods,
so that they perform the following tasks:
-
push() must create a new Node containing the
Object parameter value that is passed to it,
and a link to the current top node on the Stack.
It must then assign the Stack instance variable topNode
to reference the new node. (This variable is the external
reference to the linked list.) Finally, it must increment the
instance variable itemCount, which maintains the total count
of nodes (or equivalently, values).
-
pop() must first check whether the Stack is currently
empty. If so, it must immediately throw an IllegalStateException
and return without making any changes to the Stack.
Otherwise, pop() must declare a local Object variable
to reference the value in the top node, since it must return
this value on exit. Then it must effectively remove the top node,
which can be done merely by reassigning the instance variable
topNode to the next node in the linked list.
Finally, it must decrement the itemCount instance variable
and return the value that was popped.
-
isEmpty() must return true if itemCount is
0, and false otherwise. Applications can use this
method to check if a Stack is empty, before attempting to use
pop().
-
size() must return the number of values currently stored
on the Stack.
-
removeAll() must remove all values currently stored on the
Stack. This method will be invoked whenever the user clicks
the Clear button.
-
The version of the Queue class as defined in
Queue.java
contains only stubs of the following methods, all of which are
essential for the application to work correctly:
- public void add (Object item)
- public Object remove ()
- public void removeAll ()
However, Queue.java does define
all the instance variables for the Queue class as well as a
constructor and some methods that by now are familiar to you.
It also includes a fully implemented
render() method, which enables the QueuePanel
to draw the Queue object in the display area of the window.
Before proceeding, you should look over the declarations for
both the instance variables and the constructor.. As
usual, these are near the top of the class definition.
Now proceed to implement the bodies of the methods listed above,
so that they perform the following tasks:
-
add() must create a new Node containing the value
parameter, and a link defined to be null (since this node will
become the new last node in the Queue. Then it must
append the new node to the end of the current linked list
(remember, a queue is a FIFO list). You can normally
append a new node in two steps: first, change the internal link
in the existing rear node (identified by the instance
variable rearNode) to reference the new node. Then change
rearNode itself, so that it now references the new node.
However, there is a special case to consider here, namely that of
adding to a queue that is currently empty. Your method will
have to handle that case differently from what was described above...
Finally, add() must increment the instance variable itemCount,
which keeps track of the current number of stored values.
-
remove() must first check whether the Queue is currently
empty. If so, it must immediately throw an IllegalStateException
and return without making any changes to the Queue.
Otherwise, the method should first declare a local reference to the
value in the front node (the one referenced by the frontNode
instance variable), since on exit it must return this value. Then it
must remove the front node and decrement the itemCount
instance variable before returning the value that was removed.
Note that there is a special case to consider, namely that of
removing the last value in a Queue (in other words,
going from one to zero values). That case has to be handled at least
somewhat differently...
-
removeAll() must remove all values from the Queue.
Your version of this method should be only slightly different from
the same method you wrote for the Stack.
-
The version of the List class as defined in
List.java
contains only stubs of the following methods, all of which are
essential for the application to work correctly:
- public void add (int index, Object item)
- public void set (int index, Object item)
- public Object remove (int index)
- public Object get (int index)
Note, however, that
List.java does define all the
instance variables for the List class as well as a working
constructor. It also includes a fully implemented
render() method, which enables the ListPanel
to draw the List object.
And it even contains complete implementations of several methods
that are essentially identical to Stack and Queue
methods you wrote earlier.
Before proceeding, you should look over the declarations for
both the instance variables and the constructor. As usual, both
are near the top of the class definition.
Now proceed to implement the bodies of the methods listed above,
so that they perform the following tasks:
-
add() must first check whether the specified index is
in range. In this case the index must either correspond
to an existing value, or it may be just one position beyond the
last stored value. In other words, add() will not be allowed
to create any indexing gaps in the list. If it turns out that the index
is not in range, the method must immediately throw an
IndexOutOfBoundsException.
Otherwise, add() must go on to put its
value parameter into a new Node and insert that node into
the position marked by the index parameter.
To locate the proper insertion point within the linked list, you will
need to set up a loop that advances a temporary Node
reference from the front node to the node at location index.
As it turns out, for additions and removals you will actually need
two references, namely one on the "current" node and another
just one step behind it. This is because you will need to change
the internal link in the node just before the node at
index.
Finally, add() must increment the List
instance variable itemCount, which keeps track of the
current number of stored values.
Note: there are several special cases to be considered here,
namely
-
adding to a currently empty list
-
adding to the front of a nonempty list (inserting a new value
at index 0)
-
adding to the rear of a nonempty list (appending a new value
at index itemCount)
-
set() must first check whether the specified
index actually matches a value currently in the list
(that is, whether it is in range). If not, it must immediately
throw an IndexOutOfBoundsException and return without making
any changes to the List.
Otherwise, the method must replace the value currently stored
at the specified index by the specified new value.
It also must return the value that was replaced.
-
remove() must first check whether the specified
index actually matches a value stored in the list
(that is, whether it is in range). If not, it must immediately
throw an IndexOutOfBoundsException and return without making
any changes to the List.
Otherwise, the method must declare a local reference to the
value in the node indicated by the specified index, since on exit
it must return this value. Then it must remove that node,
which effectively will shift all components
beyond this index downward by one position.
Finally, remove() must decrement the itemCount
instance variable before returning the value that was removed.
Note: once again there are special cases to consider, namely
-
removing the only value in a list (going from one to zero
values)
-
removing the first value in a list with two or more values
-
removing the last value in a list with two or more values
-
get() must first check whether the specified
index actually matches a value stored in the list
(that is, whether it is in range). If not, it must immediately
throw an IndexOutOfBoundsException.
Otherwise, the method must return a reference to the
value in the node indicated by the specified index,
without changing the state of the List in any way.
-
Once you have completed your new implementations of the
Stack, Queue, and List classes, try to build
your project. Of course if you encounter any compiler errors, you will
have to fix them all before you can proceed...
-
Run the project. You should now test and debug the behavior
of each class as necessary. You should experiment with several sequences
of adding and removing data, and be sure to check out all the special
cases mentioned above. Verify in all cases that the graphical display
of each list type changes in the way you would expect.
What To Submit
When your project is complete and working correctly, demonstrate it
to your lab instructor. Then, before you exit NetBeans, clean your
Lab07 project. Finally, before you logout, open a terminal
window and use the cd command to enter your csci/202/labs
directory. Then create a JAR file of your Lab07 project folder,
using the command
jar cf Lab07Project.jar Lab07
Please leave both your project folder and Lab07Project.jar
in your csci/202/labs directory for the remainder of the
semester.