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 {@code 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 main(String[] args) {
StdIn.fromString ("to be or not to - be - - that - - - is");
//StdIn.fromString ("0 - 1 2 3 4 5 6 7 8 9 - -");
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();
StdOut.println(stack.size() + " left on stack:");
for (String s : stack) {
StdOut.print (s + " ");
}
StdOut.println ();
}
public static void main1(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.drawStepsOfMethod ("main");
Trace.run ();
Stack s1 = new Stack<>();
s1.push (300);
Stack s2 = new Stack<>();
s2.push ("duck");
s2.push ("goose");
}
}