CSCI 1103 Lab10: Stack Data Structures

Material from Eck Ch 5 is covered in this lab. The stack data structure is discussed in Ch 9.3.1 but implemented there differently there than this lab: the text uses linked nodes rather than contiguous arrays. This technique will be discussed later in class.

Examine the following session which shows how instances of the FixedStack class behave. This session gives insight into which methods need to be in the class and how they affect the object.

Welcome to DrJava.
> FixedStack stack = new FixedStack(3);  // create with capacity 3
> stack.getSize()                        // initially no elements
0
> stack.getCapacity()                    // max capacity 3
3
> stack.isEmpty()                        // is empty initially
true
> stack.isFull()                         // not full
false
> stack.toString()                       // no elements yet
size: 0

> stack.contentsString()                 // all elements null
capacity: 3
0 : null
1 : null
2 : null

> stack.push("A")                        // put a single element on top
> stack.getSize()                        // now 1 element
1
> stack.getCapacity()                    // capacity is always the same
3
> stack.isEmpty()                        // no longer empty
false
> stack.isFull()                         // but not full
false
> stack.toString()                       // show size and single element
size: 1
0 : A                                    // ordered top to bottom

> stack.contentsString()                 // contents no longer all null
capacity: 3
0 : A
1 : null
2 : null

> String t = stack.getTop();             // can retrieve top element
> t
A                                        // only thing present
> stack.getTop();                        
A                                        // only thing present


> stack.push("B")                        // put another element int
> stack.getSize()                        // now two elements present
2
> stack.getCapacity()
3
> stack.isEmpty()
false
> stack.isFull()
false
> stack.toString()                       // new top element is B
size: 2
1 : B
0 : A

> stack.contentsString()
capacity: 3
0 : A
1 : B
2 : null


> stack.push("C")                        // put 3rd element in
> stack.getSize()                        // size and capacity now equal
3
> stack.getCapacity()
3
> stack.isEmpty()
false
> stack.isFull()                         // size==capacity so is full
true
> stack.toString()                       // string is from top to bottom
size: 3
2 : C
1 : B
0 : A

> stack.contentsString()                 // contents from 0 to last, top is at end of array
capacity: 3
0 : A
1 : B
2 : C

> stack.getTop()                         // top is most recently added element
C

> stack.push("D")                        // no longer capacity for more
java.lang.RuntimeException: Stack full   // exception results
    FixedStack.push(FixedStack.java:54)
> stack.getSize()                        // size is unchanged
3
> stack.contentsString()                 // contents unchanged
capacity: 3
0 : A
1 : B
2 : C

> stack.getTop()                         // top unchanged due to failure to push
C


> stack.pop()                            // remove the top element
> stack.getTop()                         // top element is now whatever was below
B
> stack.toString()                       // show remaining elements
size: 2
1 : B
0 : A

> stack.contentsString()                 // last element of array has been eliminated
capacity: 3
0 : A
1 : B
2 : null

> stack.pop()                            // remove another element
> stack.getTop()                         // top element changed
A
> stack.pop()                            // remove another element
> stack.getSize()                        // no elements left
0
> stack.isEmpty()                        // size==0
true
> stack.contentsString()                 // all elements nulled out
capacity: 3
0 : null
1 : null
2 : null

> stack.getTop()                         // no elemenets to retrieve
java.lang.RuntimeException: Stack empty
  at FixedStack.getTop(FixedStack.java:44)
> stack.pop()                            // cannot pop if empty
java.lang.RuntimeException: Stack empty
  at FixedStack.pop(FixedStack.java:65)
> stack.toString()                       // show emptiness of stack
size: 0

Below is an outline of the public methods in the FixedClass class. Additional details on how to implement the class are discussed in the next section. The fields required for the class are not shown and should be inferred by the coder.

public class FixedStack{
// A fixed size stack allowing elements to be pushed into and popped
// from it. The maximum capacity of the stack is determined at
// construction time and the stack throws exceptions if too many
// elements are pushed into it.

  public FixedStack(int maxCapacity);
  // Create a stack with the given maximum capacity. Initialize the
  // internal array of contents to the given size and set the current
  // size of the stack to 0.

  public int getCapacity();
  // Return the length of the internal array in the stack.

  public int getSize();
  // Return the number of elements that are in the stack. These are
  // the elements that have been push()'ed but not pop()'ed.

  public boolean isEmpty();
  // Return true if the size of the stack is 0 and false otherwise.

  public boolean isFull();
  // Return true if the size of the stack is equal to its capacity and
  // false otherwise. If the stack is full, calling push() will raise
  // an exception.

  public String getTop();
  // Return the "top" element in the stack which is the last element
  // to be push()'ed into the stack.  If the stack is empty, there is
  // no top element so throw a RuntimeException with the message
  // "Stack empty".

  public void push(String x);
  // If the stack is full (size==capacity), throw a runtime exception
  // with the message "Stack full".  Otherwise add the new element x
  // into the stack at the "top" and increase the size.

  public void pop();
  // If the stack is empty (size==0), throw a runtime exception with
  // the message "Stack empty". Otherwise, remove the top element of
  // the stack decreasing its size.

  public String toString();
  // Create a string representation of stack. Show the size, then the
  // top element of the stack first on its own line, then the next to
  // top and so on to the bottom element. This method should only show
  // elements that have been pushed but not popped. An example of a
  // stack with size 4:
  //
  // size: 4
  // 0 : A
  // 1 : B
  // 2 : C
  // 3 : D

  public String contentsString();
  // Create a string indicating the contents of the internal array of
  // the stack which is ordered from 0th to last element of the
  // array. This method may show slots in the array where elements
  // have been popped off. An example of a stack with capacity 5 and
  // size 3:
  // 
  // capacity: 5
  // 0 : A
  // 1 : B
  // 2 : C
  // 3 : null
  // 4 : null

}

Below is an outline of the public methods in the GrowableStack class. Additional details on how to implement the class are discussed in the next section. The fields required for the class are not shown and should be inferred by the coder.

public class GrowableStack{
// A growable stack which allowing elements to be pushed into and popped
// from it. The initial capacity of the stack is determined at
// construction time. If enough elements are pushed onto the stack, a
// new internal array with twice the length of the original is created
// and used subsequently by the stack.  Thus this stack never fails on
// push() operations and always returns false for calls to isFull().

  public GrowableStack(int initialCapacity);
  // Create a stack with the given initial capacity. Initialize the
  // internal array of contents to the given size and set the current
  // size of the stack to 0.

  public void push(String x);
  // If the stack is full (size==capacity), allocate a new array for
  // the stack which is twice as large as the old array and copy the
  // current elements into it.  Assign the stack to refer the new
  // contents and proceed to push the new element x onto the stack.
  // This method should never fail to push new elements.

  public boolean isFull();
  // Always return false as this stack will grow when required even if
  // size is equal to capacity.

  public int getCapacity();
  // Return the length of the internal array in the stack.

  public int getSize();
  // Return the number of elements that are in the stack. These are
  // the elements that have been push()'ed but not pop()'ed.

  public boolean isEmpty();
  // Return true if the size of the stack is 0 and false otherwise.

  public String getTop();
  // Return the "top" element in the stack which is the last element
  // to be push()'ed into the stack. If the stack is empty, there is
  // no top element so throw a RuntimeException with the message
  // "Stack empty".

  public void pop();
  // If the stack is empty (size==0), throw a runtime exception with
  // the message "Stack empty". Otherwise, remove the top element of
  // the stack decreasing its size.

  public String toString();
  // Create a string representation of stack. Show the size, then the
  // top element of the stack first on its own line, then the next to
  // top and so on to the bottom element. This method should only show
  // elements that have been pushed but not popped. An example of a
  // stack with size 4:
  //
  // size: 4
  // 0 : A
  // 1 : B
  // 2 : C
  // 3 : D

  public String contentsString();
  // Create a string indicating the contents of the internal array of
  // the stack which is ordered from 0th to last element of the
  // array. This method may show slots in the array where elements
  // have been popped off. An example of a stack with capacity 5 and
  // size 3:
  // 
  // capacity: 5
  // 0 : A
  // 1 : B
  // 2 : C
  // 3 : null
  // 4 : null

}

The main change to make for GrowableStack is to alter push(x) so that it performs expansion when needed. The basic approach here is as follows.

field CONTENTS[] is array of stack contents
field SIZE indicates the count of elements in the stack

PUSH(X) for GrowabaleStack {
  if SIZE equals length of CONTENTS{
    // must expand as CONTENTS is full
    create array NEW_CONTENTS[] twice as long as CONTENTS
    use a loop to copy all elements form CONTENTS to NEW_CONTENTS
    set this.CONTENTS to point at NEW_CONTENTS to start using the new array
  }
  add in X at index SIZE of CONTENTS
  increment SIZE
}

Ensure that the new contents array is double the size of the original contents. This allows additional push() operations to proceed without the need for expansion.

Also make sure to modify the isFull() method to always return false.

You should feel free at any time to get help from lab staff as you get stuck on the exercises.

By the end of the lab, make sure to demonstrate your code to a staff member. This will ensure that you receive full credit on the lab. Staff might ask you to

• Change what is printed
• Compile and run on the command line
• Run tests in DrJava or on the command line
• Show how to zip the folder with your programs in it

Be ready to do any or all of these.

Ensure that file PARTNERS.txt has your name and the name of your partner in it. This fill is located with the other Java files for the lab and can be edited with DrJava.

Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to blackboard.

On Canvas:

• Click on the Assignments section
• Click on the appropriate link for this lab
• Scroll down to "Attach a File"
• Click "Browse My Computer"
• Select you Zip file and press OK