// D. Scott
// CCI - Problem 3.3
// Immplement a set of stacks with same operations as stack
// (stacks autosplit after reaching certain size)

class SetOfStacks {
    int maxSize;  // limit for stack size (create new stack when >)
    Stack curr;   // currently active stack
    
    public SetOfStacks(int s) {
        maxSize = s;
        Stack n = new Stack();
        curr = n;
    }
    
    void push(int d) {
        if (curr.numNodes < maxSize) {  // if room on stack, push
            curr.push(d);
        } else {  // if current stack filled
            if (curr.next == null) {  // if current stack latest
                Stack n = new Stack(curr.stackNum + 1,curr); // create new stack
                curr.next = n;
                curr = n;
            } else {   // if current stack not latest, go to latest
                while (curr.next != null) 
                    curr = curr.next;
            }
            curr.push(d);
        }
    }
    
    int pop() {
        // make sure we are at latest stack to pop from
        while (curr.next != null) {
            curr = curr.next;
        }
        // if still nodes on this stack, pop
        if (curr.numNodes > 0) {
            int res = curr.pop()
            return res;
        } else {  // otherwise, return to top of previous stack and pop
            curr = curr.prev;
            curr.next = null; // remove now empty stack
            int res = curr.pop();
            return res;
        }
    }
    
    void printAllStacks() { 
        Stack temp = curr;
        while (curr.prev != null) // return to first stack
            curr = curr.prev;
        while (curr != null) { // print them all in order
            curr.printStack();
            curr = curr.next;
        }
        curr = temp        
    }
}

class Stack {
    int stackNum;
    int numNodes;
    Node top;
    Stack prev;
    Stack next;
    
    public Stack() {
        stackNum = 1;
        top = null;
        numNodes = 0;
        next = null;
        prev = null;
    }
    
    public Stack(int n,Stack p) {
        stackNum = n;
        numNodes = 0;
        top = null;
        next = null;
        prev = p;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
        numNodes++;
        System.out.println(top.data + " pushed to stack "+stackNum);
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        numNodes--;
        return res;
    }
  
    void printStack() {
        System.out.println("\nCurrent stack # " + stackNum + " (top to bottom):");
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Node n = top;
        while (n != null) {
            System.out.println("\t"+n.data);
            n = n.next;
        }
    }
}
        

public static void main (String[] args)
{
    SetOfStacks sos1 = new SetOfStacks(4);
    
    sos1.push(50);
    sos1.push(4);
    sos1.push(18);
    sos1.push(3);
    sos1.push(12);
    sos1.printAllStacks();

    System.out.println("\nPopped: " + sos1.pop());
    System.out.println("Popped: " + sos1.pop());

    sos1.printAllStacks();
    sos1.push(44);
    System.out.println("Popped: " + sos1.pop());
}

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

// D. Scott
// CCI - Problem 3.3
// Immplement a set of stacks with same operations as stack
// (stacks autosplit after reaching certain size)

class SetOfStacks {
    int maxSize;  // limit for stack size (create new stack when >)
    Stack curr;   // currently active stack
    
    public SetOfStacks(int s) {
        maxSize = s;
        Stack n = new Stack();
        curr = n;
    }
    
    void push(int d) {
        if (curr.numNodes < maxSize) {  // if room on stack, push
            curr.push(d);
        } else {  // if current stack filled
            if (curr.next == null) {  // if current stack latest
                Stack n = new Stack(curr.stackNum + 1,curr); // create new stack
                curr.next = n;
                curr = n;
            } else {   // if current stack not latest, go to latest
                while (curr.next != null) 
                    curr = curr.next;
            }
            curr.push(d);
        }
    }
    
    int pop() {
        // make sure we are at latest stack to pop from
        while (curr.next != null) {
            curr = curr.next;
        }
        // if still nodes on this stack, pop
        if (curr.numNodes > 0) {
            int res = curr.pop()
            return res;
        } else {  // otherwise, return to top of previous stack and pop
            curr = curr.prev;
            curr.next = null; // remove now empty stack
            int res = curr.pop();
            return res;
        }
    }
    
    void printAllStacks() { 
        Stack temp = curr;
        while (curr.prev != null) // return to first stack
            curr = curr.prev;
        while (curr != null) { // print them all in order
            curr.printStack();
            curr = curr.next;
        }
        curr = temp        
    }
}

class Stack {
    int stackNum;
    int numNodes;
    Node top;
    Stack prev;
    Stack next;
    
    public Stack() {
        stackNum = 1;
        top = null;
        numNodes = 0;
        next = null;
        prev = null;
    }
    
    public Stack(int n,Stack p) {
        stackNum = n;
        numNodes = 0;
        top = null;
        next = null;
        prev = p;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
        numNodes++;
        System.out.println(top.data + " pushed to stack "+stackNum);
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        numNodes--;
        return res;
    }
  
    void printStack() {
        System.out.println("\nStack # " + stackNum + " (top to bottom):");
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Node n = top;
        while (n != null) {
            System.out.println("\t"+n.data);
            n = n.next;
        }
    }
}
        

public static void main (String[] args)
{
    SetOfStacks sos1 = new SetOfStacks(16);

    // Push 89 values onto 6 stacks:
    for (int i = 0; i < 89; i++) {
        sos1.push(i*3);
    }
    sos1.printAllStacks();
    
    // Pop 16 values from 2 stacks:
    System.out.println("\n");
    for (int i = 0; i < 12; i++) {
        System.out.println("Popped: " + sos1.pop());
    }
    sos1.printAllStacks();

//    System.out.println("\nPopped: " + sos1.pop());
//    System.out.println("Popped: " + sos1.pop());

 //   sos1.printAllStacks();
 //   sos1.push(44);
//    System.out.println("Popped: " + sos1.pop());
}

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

// D. Scott
// CCI - Problem 3.3 FOLLOW UP
// Immplement a set of stacks with same operations as stack
// (this time with popAt functionality to pop from a specific stack)

class SetOfStacks {
    int maxSize;  // limit for stack size (create new stack when >)
    Stack curr;   // currently active stack
    
    public SetOfStacks(int s) {
        maxSize = s;
        Stack n = new Stack();
        curr = n;
    }
    
    void push(int d) {
        if (curr.numNodes < maxSize) {  // if room on stack, push
            curr.push(d);
        } else {  // if current stack filled
            if (curr.next == null) {  // if current stack latest
                Stack n = new Stack(curr.stackNum + 1,curr); // create new stack
                curr.next = n;
                curr = n;
            } else {   // if current stack not latest, go to latest
                while (curr.next != null) 
                    curr = curr.next;
            }
            curr.push(d);
        }
    }
    
    int pop() {
        // make sure we are at latest stack to pop from
        while (curr.next != null) {
            curr = curr.next;
        }
        // if still nodes on this stack, pop
        if (curr.numNodes > 0) {
            int res = curr.pop()
            return res;
        } else {  // otherwise, return to top of previous stack and pop
            curr = curr.prev;
            curr.next = null; // remove now empty stack
            int res = curr.pop();
            return res;
        }
    }
    
    int popAt(int index) {
        // return to stack 1:
        while (curr.prev != null)
            curr = curr.prev;
        // travel to desired stack:
        int count = 1;
        while (count < index) {
            if (curr.next != null) {
                curr = curr.next;
                count++;
            } else {
                System.out.println("The stack number provided is invalid.");
                return -1;
            }
        }
        return curr.pop();
    }
    
    void printAllStacks() { 
        Stack temp = curr;
        while (curr.prev != null) // return to first stack
            curr = curr.prev;
        while (curr != null) { // print them all in order
            curr.printStack();
            curr = curr.next;
        }
        curr = temp        
    }
}

class Stack {
    int stackNum;
    int numNodes;
    Node top;
    Stack prev;
    Stack next;
    
    public Stack() {
        stackNum = 1;
        top = null;
        numNodes = 0;
        next = null;
        prev = null;
    }
    
    public Stack(int n,Stack p) {
        stackNum = n;
        numNodes = 0;
        top = null;
        next = null;
        prev = p;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
        numNodes++;
        System.out.println(top.data + " pushed to stack "+stackNum);
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        numNodes--;
        return res;
    }
  
    void printStack() {
        System.out.println("\nStack # " + stackNum + " (top to bottom):");
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Node n = top;
        while (n != null) {
            System.out.println("\t"+n.data);
            n = n.next;
        }
    }
}
        

public static void main (String[] args)
{
    SetOfStacks sos1 = new SetOfStacks(16);

    // Push 89 values onto 6 stacks:
    for (int i = 0; i < 89; i++) {
        sos1.push(i*3);
    }
    sos1.printAllStacks();
    
    System.out.println("\nPopped: " + sos1.popAt(4) + " from stack 4.");
    System.out.println("\nPopped: " + sos1.popAt(2) + " from stack 2.");
    System.out.println("\nPopped: " + sos1.popAt(6) + " from stack 6.");
    System.out.println("\nPopped: " + sos1.popAt(2) + " from stack 2.");
    System.out.println("\nPopped: " + sos1.popAt(1) + " from stack 1.");
    System.out.println("\nPopped: " + sos1.popAt(2) + " from stack 2.");    

}

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}