ResizingArrayStack ADT

/*************************************************************************
 *  Compilation:  javac ResizingArrayStack.java
 *  Execution:    java ResizingArrayStack < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *  
 *  Stack implementation with a resizing array.
 *
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java ResizingArrayStack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The ResizingArrayStack class represents a last-in-first-out (LIFO) stack
 *  of generic items.
 *  It supports the usual push and pop operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  

* This implementation uses a resizing array, which double the underlying array * when it is full and halves the underlying array when it is one-quarter full. * The push and pop operations take constant amortized time. * The size, peek, and is-empty operations takes * constant time in the worst case. * * For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class ResizingArrayStack implements Iterable { private Item[] a; // array of items private int N; // number of elements on stack /** * Initializes an empty stack. */ public ResizingArrayStack() { a = (Item[]) new Object[2]; } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { return N == 0; } /** * Returns the number of items in the stack. * @return the number of items in the stack */ public int size() { return N; } // resize the underlying array holding the elements private void resize(int capacity) { assert capacity >= N; Item[] temp = (Item[]) new Object[capacity]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { if (N == a.length) resize(2*a.length); // double size of array if necessary a[N++] = item; // add item } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = a[N-1]; a[N-1] = null; // to avoid loitering N--; // shrink size of array if necessary if (N > 0 && N == a.length/4) resize(a.length/2); return item; } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return a[N-1]; } /** * Returns an iterator to this stack that iterates through the items in LIFO order. * @return an iterator to this stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ReverseArrayIterator(); } // an iterator, doesn't implement remove() since it's optional private class ReverseArrayIterator implements Iterator { private int i; public ReverseArrayIterator() { i = N; } public boolean hasNext() { return i > 0; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return a[--i]; } } /** * Unit tests the Stack data type. */ public static void main(String[] args) { ResizingArrayStack s = new ResizingArrayStack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } } Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. Last updated: Mon Oct 7 11:58:25 EDT 2013.