001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac Stack.java 007 * Execution: java Stack < input.txt 008 * 009 * A generic stack, implemented using a linked list. Each stack 010 * element is of type Item. 011 * 012 * % more tobe.txt 013 * to be or not to - be - - that - - - is 014 * 015 * % java Stack < tobe.txt 016 * to be not that or be (2 left on stack) 017 * 018 *************************************************************************/ 019 020/** 021 * The {@code Stack} class represents a last-in-first-out (LIFO) stack of generic items. 022 * It supports the usual <em>push</em> and <em>pop</em> operations, along with methods 023 * for peeking at the top item, testing if the stack is empty, and iterating through 024 * the items in LIFO order. 025 * <p> 026 * All stack operations except iteration are constant time. 027 * <p> 028 * For additional documentation, see <a href="/algs4/13stacks">Section 1.3</a> of 029 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 030 */ 031public class StackWithNonStaticNode<T> implements Iterable<T> { 032 private int N; // size of the stack 033 private Node first; // top of stack 034 035 // helper linked list class 036 private class Node { 037 T item; 038 Node next; 039 } 040 041 /** 042 * Create an empty stack. 043 */ 044 public StackWithNonStaticNode() { 045 this.first = null; 046 this.N = 0; 047 } 048 049 /** 050 * Is the stack empty? 051 */ 052 public boolean isEmpty() { 053 return first == null; 054 } 055 056 /** 057 * Return the number of items in the stack. 058 */ 059 public int size() { 060 return N; 061 } 062 063 /** 064 * Add the item to the stack. 065 */ 066 public void push(T item) { 067 Node oldfirst = first; 068 first = new Node(); 069 first.item = item; 070 first.next = oldfirst; 071 N++; 072 } 073 074 /** 075 * Delete and return the item most recently added to the stack. 076 * @throws java.util.NoSuchElementException if stack is empty. 077 */ 078 public T pop() { 079 if (isEmpty()) throw new NoSuchElementException("Stack underflow"); 080 T item = first.item; // save item to return 081 first = first.next; // delete first node 082 N--; 083 return item; // return the saved item 084 } 085 086 087 /** 088 * Return the item most recently added to the stack. 089 * @throws java.util.NoSuchElementException if stack is empty. 090 */ 091 public T peek() { 092 if (isEmpty()) throw new NoSuchElementException("Stack underflow"); 093 return first.item; 094 } 095 096 /** 097 * Return string representation. 098 */ 099 public String toString() { 100 StringBuilder s = new StringBuilder(); 101 for (T item : this) 102 s.append(item + " "); 103 return s.toString(); 104 } 105 106 107 // check internal invariants 108 private static <T> boolean check(StackWithNonStaticNode<T> that) { 109 int N = that.N; 110 StackWithNonStaticNode<T>.Node first = that.first; 111 if (N == 0) { 112 if (first != null) return false; 113 } 114 else if (N == 1) { 115 if (first == null) return false; 116 if (first.next != null) return false; 117 } 118 else { 119 if (first.next == null) return false; 120 } 121 122 // check internal consistency of instance variable N 123 int numberOfNodes = 0; 124 for (StackWithNonStaticNode<T>.Node x = first; x != null; x = x.next) { 125 numberOfNodes++; 126 } 127 if (numberOfNodes != N) return false; 128 129 return true; 130 } 131 132 133 /** 134 * Return an iterator to the stack that iterates through the items in LIFO order. 135 */ 136 public Iterator<T> iterator() { return new ListIterator(); } 137 138 // an iterator, doesn't implement remove() since it's optional 139 private class ListIterator implements Iterator<T> { 140 private Node current = first; 141 public boolean hasNext() { return current != null; } 142 public void remove() { throw new UnsupportedOperationException(); } 143 144 public T next() { 145 if (!hasNext()) throw new NoSuchElementException(); 146 T item = current.item; 147 current = current.next; 148 return item; 149 } 150 } 151 152 153 /** 154 * A test client. 155 */ 156 public static void bookMain(String[] args) { 157 StdIn.fromString ("to be or not to - be - - that - - - is"); 158 StackWithNonStaticNode<String> stack = new StackWithNonStaticNode<>(); 159 while (!StdIn.isEmpty()) { 160 String item = StdIn.readString(); 161 if (!item.equals("-")) stack.push(item); 162 else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); 163 } 164 StdOut.println(stack.size() + " left on stack:"); 165 for (String s : stack) { 166 StdOut.print (s + " "); 167 } 168 StdOut.println (); 169 } 170 public static void main(String[] args) { 171 //Trace.showBuiltInObjectsVerbose (true); 172 Trace.drawStepsOfMethod ("main"); 173 Trace.run (); 174 Integer r1 = null; 175 StackWithNonStaticNode<Integer> s1 = new StackWithNonStaticNode<>(); 176 s1.push (11); 177 s1.push (21); 178 s1.push (31); 179 s1.push (41); 180 s1.push (51); 181 r1 = s1.pop (); 182 r1 = s1.pop (); 183 r1 = s1.pop (); 184 r1 = null; 185 s1.push (61); 186 s1.push (71); 187 188 String r2 = null; 189 StackWithNonStaticNode<String> s2 = new StackWithNonStaticNode<>(); 190 s2.push ("a"); 191 s2.push ("b"); 192 s2.push ("c"); 193 s2.push ("d"); 194 s2.push ("e"); 195 r2 = s2.pop (); 196 r2 = s2.pop (); 197 r2 = s2.pop (); 198 r2 = null; 199 s2.push ("f"); 200 s2.push ("g"); 201 s2.push ("h"); 202 } 203 public static void main2(String[] args) { 204 Trace.showObjectIdsRedundantly (true); 205 //Trace.showBuiltInObjectsVerbose (true); 206 Trace.drawStepsOfMethod ("main"); 207 Trace.run (); 208 StackWithNonStaticNode<Integer> s1 = new StackWithNonStaticNode<>(); 209 s1.push (300); 210 StackWithNonStaticNode<String> s2 = new StackWithNonStaticNode<>(); 211 s2.push ("duck"); 212 s2.push ("goose"); 213 } 214}