8.5 Partially Filled Arrays

Up to now, we have assumed that arrays are always exactly the right size - the number of elements is equal to the length of the array. Often, however, we are faced with situations where the size of an array is not known in advance. To handle such situations, we must modify our approach slightly.

A simple solution to the problem is to create an array whose length is great enough to hold the maximum number of items that we will ever need and then have another variable keep track of the current size of the array - the number of cells that are currently occupied by data. Although it is not necessary to do so, we think that it is a good idea to always identify the current size in a consistent way. We will always identify these variables using the array name followed by Size. 





   

      
Example 1
Assuming that MAX_LIST_LENGTH has a value of 100, then the fragment 


double list = new double[MAX_LIST_LENGTH];
int listSize = 0;

creates a double array called list whose maximum size is 100 (available
in the variable list.length) and whose current size is initialized to zero
(available in the variable listSize).
      

   







	To add a new element to such an array, we must update the current
size when an item is added. In addition, before adding a new item, we
must check that there is room in the array. Even though we set the array's
length to be as large as we would ever need, it is almost certain that, if
a program is run often enough, all estimates of maxima and minima will
eventually be exceeded.

If an array is full when we try to add an element, we can solve that
problem by making the array larger. We cannot do this directly during
program execution since an array's size is fixed at declaration. We can,
however, do it indirectly in the following way. We first create a new array
that is larger than the original, then copy all the element~ of the original
array into the temporary one, and finally set the original array reference
to the new array.





   

      
Example 2
The fragment shown here adds an item to a partially filled array called
list. If there is no room in list, the fragment doubles its size before
adding the new element.

if (listSize == list.length)
{
   //array too small - double its size
   double[] temp = new double [2*list.length];
   for (int i = 0; i < list.length; i++)
      temp[i] = list[i];
   list = temp;
}
list [listSize] = item;
listSize++;











The diagrams show the effect of adding an element if the array is already
fully occupied. (Occupied cells are indicated by the shaded regions.)



      




A stack is a list whose size can grow and shrink by inserting or deleting
items at one end of the list. The end at which insertions and deletions are
made is called the top of the stack; the other end is called the bottom of the
stack. Stacks have a physical analogy in the spring-operated mechanisms
sometimes used to store stacks of plates in cafeterias. In these devices, if
you place a new plate on the top of the stack, the added pressure pushes
the stack down a bit; if you remove a plate from the top, the decreased
pressure allows the remaining plates to pop up a bit.






Following this analogy, to insert an item into a stack, we push it onto
the stack; to delete an item, we pop it from the stack.
To implement stacks in Java, we can use partially filled arrays." For
our stacks, we want to be able to perform the following operations:





In the class Stack that follows, when we create a new stack, we start
it with an array that will hold ten items. If the size ever proves to be
inadequate, we double the stack's capacity. Notice that the array that is
used to hold the elements of the stack and its size field are both made
private. This ensures that a user cannot manipulate the array directly.
If we ever decide to change the implementation, it will not affect the way
that the user interacts with the class.





   

      
Example 3
The following class implements the concept of a stack using partially filled
arrays of type Object. An attempt to delete an item from an empty stack
(in the pop method) will cause an exception to be thrown. The exception
will print a message and execution of the program will terminate. For
information on exceptions, see Appendix E.


class Stack
{
   private Object[] stack;
   private int stackSize;
   
   public Stack ()
   {
      // create a new, empty stack
      stack = new Object [10] ;
      stackSize = 0;
   }
   
   public void push (Object o)
   {
      //insert object o into stack
      if (stackSize == stack. length)
      {
         //array too small - double its size
         Object[] temp = new Object [2*stack.length];
         for (int i = 0; i < stack. length; i++)
            temp[i] = stack[i];
         stack = temp;
      }
      stack [stackSize] = o;
      stackSize++;
   }
   
   public Object pop ()
   {
      // remove and return object at top of stack
      if (stackSize == 0)
         throw new RuntimeException
            ("Attempt to pop empty stack");
      else
      {
         stackSize--;
         return stack [stackSize] ;
      }
   }
   
   public boolean isEmpty ()
   {
      // return true if and only if the stack is empty
      return stackSize == 0;
   }
}




   






Java actually supplies a Stack class in the package java.util with
methods for each of these operations plus some others. The implementation
used by Java is similar to that used here.






Exercise 8.5
    

  1. Complete the definition of the method get so that it returns the kth
element from a partially filled array of objects. If the array does not
have a kth element, the method should return null.

    public static Object get (Object[] list,int listSize, int k)
    2. 

  2. Write a fragment that prints the largest value in a partially filled array
of double values called scores. If the array is empty, the fragment
should print an appropriate message. Assume that the int variable
scoresSize contains the current size of the array.
    3.  
    

  3. Write a complete program that repeatedly prompts a user for positive
integers and reads those values until the user supplies a value of zero.
The program should then print the values read, in the order that they
were supplied by the user. The program should not place a restriction
on the number of values that can be read.
    4.  
    

  4. Another possible operation on stacks is usually called peek. It notes
and returns the value of the item currently at the top of the stack.
Write a method peek that could be added to the class Stack shown
in Example 3. The method should have header
    public Object peek ()
    If the stack is not empty, the method should return a reference to the object at the top of the stack. Otherwise it should throw an
exception. The method should not alter the contents of the stack.
    5.