// D. Scott
// CCI - Problem 3.5
// Sort a stack from smallest to largest elements using only
// one additional stack as a buffer

class Stack {
    Node top;
    
    public Stack() {
        top = null;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        return res;
    }
    
    
    int peek() {
        if (top == null) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return top.data;
    }
        
    boolean isEmpty() {
        if (top == null)
            return true;
        else
            return false;
    }
    
    void printStack(int stNum) {
        System.out.println("\nStack " + stNum + " contents:");
        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;
        }
    }
    // print reverse of stack:
    void printRev() {
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Stack rev = new Stack();
        Node n = top;
        while (n != null) {
            rev.push(n.data);
            n = n.next;
        }
        rev.printStack();
    }
}
        

public static void main (String[] args)
{
    Stack s1 = new Stack();
    s1.push(56);
    s1.push(4);
    s1.push(96);
    s1.push(128);
    s1.push(22);
    
    s1.printStack(1);
    
    Stack s2 = new Stack();
    
    while (s1.top.next != null) {
        if (s1.peek() < s1.top.next.data) {
            s2.push(s1.pop());
        } else {
            int temp_pop = s1.pop();
            s2.push(s1.pop());
            s1.push(temp_pop);
            s1.printStack(1);
            s2.printStack(2);
        }
        while (s2.top.next != null) {
            if (s2.peek() > s2.top.next.data) {
                break;
            } else {
                int temp_pop = s2.pop();
                s1.push(s2.pop());
                s2.push(temp_pop);
            }
            s1.printStack(1);
            s2.printStack(2);
        }
    
    s1.printStack(1);
    s2.printStack(2);
    System.out.println("--------------------");
    }
    
    s2.push(s1.pop());
    while (!s2.isEmpty())
        s1.push(s2.pop())
    s1.printStack(1);
    s2.printStack(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;
    }
}

// D. Scott
// CCI - Problem 3.5
// Sort a stack from smallest to largest elements using only
// one additional stack as a buffer

import java.util.Random;


class Stack {
    Node top;
    
    public Stack() {
        top = null;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        return res;
    }
    
    
    int peek() {
        if (top == null) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return top.data;
    }
        
    boolean isEmpty() {
        if (top == null)
            return true;
        else
            return false;
    }
    
    void printStack(int stNum) {
        System.out.println("\nStack " + stNum + " contents:");
        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;
        }
    }
    // print reverse of stack:
    void printRev() {
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Stack rev = new Stack();
        Node n = top;
        while (n != null) {
            rev.push(n.data);
            n = n.next;
        }
        rev.printStack();
    }
}
        

public static void main (String[] args)
{
    Stack s1 = new Stack();
    Random rand = new Random();
 
    // fill stack with randomly generated numbers between 0-140
    for (int i = 0; i < 30; i++) {
        int num = rand.nextInt(140);
        s1.push(num);
    }
    System.out.println("Presort stack:");
    s1.printStack(1);
    
    Stack s2 = new Stack();
    
    while (s1.top.next != null) {
        if (s1.peek() <= s1.top.next.data) {
            s2.push(s1.pop());
        } else {
            int temp_pop = s1.pop();
            s2.push(s1.pop());
            s1.push(temp_pop);
        }
        while (s2.top.next != null) {
            if (s2.peek() >= s2.top.next.data) {
                break;
            } else {
                int temp_pop = s2.pop();
                s1.push(s2.pop());
                s2.push(temp_pop);
            }
        }
    
    }
    
    s2.push(s1.pop());
    while (!s2.isEmpty())
        s1.push(s2.pop())
    System.out.println("\nPostsort stack:");
    s1.printStack(1);
    
}

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;
    }
}