# CSC300: Lecture 7 (More Analysis, Resizing Arrays (1.4, 1.3))

 Contents [0/15]

 Induction: Is this function useful? [1/15] Induction: Is this function useful? [2/15] Induction: Is this function useful? [3/15] Induction: Is this function useful? [4/15] Induction: Is this function useful? [5/15] Induction: Linear search [6/15] Induction: Binary search [7/15] Homework [8/15] XFixedCapacityStackOfStrings [9/15] XFixedCapacityStack [10/15] XFixedCapacityIterableStack [11/15] XResizingSlowStack [12/15] ResizingArrayStack [13/15] Stack [14/15] StackWithNonStaticNode [15/15]

 Induction: Is this function useful? [1/15]

 ``` 01 02 03 04 05 06 ``` ```public static int f (int x, int y) { while (false) { x++; } return x; }```

Degenerate loop 1

 Induction: Is this function useful? [2/15]

 ``` 01 02 03 04 05 06 ``` ```public static int f (int x, int y) { while (true) { x++; } return x; }```

Degenerate loop 2

 Induction: Is this function useful? [3/15]

 ``` 01 02 03 04 05 06 07 ``` ```public static int f (int x, int y) { while (y > 0) { x++; y--; } return x; }```

A useful loop.

Why is it useful? What does it do? How do you know?

I will walk through the first part of these notes (also available here)

 Induction: Is this function useful? [4/15]

 ``` 01 02 03 04 05 06 07 08 09 ``` ```public static boolean someTrue (boolean[] a) { boolean result = false; int i = 0; while (i < a.length) { if (a[i]) result = true; i++; } return result; }```

 Induction: Is this function useful? [5/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 ``` ```public static int f (boolean[] a) { int result = 0; while (someTrue (a)) { int i = StdRandom.uniform (a.length); if (a[i]) { a[i] = false; result++; } } return result; }```

Is it guaranteed to terminate?

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ``` ```package algs11; import stdlib.*; public class Hello { public static boolean someTrue (boolean[] a) { boolean result = false; int i = 0; while (i < a.length) { if (a[i]) { result = true; break; } i++; } return result; } public static int f (boolean[] a) { int result = 0; while (someTrue (a)) { int i = StdRandom.uniform (a.length); Trace.draw (); if (a[i]) { a[i] = false; result++; } } return result; } public static void main (String[] args) { Trace.run (); f (new boolean[] {true, false, true, true, false}); StdOut.println ("Hello"); } }```

 Induction: Linear search [6/15]

 ``` 01 02 03 04 05 06 07 08 ``` ``` public static boolean contains (double val, double[] list) { int i = 0; while (i < list.length) { if (val == list[i]) { return true; } i++; } return false; }```

Another version

 ``` 01 02 03 04 05 06 07 08 09 ``` ``` public static boolean contains (double val, double[] list) { int i = 0; boolean result = false; while (i < list.length) { if (val == list[i]) { result = false; break; } i++; } return result; }```

How long does it take (in the worst case)?

• Constant amount of time (1)
• Time proportional to the logorithm of the length of the list (log2 N)
• Time proportional to the length of the list (N)
• Time proportional to the length of the list squared (N2)
• Time proportional to the exponential of the length of the list squared (2N)

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ``` ```package algs11; import java.util.Arrays; import stdlib.*; public class Playground { /* Return true if val is in the list */ public static boolean contains (double val, double[] list) { return StdRandom.bernoulli (); //TODO: fix this } /* This is a test function */ public static void testContains (boolean expected, double val, double[] list) { boolean actual = contains (val, list); if (expected != actual) { StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list)); } } /* A main function for testing */ public static void main (String[] args) { for (double v : new double[] { 5, 7 }) { testContains (true, v, new double[] { 11, 21, 31, v, 41 }); testContains (true, v, new double[] { v, 11, 21, 31, 41 }); testContains (true, v, new double[] { 11, 21, 31, 41, v }); testContains (true, v, new double[] { 11, v, 21, v, 31, 41 }); testContains (true, v, new double[] { v }); testContains (true, v, new double[] { v, v }); testContains (false, v, new double[] { 11, 21, 31, 41 }); testContains (false, v, new double[] { 11 }); testContains (false, v, new double[] {}); } StdOut.println ("Finished tests"); } }```

 Induction: Binary search [7/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 ``` ``` public static boolean contains(double val, double[] list) { int lo = 0; int hi = list.length-1; while (hi >= lo) { int mid = lo + (hi-lo)/2; if (val > list[mid]) lo = mid + 1; if (val < list[mid]) hi = mid - 1; if (val == list[mid]) return true; } return false; }```

A more complicated pattern. Does it terminate? Under what assumptions?

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ``` ```package algs11; import java.util.Arrays; import stdlib.*; public class Playground { /* Return true if val is in the list */ public static boolean contains (double val, double[] list) { return StdRandom.bernoulli (); //TODO: fix this } /* This is a test function */ public static void testContains (boolean expected, double val, double[] list) { boolean actual = contains (val, list); if (expected != actual) { StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list)); } } /* A main function for testing */ public static void main (String[] args) { testContains (true, 11, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 21, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 31, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 41, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 51, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 61, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (true, 71, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 }); testContains (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 }); StdOut.println ("Finished tests"); } }```

 Homework [8/15]

• Read Algorithms 1.4 again. Also read 2.1. Also read the discussion of stability in section 2.5 (page 341 in the third printing of the text).

• Do these problems on paper, but don't hand them in.
• 1.5.1
• 1.5.2
• 1.5.3
• Complete Percolation.java

 XFixedCapacityStackOfStrings [9/15]

 file:XFixedCapacityStackOfStrings.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 ``` ```package algs13; import stdlib.*; public class XFixedCapacityStackOfStrings { private final String[] a; // holds the items private int N; // number of items in stack // a[0]..a[N-1] are non null // a[N]..a[a.length-1] are null public XFixedCapacityStackOfStrings (int capacity) { this.a = new String[capacity]; this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (String item) { if (item == null) throw new IllegalArgumentException (); a[N] = item; N++; } public String pop () { N--; String result = a[N]; a[N] = null; return result; } public static void main(String[] args) { Trace.showObjectIdsRedundantly (true); //Trace.showBuiltInObjects (true); Trace.drawStepsOfMethod ("main"); Trace.run (); XFixedCapacityStackOfStrings stack = new XFixedCapacityStackOfStrings (7); stack.push ("a"); stack.push ("b"); stack.push ("c"); stack.push ("d"); while (!stack.isEmpty()) { StdOut.println (stack.pop ()); } } } ```

 XFixedCapacityStack [10/15]

 file:XFixedCapacityStack.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ``` ```package algs13; import stdlib.*; public class XFixedCapacityStack { private final T[] a; // holds the items private int N; // number of items in stack @SuppressWarnings("unchecked") public XFixedCapacityStack (int capacity) { this.a = (T[]) new Object[10]; // no generic array creation this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (T item) { a[N] = item; N++; } public T pop () { N--; T result = a[N]; a[N] = null; return result; } public static void main (String[] args) { Trace.showObjectIdsRedundantly (true); Trace.showBuiltInObjects (true); //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); XFixedCapacityStack s1 = new XFixedCapacityStack<> (5); XFixedCapacityStack s2 = new XFixedCapacityStack<> (3); s1.push (11); s1.push (21); s1.push (31); //s2.push (41); s2.push ("duck"); s2.push ("goose"); } } ```

 XFixedCapacityIterableStack [11/15]

 file:XFixedCapacityIterableStack.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ``` ```package algs13; import stdlib.*; import java.util.Iterator; public class XFixedCapacityIterableStack implements Iterable { private final T[] a; // holds the items private int N; // number of items in stack @SuppressWarnings("unchecked") public XFixedCapacityIterableStack (int capacity) { this.a = (T[]) new Object[10]; // no generic array creation this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (T item) { a[N] = item; N++; } public T pop () { N--; T result = a[N]; a[N] = null; return result; } public Iterator iterator () { return new ReverseArrayIterator (); } public class ReverseArrayIterator implements Iterator { private int i = N - 1; public void remove () { throw new UnsupportedOperationException (); } public boolean hasNext () { return i >= 0; } public T next () { T result = a[i]; i--; return result; } } public static void main (String[] args) { Trace.showBuiltInObjects (true); Trace.drawStepsOfMethod ("main"); Trace.drawStepsOfMethod ("next"); Trace.run (); XFixedCapacityIterableStack s1 = new XFixedCapacityIterableStack<> (5); XFixedCapacityIterableStack s2 = new XFixedCapacityIterableStack<> (3); s1.push (11); s1.push (21); s1.push (31); s2.push ("duck"); s2.push ("goose"); StdOut.print ("What's on the stack: "); for (Integer k : s1) { StdOut.print (k + " "); } StdOut.println (); // Here is a more explicit version StdOut.print ("What's on the stack: "); { Iterator it = s1.iterator (); while (it.hasNext ()) { Integer k = it.next (); StdOut.print (k + " "); } } StdOut.println (); } } ```

 XResizingSlowStack [12/15]

 file:XResizingSlowStack.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 ``` ```package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac ResizingSlowStack.java * Execution: java ResizingSlowStack < 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 ResizingSlowStack < tobe.txt * to be not that or be (2 left on stack) * *************************************************************************/ public class XResizingSlowStack implements Iterable { private T[] a; // array of items private int N = 0; // number of elements on stack // create an empty stack @SuppressWarnings("unchecked") public XResizingSlowStack() { a = (T[]) new Object[N]; } public boolean isEmpty() { return N == 0; } public int size() { return N; } // resize the underlying array holding the elements private void resize(int capacity) { @SuppressWarnings("unchecked") T[] temp = (T[]) new Object[capacity]; for (int i = 0; i < N; i++) temp[i] = a[i]; a = temp; } // push a new item onto the stack public void push(T item) { if (N == a.length) resize(N + 1); a[N] = item; N++; } // delete and return the item most recently added public T pop() { if (isEmpty()) { throw new Error("Stack underflow error"); } N--; T item = a[N]; a[N] = null; // to avoid loitering resize(N); // shrink size of array if necessary return item; } public Iterator iterator() { return new LIFOIterator(); } // an iterator, doesn't implement remove() since it's optional private class LIFOIterator implements Iterator { private int i = N; public boolean hasNext() { return i > 0; } public void remove() { throw new UnsupportedOperationException(); } public T next() { if (!hasNext()) throw new NoSuchElementException(); return a[--i]; } } /* ********************************************************************* * Test routine. **********************************************************************/ public static void main(String[] args) { Trace.drawStepsOfMethod ("resize"); Trace.run (); StdIn.fromString ("to be or not to - be - - that - - - is"); XResizingSlowStack s = new XResizingSlowStack<>(); 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)"); } } ```

 ResizingArrayStack [13/15]

 file:ResizingArrayStack.java [source] [doc-public] [doc-private]
 ``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 ``` ```package algs13; //import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * 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) * *************************************************************************/ public class ResizingArrayStack implements Iterable { private T[] a; // array of items private int N; // number of elements on stack // create an empty stack @SuppressWarnings("unchecked") public ResizingArrayStack() { this.a = (T[]) new Object[2]; this.N = 0; } public boolean isEmpty() { return N == 0; } public int size() { return N; } // resize the underlying array holding the elements @SuppressWarnings("unchecked") private void resize(int capacity) { if (capacity <= N) throw new IllegalArgumentException (); T[] temp = (T[]) new Object[capacity]; for (int i = 0; i < N; i++) temp[i] = a[i]; a = temp; } // push a new item onto the stack public void push(T item) { if (N == a.length) resize(2*N); // increase array size if necessary //if (N == a.length) resize(N + Math.max (1, N/1)); a[N] = item; N++; } // delete and return the item most recently added public T pop() { if (isEmpty()) { throw new Error("Stack underflow error"); } N--; T item = a[N]; a[N] = null; // to avoid loitering if (N > 0 && N == a.length/4) resize(a.length/2); // shrink size of array if necessary return item; } public Iterator iterator() { return new ReverseArrayIterator(); } // an iterator, doesn't implement remove() since it's optional private class ReverseArrayIterator implements Iterator { private int i = N; public boolean hasNext() { return i > 0; } public void remove() { throw new UnsupportedOperationException(); } public T next() { if (!hasNext()) throw new NoSuchElementException(); return a[--i]; } } /* ********************************************************************* * Test routine. **********************************************************************/ // public static void bookMain(String[] args) { // StdIn.fromString ("to be or not to - be - - that - - - is"); // // 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)"); // } // // /* ********************************************************************* // * Test routine. // **********************************************************************/ // public static void main(String[] args) { // double prevTime = 1; // for (int i = 0, size = 16; i<20; i += 1, size *= 2) { // Stopwatch s = new Stopwatch (); // // for (int k = 0; k < 100; k++) { // ResizingArrayStack stack = new ResizingArrayStack<> (); // for (int j = 0; j < size; j++) { // stack.push (1.2); // } // } // // double thisTime = s.elapsedTime (); // StdOut.format ("size=%d thisTime=%f ratio=%f\n", size, thisTime, thisTime/prevTime); // prevTime = thisTime; // } // } } ```

 Stack [14/15]

 file:Stack.java [source] [doc-public] [doc-private]
 ``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 ``` ```package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac Stack.java * Execution: java Stack < input.txt * * A generic stack, implemented using a linked list. Each stack * element is of type Item. * * % more tobe.txt * to be or not to - be - - that - - - is * * % java Stack < tobe.txt * to be not that or be (2 left on stack) * *************************************************************************/ /** * The Stack 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. *

* All stack operations except iteration are constant time. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class Stack implements Iterable { private int N; // size of the stack private Node first; // top of stack // helper linked list class private static class Node { public Node () { } public T item; public Node next; } /** * Create an empty stack. */ public Stack() { this.first = null; this.N = 0; } /** * Is the stack empty? */ public boolean isEmpty() { return first == null; } /** * Return the number of items in the stack. */ public int size() { return N; } /** * Add the item to the stack. */ public void push(T item) { Node oldfirst = first; first = new Node<>(); first.item = item; first.next = oldfirst; N++; } /** * Delete and return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); T item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Return string representation. */ public String toString() { StringBuilder s = new StringBuilder(); for (T item : this) s.append(item + " "); return s.toString(); } // check internal invariants private static boolean check(Stack that) { int N = that.N; Stack.Node first = that.first; if (N == 0) { if (first != null) return false; } else if (N == 1) { if (first == null) return false; if (first.next != null) return false; } else { if (first.next == null) return false; } // check internal consistency of instance variable N int numberOfNodes = 0; for (Stack.Node x = first; x != null; x = x.next) { numberOfNodes++; } if (numberOfNodes != N) return false; return true; } /** * Return an iterator to the stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current = first; public void remove() { throw new UnsupportedOperationException(); } public boolean hasNext() { return current != null; } //public ListIterator () { TraceGraph.draw (); } public T next() { if (!hasNext()) throw new NoSuchElementException(); T item = current.item; current = current.next; return item; } } /** * A test client. */ public static void bookMain(String[] args) { StdIn.fromString ("to be or not to - be - - that - - - is"); Stack stack = new Stack<>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) stack.push(item); else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); } StdOut.println(stack.size() + " left on stack:"); for (String s : stack) { StdOut.print (s + " "); } StdOut.println (); } public static void main(String[] args) { //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); Integer r1 = null; Stack s1 = new Stack<>(); s1.push (11); s1.push (21); s1.push (31); s1.push (41); s1.push (51); r1 = s1.pop (); r1 = s1.pop (); r1 = s1.pop (); r1 = null; s1.push (61); s1.push (71); String r2 = null; Stack s2 = new Stack<>(); s2.push ("a"); s2.push ("b"); s2.push ("c"); s2.push ("d"); s2.push ("e"); r2 = s2.pop (); r2 = s2.pop (); r2 = s2.pop (); r2 = null; s2.push ("f"); s2.push ("g"); s2.push ("h"); } public static void main2(String[] args) { Trace.showObjectIdsRedundantly (true); //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); Stack s1 = new Stack<>(); s1.push (300); Stack s2 = new Stack<>(); s2.push ("duck"); s2.push ("goose"); } } ```

 StackWithNonStaticNode [15/15]

 file:StackWithNonStaticNode.java [source] [doc-public] [doc-private]
 ``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 ``` ```package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac Stack.java * Execution: java Stack < input.txt * * A generic stack, implemented using a linked list. Each stack * element is of type Item. * * % more tobe.txt * to be or not to - be - - that - - - is * * % java Stack < tobe.txt * to be not that or be (2 left on stack) * *************************************************************************/ /** * The Stack 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. *

* All stack operations except iteration are constant time. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class StackWithNonStaticNode implements Iterable { private int N; // size of the stack private Node first; // top of stack // helper linked list class private class Node { T item; Node next; } /** * Create an empty stack. */ public StackWithNonStaticNode() { this.first = null; this.N = 0; } /** * Is the stack empty? */ public boolean isEmpty() { return first == null; } /** * Return the number of items in the stack. */ public int size() { return N; } /** * Add the item to the stack. */ public void push(T item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } /** * Delete and return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); T item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Return string representation. */ public String toString() { StringBuilder s = new StringBuilder(); for (T item : this) s.append(item + " "); return s.toString(); } // check internal invariants private static boolean check(StackWithNonStaticNode that) { int N = that.N; StackWithNonStaticNode.Node first = that.first; if (N == 0) { if (first != null) return false; } else if (N == 1) { if (first == null) return false; if (first.next != null) return false; } else { if (first.next == null) return false; } // check internal consistency of instance variable N int numberOfNodes = 0; for (StackWithNonStaticNode.Node x = first; x != null; x = x.next) { numberOfNodes++; } if (numberOfNodes != N) return false; return true; } /** * Return an iterator to the stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current = first; public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public T next() { if (!hasNext()) throw new NoSuchElementException(); T item = current.item; current = current.next; return item; } } /** * A test client. */ public static void main(String[] args) { StdIn.fromString ("to be or not to - be - - that - - - is"); StackWithNonStaticNode s = new StackWithNonStaticNode<>(); 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)"); } } ```

Revised: 2008/03/17 13:01