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}