This blog entry was motivated by the description and implementation of Java Generics in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne. The code in this post is based on their implementation. I did some minor changes.
Collections, Generics and Iterators are important concepts in object oriented programming languages. It is central to understand the reasons for them and the associated ideas. If you are interested (and you should if you work with object oriented languages) get a copy of the book and take a look at pages 132 – 141.
The following code shows an implementation of a stack using an array without implementing an Iterator:
package edu.princeton.cs.algs4;
public class FixCapacityStackOfInts {
private int[] a;
private int N;
private int totalCapacity;
// **** constructor ****
public FixCapacityStackOfInts(int cap) {
a = new int[cap];
totalCapacity = cap;
}
// **** methods ****
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void push(int item) {
if (N >= totalCapacity) {
throw new IndexOutOfBoundsException();
}
a[N++] = item;
}
public int pop() {
return a[–N];
}
// **** test ****
public static void main(String[] args) {
final int maxVal = 100;
final int maxItems = 7;
int val = 0;
FixCapacityStackOfInts stack = new FixCapacityStackOfInts(maxItems);
// **** push some random values ****
for (int i = 0; i < maxItems; i++) {
val = StdRandom.uniform(1, maxVal);
StdOut.println(“main <<< val: ” + val);
try {
stack.push(val);
} catch (IndexOutOfBoundsException e) {
StdOut.println(“main <<< stack.push() IndexOutOfBoundsException val: “ + val);
}
}
// **** pop all items from the stack ****
System.out.print(“main <<< stack: “);
while (!stack.isEmpty()) {
val = stack.pop();
StdOut.print(val + ” “);
}
StdOut.println();
}
}
Following is a screen capture of the output from the test method (Main):
main <<< val: 37
main <<< val: 50
main <<< val: 59
main <<< val: 44
main <<< val: 30
main <<< val: 28
main <<< val: 91
main <<< stack: 91 28 30 44 59 50 37
The program allocates a stack with a maxim capacity as indicated by the 
value in the maxItems constant. As illustrated by the previous output the random values are properly “pushed” into the stack. Life is good; at least it seems so. If you attempt to push additional items; the stack throws an exception. We could add a check for this condition (as is already implemented in the code) to determine if there is space left in the stack or add a method (e.g., isFull()) that the client would call before calling push() to determine if there is space left in the stack. How about using a different type of object besides integers? No problem; just duplicate the code and replace the int references by let’s say String. Not a good approach. One may end up with dozens of implementations of the same stack code using different object types :o( There is also the issue of memory allocation. If there are very few places in a system using this implementation and all allocate a dozen or so elements; all is well. In reality that seldom happens. This implementation of stack is far from being optimal.
If you change the following line in Main() from:
for (int i = 0; i < maxItems; i++) {
to
for (int i = 0; i < maxItems + 1; i++) {
the output from the program would display something like:
main <<< val: 66
main <<< val: 68
main <<< val: 92
main <<< val: 16
main <<< val: 25
main <<< val: 80
main <<< val: 24
main <<< val: 93
main <<< stack.push() IndexOutOfBoundsException val: 93
main <<< stack: 24 80 25 16 92 68 66
Not too elegant and the code is starting to get somewhat complex.
In the next entry in this blog we would see a much better algorithm to implement a stack.
If you have comments or questions, please send me a note via email.
John
john.canessa@gmail.com