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}