University of North Carolina at Asheville

CSCI 202: Introduction to Data Structures


Lab 07: Linked Stacks, Queues, and Lists

[Introduction] [Instructions] [What To Submit]


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:

  1. 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.
  2. 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.

    DisplayFrame.java DisplayPanel.java StackPanel.java QueuePanel.java ListPanel.java Paintable.java

    Stack.java Queue.java List.java

  3. Open the file lab07.Main and add the following lines of code into its main() method:
    	DisplayFrame frame = new DisplayFrame();
    	frame.setVisible(true);
    
  4. 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.
  5. 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:

    1. public void push(Object value)
    2. public Object pop( )
    3. public boolean isEmpty( )
    4. public int size ( )
    5. public void removeAll()

    You now need to implement each of these methods, so that they perform the following tasks:

    1. 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).
    2. 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.
    3. 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().
    4. size() must return the number of values currently stored on the Stack.
    5. removeAll() must remove all values currently stored on the Stack. This method will be invoked whenever the user clicks the Clear button.
  6. 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:

    1. public void add (Object item)
    2. public Object remove ()
    3. 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:

    1. 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.

    2. 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...

    3. 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.

  7. 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:

    1. public void add (int index, Object item)
    2. public void set (int index, Object item)
    3. public Object remove (int index)
    4. 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:

    1. 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)
    2. 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.

    3. 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.

    4. Note: once again there are special cases to consider, namely

    5. 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.

  8. 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...
  9. 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.