001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac ResizingSlowStack.java 007 * Execution: java ResizingSlowStack < input.txt 008 * Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt 009 * 010 * Stack implementation with a resizing array. 011 * 012 * % more tobe.txt 013 * to be or not to - be - - that - - - is 014 * 015 * % java ResizingSlowStack < tobe.txt 016 * to be not that or be (2 left on stack) 017 * 018 *************************************************************************/ 019 020public class XResizingArraySlowStack<T> implements Iterable<T> { 021 private T[] a; // array of items 022 private int N = 0; // number of elements on stack 023 024 // create an empty stack 025 @SuppressWarnings("unchecked") 026 public XResizingArraySlowStack() { 027 a = (T[]) new Object[N]; 028 } 029 030 public boolean isEmpty() { return N == 0; } 031 public int size() { return N; } 032 033 // resize the underlying array holding the elements 034 private void resize(int capacity) { 035 @SuppressWarnings("unchecked") 036 T[] temp = (T[]) new Object[capacity]; 037 for (int i = 0; i < N; i++) 038 temp[i] = a[i]; 039 a = temp; 040 } 041 042 // push a new item onto the stack 043 public void push(T item) { 044 if (N == a.length) resize(N+1); 045 a[N] = item; 046 N++; 047 } 048 049 // delete and return the item most recently added 050 public T pop() { 051 if (isEmpty()) { throw new Error("Stack underflow error"); } 052 N--; 053 T item = a[N]; 054 a[N] = null; // to avoid loitering 055 resize(N); // shrink size of array if necessary 056 return item; 057 } 058 059 060 public Iterator<T> iterator() { return new LIFOIterator(); } 061 062 // an iterator, doesn't implement remove() since it's optional 063 private class LIFOIterator implements Iterator<T> { 064 private int i = N; 065 public boolean hasNext() { return i > 0; } 066 public void remove() { throw new UnsupportedOperationException(); } 067 068 public T next() { 069 if (!hasNext()) throw new NoSuchElementException(); 070 return a[--i]; 071 } 072 } 073 074 075 076 /* ********************************************************************* 077 * Test routine. 078 **********************************************************************/ 079 public static void main(String[] args) { 080 Trace.drawStepsOfMethod ("resize"); 081 Trace.run (); 082 StdIn.fromString ("to be or not to - be - - that - - - is"); 083 084 XResizingArraySlowStack<String> s = new XResizingArraySlowStack<>(); 085 while (!StdIn.isEmpty()) { 086 String item = StdIn.readString(); 087 if (!item.equals("-")) s.push(item); 088 else if (!s.isEmpty()) StdOut.print(s.pop() + " "); 089 } 090 StdOut.println("(" + s.size() + " left on stack)"); 091 } 092}