Data Structures Demystified (Demystified)

Many of the basic concepts that create a stack in C++ also create a stack in Java, as you ll see in the following example. The Stack class definition contains all the members that are found in the definition of the Stack class in the C++ example, although the format of these class definitions is slightly different.

Java doesn t permit the class definition to be grouped into private and public access specifier sections. Instead, the keywords private and public precede the name of the member. In this example, the attributes size and top and the reference to the values array are private and accessible only by a member method of the class.

Stack is a member method that is a constructor of the Stack class. Previously, you learned that a constructor is a member method that is called when an instance of the class is created. The Stack constructor requires that an integer representing the size of the stack be passed to its argument list.

Statements within the Stack constructor are similar to the statements within the Stack constructor in the C++ version of the Stack class. The first statement assigns the integer passed to the Stack constructor to the size attribute of the Stack class by using the this pointer.

The next statement declares an array of integers using the new operator, which returns a reference to the memory location of the array. This reference is assigned to the values attribute, which is a reference to an array of integers.

The last statement assigns “1 to the top attribute. As you ll recall, the top attribute contains the index of the array element that is at the top of the stack. The value “1 means that the stack is empty.

Beneath the Stack definition in this example is the definition of the StackExample application class, which is the Java application that creates an instance of the Stack class. You ll remember this statement from your Java programming class. Three things are happening here. On the right side of the assignment operator, the new operator declares an instance of the Stack class and passes 10 to the constructor as the size of the stack. On the left side of the assignment operator, the statement declares a reference to an instance of the Stack class called myStack . The last step is that the assignment operator assigns a reference to the instance of the Stack class returned by the new operator to the myStack reference. You ll then use the myStack reference to access public members of the Stack class.

public class Stack { private int size; private int top; private int[] values; public Stack(int size) { this.size = size; values = new int[size]; top = -1; } } public class StackExample { void main(String args[]){ Stack myStack = new Stack(10); } }

Creating a Push Member Method in Java

The Java versions of the push() member method also require that you define an isFull() member method to determine if room is available to place another value on the stack. The next example shows the definition of the isFull() member method.

Notice that this is nearly identical to the C++ version, with two exceptions. The method name begins with the keyword public making it callable from within the program using the instance of the Stack class. In the C++ version, the isFull() member method was placed beneath the public access specifier section of the class definition. The other difference is the keyword that designates the data type of the return value. In C++, bool is the keyword for a Boolean data type; the equivalent in Java is boolean .

Inside the isFull() member method, the condition expression in the if statement determines if the value of the top attribute (index) is less than one less the value of the size attribute (total number of array elements).

public boolean isFull() { if(top < size-1) { return false; } else { return true; } }

The Java version of the push() member method is defined in the next example. This too is nearly identical to the C++ push() member function except the keyword public precedes the signature of the member method.

The statement calling the push() member method passes it the value that is to be placed on the top of the stack. This value is assigned to the variable x . Inside the method, the isFull() member method is called in the condition expression of the if statement to determine if there is room for the new value on the stack. As with C++, you must reverse the logic of the value returned by the isFull() member method by using the exclamation point. That is, when a false is returned (room is available on the stack), the condition expression treats it as true , enabling statements within the if statement to be executed.

The first statement in the if statement increments the value of the top attribute, which you ll remember is an index. The other statement assigns the value of the variable x to the array element.

public void push(int x) { if(!isFull()) { top++; values[top] = x; } }

Creating a Pop Member Method in Java

Two methods must be defined to pop a value off the top of the stack in Java. These are isEmpty() and pop() , both of which are similar to the C++ versions. The isEmpty() member method, shown in the next example, determines if there is a value at the top of the stack by comparing the value of the top attribute to “1. The value “1 is the initial value of the top attribute when the instance of the Stack class is declared. The comparison is made in the condition expression of the if statement. Depending on the result of the comparison, either a true or a false is returned.

public boolean isEmpty() { if(top == -1) { return true; } else { return false; } }

The pop() member method that is defined in the next example works the same way as the C++ version. First, an integer variable called retVal is declared and initialized to 0. This stores the value that is popped off the top of the stack and returned to the statement that calls the pop() member method.

The isEmpty() member method is called in the condition expression of the if statement to determine if there is a value at the top of the stack. Again, the exclamation point must be used to reverse the logic of the value returned by the isEmpty() member method. A false is returned if there is a value at the top of the stack. The exclamation point makes this a true enabling statement within the if statement to execute.

The first statement within the if statement assigns the value of the top element of the stack to the retVal variable. The other statement decrements the value of the top attribute, which brings the next index of the array to the top of the stack.

The last statement in the pop() member method returns the value of the variable retVal .

public int pop() { int retVal = 0; if(!isEmpty()) { retVal = values[top]; top--; } return retVal; }