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 Stack<T> implements Iterable<T> { 032 private int N; // size of the stack 033 private Node<T> first; // top of stack 034 035 // helper linked list class 036 private static class Node<T> { 037 public Node () { } 038 public T item; 039 public Node<T> next; 040 } 041 042 /** 043 * Create an empty stack. 044 */ 045 public Stack() { 046 this.first = null; 047 this.N = 0; 048 } 049 050 /** 051 * Is the stack empty? 052 */ 053 public boolean isEmpty() { 054 return first == null; 055 } 056 057 /** 058 * Return the number of items in the stack. 059 */ 060 public int size() { 061 return N; 062 } 063 064 /** 065 * Add the item to the stack. 066 */ 067 public void push(T item) { 068 Node<T> oldfirst = first; 069 first = new Node<>(); 070 first.item = item; 071 first.next = oldfirst; 072 N++; 073 } 074 075 /** 076 * Delete and return the item most recently added to the stack. 077 * @throws java.util.NoSuchElementException if stack is empty. 078 */ 079 public T pop() { 080 if (isEmpty()) throw new NoSuchElementException("Stack underflow"); 081 T item = first.item; // save item to return 082 first = first.next; // delete first node 083 N--; 084 return item; // return the saved item 085 } 086 087 088 /** 089 * Return the item most recently added to the stack. 090 * @throws java.util.NoSuchElementException if stack is empty. 091 */ 092 public T peek() { 093 if (isEmpty()) throw new NoSuchElementException("Stack underflow"); 094 return first.item; 095 } 096 097 /** 098 * Return string representation. 099 */ 100 public String toString() { 101 StringBuilder s = new StringBuilder(); 102 for (T item : this) 103 s.append(item + " "); 104 return s.toString(); 105 } 106 107 108 // check internal invariants 109 private static <T> boolean check(Stack<T> that) { 110 int N = that.N; 111 Stack.Node<T> first = that.first; 112 if (N == 0) { 113 if (first != null) return false; 114 } 115 else if (N == 1) { 116 if (first == null) return false; 117 if (first.next != null) return false; 118 } 119 else { 120 if (first.next == null) return false; 121 } 122 123 // check internal consistency of instance variable N 124 int numberOfNodes = 0; 125 for (Stack.Node<T> x = first; x != null; x = x.next) { 126 numberOfNodes++; 127 } 128 if (numberOfNodes != N) return false; 129 130 return true; 131 } 132 133 134 /** 135 * Return an iterator to the stack that iterates through the items in LIFO order. 136 */ 137 public Iterator<T> iterator() { return new ListIterator(); } 138 139 // an iterator, doesn't implement remove() since it's optional 140 private class ListIterator implements Iterator<T> { 141 private Node<T> current = first; 142 public void remove() { throw new UnsupportedOperationException(); } 143 public boolean hasNext() { return current != null; } 144 //public ListIterator () { TraceGraph.draw (); } 145 public T next() { 146 if (!hasNext()) throw new NoSuchElementException(); 147 T item = current.item; 148 current = current.next; 149 return item; 150 } 151 } 152 153 /** 154 * A test client. 155 */ 156 public static void main(String[] args) { 157 StdIn.fromString ("to be or not to - be - - that - - - is"); 158 //StdIn.fromString ("0 - 1 2 3 4 5 6 7 8 9 - -"); 159 Stack<String> stack = new Stack<>(); 160 while (!StdIn.isEmpty()) { 161 String item = StdIn.readString(); 162 if (!item.equals("-")) stack.push(item); 163 else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); 164 } 165 StdOut.println(); 166 StdOut.println(stack.size() + " left on stack:"); 167 for (String s : stack) { 168 StdOut.print (s + " "); 169 } 170 StdOut.println (); 171 } 172 public static void main1(String[] args) { 173 //Trace.showBuiltInObjectsVerbose (true); 174 Trace.drawStepsOfMethod ("main"); 175 Trace.run (); 176 Integer r1 = null; 177 Stack<Integer> s1 = new Stack<>(); 178 s1.push (11); 179 s1.push (21); 180 s1.push (31); 181 s1.push (41); 182 s1.push (51); 183 r1 = s1.pop (); 184 r1 = s1.pop (); 185 r1 = s1.pop (); 186 r1 = null; 187 s1.push (61); 188 s1.push (71); 189 190 String r2 = null; 191 Stack<String> s2 = new Stack<>(); 192 s2.push ("a"); 193 s2.push ("b"); 194 s2.push ("c"); 195 s2.push ("d"); 196 s2.push ("e"); 197 r2 = s2.pop (); 198 r2 = s2.pop (); 199 r2 = s2.pop (); 200 r2 = null; 201 s2.push ("f"); 202 s2.push ("g"); 203 s2.push ("h"); 204 } 205 public static void main2(String[] args) { 206 Trace.drawStepsOfMethod ("main"); 207 Trace.run (); 208 Stack<Integer> s1 = new Stack<>(); 209 s1.push (300); 210 Stack<String> s2 = new Stack<>(); 211 s2.push ("duck"); 212 s2.push ("goose"); 213 } 214}