Programming Activity 14-1 Guidance ================================== Fields ------ Your will write your code in StackArray.java, which is an array based implementation of a stack. The StackArray class has 2 private fields that you can directly access in your code: private int[] stack; private int top; stack is an array of integers that will store the stack values. top is an index to the current top of the stack. A top value of -1, which is an invalid index, is used to indicate when the stack is empty. StackArray provides 2 public accessor functions for other classes to get the values of these private fields. Stack top --------- The top of a stack refers to an occupied place, not an empty place. Consider, for example, a stack of plates. If the stack of plates is not empty, a plate is at its top. Refer to figure 14.11a for an example. When you add (put) an item on a stack, you must first increment its top index. When you remove (pop) an item from a stack, you must decrement its top index. If the stack becomes empty, you must set the top index to -1. Part 1 (push) ------------- The framework comments say: "The push method adds the argument value to the top of the stack, if it is possible" Remember that "argument value" is just another way to say "parameter value". For the "push" function, the parameter here is named "value" and it is an int. What do they mean by "if it is possible"? They mean as long as there is still room to add another item. Understand that they told us that this stack has a limited capacity. The framework comments say: "CAPACITY is a constant instance variable representing the size of the array stack" The first thing you must do is make sure there is room for another item. You must compare "top" to "CAPACITY" in some way that understands that top is a 0-relative index into the stack array and CAPACITY is the size (max number of items allowed in this array). If top is already at the limit level, you must display the following message to the system console: "Stack is full: cannot push " + value and then return false, which takes your flow out of the function. BELOW your if block, you know you have room to add the new item to the stack because the flow would not continue there if it took the return false path. You need to add a new item and you know you have room in the stack array. Change the top index to the next available array slot. Use this new value of top to assign the new item to this array slot. The new item is passed into the push function as the parameter "value". After you add the value via an assignment statement, remember that your function must return a boolean (true or false). Since you added an item at this point, you return true. Part 2 (pop) ------------ The best place to start with any function is to examine how it is declared. What are its parameters? What is its return type? Does it throw any exceptions? You can see that the pop() function takes no parameters and returns an int value. You can also see that it might throw a DataStructureException exception (if it encounters a certain situation). Let's start by asking when your code will need to throw the exception. The purpose of the pop function is to return the top item on the stack. If the stack is currently empty, then this cannot be done. The first thing you will check is if the stack is empty, which is indicated by a top value of -1. If the stack is empty you must throw the exception. This exception should be instantiated with the following message text: "Stack is empty: cannot pop" When you throw an exception, that takes you out of the flow right then and there, so there is no need to have any return statement after the throw statement. Review the section on exceptions to see how to throw the exception. BELOW the above "if" block, you know that the stack is not empty. You could not possibly reach that place in your code if your stack was empty because your thrown exception would have taken you out of the pop function. What do you need to do next? First, you need to get the top item into an int local variable. You do this by using the "top" index into the "stack" array. Next, you must adjust the "top" index to make it refer to a new top item. This new top is obviously the item underneath (below) the current top. You must have first obtained the current top item before you change the top index. After adjusting the top index, return the item you obtained, which was saved in the local variable mentioned above. Comments -------- The source code method header comments contain important information about what the method is supposed to do and what it is supposed to return.

============================================================

You will write the code in the "bold" areas saying "student code starts here"

import java.awt.Graphics; import javax.swing.JFrame; import java.awt.Color;

public class StackArray { public static final int CAPACITY = 10;

private int[] stack; private int top;

public StackArray() { stack = new int[CAPACITY]; top = -1; }

public int get(int index) { return stack[index]; }

public int getTop() { return top; }

/** * push method * * @param value value to be pushed onto the stack * @return true if successful, false if unsuccessful */ public boolean push(int value) { // ***** 1. Student code starts here ***** // stack is an int array instance variable representing // the array that stores our stack

// top is an instance variable representing // the index of the top of the stack // CAPACITY is a constant instance variable representing // the size of the array stack // The push method adds the argument value // to the top of the stack, if it is possible // code the push method here // Part 1 student code starts here:

return true; // replace this dummy return statement

// Part 1 student code ends here. }

/** * pop method * * @return the value of the top element of the stack, if successful */ public int pop() throws DataStructureException { // ***** 2. Student code restarts here ***** // stack is an int array instance variable representing // the array that stores our stack

// top is an instance variable representing // the index of the top of the stack // CAPACITY is a constant instance variable representing // the size of the array stack // The pop method deletes the element // at the top of the stack, if it is possible // Code the pop method here // Part 2 student code starts here:

return 0; // replace this dummy return statement

// Part 2 student code ends here. } }

=========================================

OUTPUT OF COMPLIDED CODE:

Example Programming Activity 14-1 Output Start of program Push or pop push pop top After pushing 12 Push or pop push pop successfuy pushed 12 5 top 12 After pushing more items to fill up the stack: Push or pop pus hpop lop 9 67 successfuy pushed 55 100 5 14 13 12 Failed to push: dieit-Actvity-14-1 -Nelleans I File Edi View avigane Source Fefactee Run Debug Frofie Teare Tools Wndew Help onfg Rx.rr. Pecseng DataSTuctreExcepton output dseitz Activity 141 (run) N> Stack 28 full; cennos pasa 10 bush Do0 op 9 fa led bo gush 10 pop- Navigetor Hembers 12 -CAPACITY : nt sack: it ] bop: Int tz-Activity-141 (n) d 9:38 PM Note the error messages on the pop-up window and also on the system console. After popping a few items (through 7): Push or pop push pop 45 67 successfu popped7 100 5 top 4 14 13 12 Popped more items until the stack is empty. Now about to try popping from an empty stack: Push or pop push pop 45 67 successfuy popped 12 100 5 14 13 12 1op Failed to pop dieit-Actvity-14-1 -Nelleans I File Edi View avigane Source Fefactee Run Debug Frofie Teare Tools Wndew Help onfg Rx.rr. Pecseng DataSTuctreExcepton output dseitz Activity 141 (run) Stack 1.8 fall; cenno pasa 10 Stack a, ptr; cannot pop l Pusl or pop 67 allasd to pop pop- Navigetor Hembers 100 13 -CAPACITY : nt sack: it ] bop: Int 942 PM Note the error messages on the pop-up window and also on the system console