CSCI 1103 Lab10: Stack Data Structures
- Due: 11:59pm Monday 11/20/2017
- Approximately 0.83% of total grade
- Submit to Canvas
- You may work with one partner on this lab but both partners must submit files and be physically present for Check-offs
- Lab exercises are open resource/open collaboration. You may freely discuss lab topics with other members of the class.
CODE DISTRIBUTION: lab10-code.zip
- Download the code distribution every lab
- See further setup instructions below
CHANGELOG:
- Mon Nov 13 16:43:34 CST 2017
- Some clarification has been added to the documentation for the
getTop()
method of both stacks: calling this method on an empty stack should raise aRuntimeException
with the messageStack empty
. Read more on how to do this in the section on throwing exceptions.
1 Rationale
Data structures provide a means to store, retrieve, and manipulate information in common patterns. The Stack data structure is a simple, linear arrangement of data which comes up frequently enough to merit discussion as an independent entity and is the focus of this lab. Implementing a growable stack illustrates memory allocation within a data structure and also underscores the private field/public method principles of object-oriented design which have been covered in the course so far.
Associated Reading
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.
2 Download Lab Code and Setup
As in Lab01, download the code pack linked at the top of the page. Unzip this which will create a folder and create your files in that folder.
File | State | Notes |
---|---|---|
PARTNERS.txt | Edit | Fill in your name and the name of your partner in this text file |
TextIO.java | Provided | Allows easy input calls like TextIO.getInt() |
KTests.java | Testing | Utility routines for all tests |
junit-1103.jar | Testing | For testing, don't try to edit this one |
FixedStack.java | Create | Class to write for Problem 1 |
FixedStackTests.java | Testing | Tests for Problem 1 |
GrowableStack.java | Create | Class to write for Problem 2 |
GrowableStackTests.java | Testing | Tests for Problem 2 |
3 Overview
The function call stack has been discussed a great deal in lecture as a means for several functions/methods to be in use at once, communicate parameters and return values between them, and allow for flexible programming. This area of memory is named after the stack data structure which has very simple semantics that mirror a stack of heavy objects such as books.
- Stacks contain many objects but only the top one is easily accessible
with
getTop()
- Additional objects can be added to a stack by
push(x)
so thatx
becomes the new top object - The top object can be removed via a call to
pop()
which will uncover the next lower object
Figure 1: The push and pop operations on a stack from Wikipedia.
This lab focuses on implementing stacks using arrays but there are other ways to implement them such as using linked nodes.
The lab will implement two versions of a stack using arrays.
- A
FixedStack
with a fixed maximum size. This version uses an array with a size dictated at when the stack is constructed. If too many elementspush()
'ed onto the stack, errors will result. - A
GrowableStack
which will always allow more elements to bepush()
'ed onto it. If the array in use by the stack is not large enough, a larger array is allocated, elements are copied over, and the stack begins using the larger array.
4 Problem 1: Fixed Size Stack
Write all your code in the FixedStack.java
file. Importantly,
all of the fields of this class should have private
access
modifiers. This prevents changes to those variables by entities
outside the class and allows the relationships between the variables
to be preserved.
4.1 Sample Session
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
4.2 Class Structure of FixedStack
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 }
4.3 Implementation Notes for FixedStack
Fields
At a minimum the FixedStack
will need two fields
- An array of
String
elements which is allocated during the constructor sized according to themaxCapacity
parameter - An integer which tracks the size of the stack which is the number of elements in the stack at any time.
Both these fields should be private. It is not likely additional fields will be needed and more will likely complicate the implementation as it will require additional data to be coordinated as the stack changes.
Basic accessors
The basic accessors such as getSize()
and getCapacity()
will
return fields directly or aspects of fields such as the length of the
array of contents. Other accessors such isEmpty()
and isFull()
can determine their answer via simple comparisons between the basic
fields.
Position of Top Element
The "top" element in the stack should be at a high index. Thus
- The first push should put an element at index 0
- Second push at index 1
- Third at index 2
- etc.
Popping elements should remove the last index that was pushed: after pushing 4 times, the top element is at index 3 so a pop should remove it.
Removing elements is accomplished simply by setting an array element
to null
and decreasing the size of the stack. Any elements in the
array that have not been pushed onto should be null
.
String Representations
There are two ways to show the stack as a string
toString()
shows the size of the stack and all elements in the stack from top to bottom. This means reading the elements of the array in reverse order, high index to low index.contentsString()
shows the capacity of stack and the entire contents of the underlying array from low index to high index. This includes slots of the array beyond the size of the stack which should all benull
.
Build up the string version of the stack in a loop using a patter like the following.
String str = "something here\n"; for(...){ str += "more stuff"; } return str;
Throwing Exceptions
When too many elements are push()
'ed onto the stack or too few are
present for a pop()
or getTop()
, throw a RuntimeException
. This
is the Java mechanism to indicate an error has occurred. I can be done
with the following line:
if(something is wrong){ throw new RuntimeException("Here is what's wrong"); // this line throws an exception }
Under most circumstances this should terminate the program being run
such as in a main()
method however there are methods that can allow
a program to handle an exception and proceed. These are not covered in
this lab.
5 Problem 2: Growable Stack
Write your code in the file GrowableArray.java
. A good first step is
to copy over FixedStack.java
and edit it to account for the changes
below.
A major limitation of the FixedStack
is that there is a limit to the
number of elements that can be pushed onto it. This requires uses to
know ahead of time the maximum capacity of the stack which never
changes.
The GrowableStack
will overcome this limitation as follows.
- The
initialCapacity
is given at construction time and dictates the size of the backing array at first. - If the stack becomes full and another push is performed, a larger array is allocated. All elements from the previous array are copied over to the new array and the stack begins referring to the new array.
- When this expansion occurs, the larger array is allocated as
twice as big as the old array. This means that many more pushes
can happen before another expansion is required giving the
GrowableStack
better performance properties for many pushes.
Aside from altering the push()
operation to allow expansion when
needed and always returning false
for isFull()
, the
GrowableStack
is identical to FixedStack
. This means copying over
code from FixedStack
is a good first step.
5.1 Demo
Welcome to DrJava. > GrowableStack stack = new GrowableStack(2); // initial capacity of 2 > stack.push("A") // push 2 elements on > stack.push("B") > stack.contentsString() // contents are full capacity: 2 0 : A 1 : B > stack.getSize() // size is equal to capacity 2 > stack.getCapacity() 2 > stack.isFull() // stack is not full: can grow false > stack.push("C") // push another element > stack.toString() // push is honored, element at top of stack size: 3 2 : C 1 : B 0 : A > stack.contentsString() // stack expands: capacity doubles capacity: 4 // larger array allocated: twice as big 0 : A // old elements copied into new array 1 : B // stack pointed at new larger array 2 : C // new element can be added 3 : null // extra space for next pushes > stack.getSize() 3 > stack.getCapacity() // capacaity has doubled 4 > stack.push("D") // size and capacity both 4 > stack.isFull() // still not full: can grow false > stack.contentsString() capacity: 4 0 : A 1 : B 2 : C 3 : D > stack.push("E") // pushing 5 element triggers expansion > stack.contentsString() capacity: 8 // capacity doubled from 4 to 8 0 : A // copied old elements into larger array 1 : B 2 : C 3 : D 4 : E // added in new element 5 : null // extra space for furhter pushes 6 : null 7 : null > stack.getCapacity() // capacity now 8 8 > stack.getSize() 5 > stack.toString() size: 5 4 : E 3 : D 2 : C 1 : B 0 : A > stack.pop() // popping elements does not decrase capacity > stack.pop() > stack.toString() // 3 elements in stack size: 3 2 : C 1 : B 0 : A > stack.contentsString() // capacity stays at 8 capacity: 8 0 : A 1 : B 2 : C 3 : null 4 : null 5 : null 6 : null 7 : null > stack.getCapacity() 8
5.2 Class Structure of GrowableStack
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 }
5.3 Implementation Notes for GrowableStack
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.
6 Getting Credit for this Lab
6.1 Demonstrate your code to Lab Staff (40%)
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.
6.2 Zip and Submit (60%)
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