This blog entry is based on the example on page 141 of Algorithms fourth edition by Robert Sedgewick and Kevin Wayne. I am reading the book as a refresher and learning experience on computer algorithms. Initially what called my attention was the statement that it contains 50 algorithms that every programmer should know. I want to make sure I have a good handle on those algorithms. After reading the first few chapters which have not cover the algorithms yet, I feel that the way the ground work is presented is very educational, direct to the point and simple to follow. I always like simplicity in code and documentation. Elegant code is very hard to find and write. This book seems that it should help readers achieve such goal.
The following code (with some modifications) is what I used to experiment and follow the material on pages 132 – 141. If you take a look at the previous entry, it contains an implementation on a stack. It does work but has many limitations. The following code snippet seems to address them:
package edu.princeton.cs.algs4;
import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item> {
private Item[] a = (Item[]) new Object[1];
private int N = 0;
// **** methods ****
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void resize(int max) {
StdOut.println(“resize <<< N: ” + N + ” max: ” + max);
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
this.a = temp;
}
public void push(Item item) {
// **** resize (grow) the stack (if needed) ****
if (N == a.length) {
resize(2 * a.length);
}
// **** push the item on the stack ****
a[N++] = item;
}
public Item pop() {
Item item = a[–N];
// **** avoid loitering ****
a[N] = null;
// **** reduce the size of the stack (if needed) ****
if ((N > 0) && (N == a.length / 4)) {
resize(a.length / 2);
}
// **** return the item ****
return item;
}
// **** ****
@Override
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item> {
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[–i];
}
public void remove() {}
}
// **** ****
public static void main(String[] args) {
final int maxVal = 100;
final int maxItems = 7;
ResizingArrayStack<Integer> stack = new ResizingArrayStack<Integer>();
// **** push some random values ****
for (int i = 0; i < maxItems; i++) {
int val = StdRandom.uniform(1, maxVal);
StdOut.println(“main <<< val: ” + val);
stack.push(val);
}
// **** pop all items from the stack ****
System.out.print(“<<< stack: “);
for (int val : stack) {
val = stack.pop();
StdOut.print(val + ” “);
}
StdOut.println();
}
}
The console output (I am using the Eclipse IDE) of the above code follows:
main <<< val: 90
main <<< val: 20
resize <<< N: 1 max: 2
main <<< val: 81
resize <<< N: 2 max: 4
main <<< val: 78
main <<< val: 48
resize <<< N: 4 max: 8
main <<< val: 77
main <<< val: 97
main <<< stack: 97 77 48 78 resize <<< N: 2 max: 4
81 resize <<< N: 1 max: 2
20 90
The test code in Main() generates a set of random integers within a range and pushes them into the stack. As one can see in the output, every so often, the resize() method is called. It elegantly extends the size of the array and copies the previous entries to the new array. This is a simple and elegant implementation. The client does not need to allocate a stack with an expected capacity that would probably waste a considerably amount of memory.
The code then starts popping values from the stack. As you can see the 
values are taken in the expected order. A side benefit is that periodically the size of the stack is reduced allowing memory to be released and reused. Reuse is taken care of by the Java garbage collection mechanism.
The authors of the book take you from a simple stack illustrated in the previous blog entry that only supports a single type of items to this new and improved version that supports different type of objects and handles memory allocation and release.
If you have comments or questions, please drop me a line via email.
John
john.canessa@gmail.com