Java, Java, Java: Object-Oriented Problem Solving, 2022E

Subsection 16.11.1

1. Explain the difference between each of the following pairs of terms:

   1. Stack and queue.
   2. Static structure and dynamic structure.
   3. Data structure and Abstract Data Type.
   4. Push and pop.
   5. Enqueue and dequeue.
   6. Linked list and node.
2. Fill in the blanks.

   1. An Abstract Data Type consists of two main parts: __________ and __________ .
   2. An object that contains a variable that refers to an object of the same class is a __________ .
   3. One application for a __________ is to manage the method call and returns in a computer program.
   4. One application for a __________ is to balance the parentheses in an arithmetic expression.
   5. A __________ operation is one that starts at the beginning of a list and processes each element.
   6. A vector is an example of a __________ data structure.
   7. An array is an example of a __________ data structure.
   8. By default, the initial value of a reference variable is __________ .
3. Add a removeAt() method to the List class to return the object at a certain index location in the list. This method should take an int parameter, specifying the object’s position in the list, and it should return an Object.
4. Add an insertAt() method to the List class that will insert an object at a certain position in the list. This method should take two parameters, the Object to be inserted, and an int to designate where to insert it. It should return a boolean to indicate whether the insertion was successful.
5. Add a removeAll() method to the List class. This void method should remove all the members of the list.
6. Write an int method named size() that returns the number of elements in a List.
7. Write an boolean method named contains(Object o) that returns true if its Object parameter is contained in the list.
8. The head of a list is the first element in the list. The tail of a list consists of all the elements except the head. Write a method named tail() that returns a reference to the tail of the list. Its return value should be Node.
9. Write a program that uses the ListADT to store a list of 100 random floating-point numbers. Write methods to calculate the average of the numbers.
10. Write a program that uses the ListADT to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.
11. Write a program that creates a copy of a List. It is necessary to copy each node of the list. This will require that you create new nodes that are copies of the nodes in the original list. To simplify this task, define a copy constructor for your node class and then use that to make copies of each node of the list.
12. Write a program that uses a StackADT to determine if a string is a palindrome—spelled the same way backward and forward.
13. Design and write a program that uses a Stack to determine whether a parenthesized expression is well-formed. Such an expression is well formed only if there is a closing parenthesis for each opening parenthesis.
14. Design and write a program that uses Stack s to determine whether an expression involving both parentheses and square brackets is well formed.
15. Write a program that links two lists together, appending the second list to the end of the first list.
16. Design a Stack class that uses a ArrayList instead of a linked list to store its elements. This is the way Java’s Stack class is defined.
17. Design a Queue class that uses a ArrayList instead of a linked list to store its elements.
18. Write a program that uses the List<E> and LinkedList<E> classes to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.
19. Write an implementation of the insert() method of the PhoneTree class described at the end of this chapter.
20. Write an implementation of the insert() method of the PhoneTreeNode class described at the end of this chapter.
21. Challenge: Design a List class, similar in functionality to the one we designed in this chapter, that uses an array to store the list’s elements. Set it up so that the middle of the array is where the first element is placed. That way you can still insert at both the front and rear of the list. One limitation of this approach is that, unlike a linked list, an array has a fixed size. Allow the user to set the initial size of the array in a constructor, but if the array becomes full, don’t allow any further insertions.
22. Challenge: Add a method to the program in the previous exercise that lets the user increase the size of the array used to store the list.
23. Challenge: Recursion is a useful technique for list processing. Write recursive versions of the print() method and the lookup-by-name method for the PhoneList. (Hint: The base case in processing a list is the empty list. The recursive case should handle the head of the list and then recurse on the tail of the list. The tail of the list is everything but the first element.) Challenge: Design an OrderedList class. An ordered list is one that keeps its elements in order. For example, if it’s an ordered list of integers, then the first integer is less than or equal to the second, the second is less than or equal to the third, and so on. If it’s an ordered list of employees, then perhaps the employees are stored in order according to their social security numbers. The OrderedList class should contain an insert(Object o) method that inserts its object in the proper order. One major challenge in this project is designing your class so that it will work for any kind of object. (Hint: Define an Orderable interface that defines an abstract precedes() method. Then define a subclass of Node that implements Orderable. This will let you compare any two Node s to see which one comes before the other.)