[ADSx] - StackAndQueueFun

import java.util.ListIterator;
import java.util.Stack;

public class StackAndQueueFun {
    public static void main(String args[]) {
    }
}

/**
 * https://stackoverflow.com/questions/5134127/sorting-a-queue-using-same-queue
 * */

class SortStack {
    /**
     * https://www.geeksforgeeks.org/sort-stack-using-temporary-stack/
     */

    // This function return the sorted stack
    public static Stack<Integer> sortStack(Stack<Integer> input) {
        Stack<Integer> tmpStack = new Stack<>();
        while (!input.isEmpty()) {
            // pop out the first element
            int tmp = input.pop();

            System.out.printf("tmp: %d | input: %s | tmpStack: %s\n", tmp, input, tmpStack);

            // while temporary stack is not empty and
            // top of stack is greater than temp
            while (!tmpStack.isEmpty() && tmpStack.peek() < tmp) {
                // pop from temporary stack and
                // push it to the input stack
                input.push(tmpStack.pop());
            }


            // push temp in temporary stack
            tmpStack.push(tmp);
            System.out.printf("tmp: %d | input: %s | tmpStack: %s\n", tmp, input, tmpStack);
        }
        return tmpStack;
    }

    // Driver Code
    public static void main(String args[]) {
        Stack<Integer> input = new Stack<>();
        input.add(34);
        input.add(3);
        input.add(31);
        input.add(98);
        input.add(92);
        input.add(23);

        // This is the temporary stack
        Stack<Integer> tmpStack = sortStack(input);
        System.out.println("Sorted numbers are:");

        while (!tmpStack.empty()) {
            System.out.print(tmpStack.pop() + " ");
        }
    }
}

// Java program to sort a Stack using recursion
// Note that here predefined Stack class is used
// for stack operation
class SortStackRecursion {
    /**
     * https://www.geeksforgeeks.org/sort-a-stack-using-recursion/
     */

    // Recursive Method to insert an item x in sorted way
    static void sortedInsert(Stack<Integer> s, int x) {
        // Base case: Either stack is empty or newly inserted
        // item is greater than top (more than all existing)
        if (s.isEmpty() || x > s.peek()) {
            s.push(x);
            return;
        }

        // If top is greater, remove the top item and recur
        int temp = s.pop();
        sortedInsert(s, x);

        // Put back the top item removed earlier
        s.push(temp);
    }

    // Method to sort stack
    static void sortStack(Stack<Integer> s) {
        // If stack is not empty
        if (!s.isEmpty()) {
            // Remove the top item
            int x = s.pop();

            // Sort remaining stack
            sortStack(s);

            // Push the top item back in sorted stack
            sortedInsert(s, x);
        }
    }

    // Utility Method to print contents of stack
    static void printStack(Stack<Integer> s) {
        ListIterator<Integer> lt = s.listIterator();

        // forwarding
        while (lt.hasNext())
            lt.next();

        // printing from top to bottom
        while (lt.hasPrevious())
            System.out.print(lt.previous() + " ");
    }

    // Driver method
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(30);
        s.push(-5);
        s.push(18);
        s.push(14);
        s.push(-3);

        System.out.println("Stack elements before sorting: ");
        printStack(s);

        sortStack(s);

        System.out.println(" \n\nStack elements after sorting:");
        printStack(s);

    }
}


class ReverseStackRecursion {
    /**
     * https://www.geeksforgeeks.org/reverse-a-stack-using-recursion/
     * */

    //using Stack class for stack implementation
    static Stack<Character> st = new Stack<>();

    // Below is a recursive function that inserts an element
    // at the bottom of a stack.
    static void insert_at_bottom(char x) {

        if (st.isEmpty())
            st.push(x);

        else {
            /* All items are held in Function Call Stack until we
               reach end of the stack. When the stack becomes
               empty, the st.size() becomes 0, the
               above if part is executed and the item is inserted
               at the bottom */

            char a = st.peek();
            st.pop();
            insert_at_bottom(x);

            //push allthe items held in Function Call Stack
            //once the item is inserted at the bottom
            st.push(a);
        }
    }

    // Below is the function that reverses the given stack using
    // insert_at_bottom()
    static void reverse() {
        if (st.size() > 0) {
            /* Hold all items in Function Call Stack until we
               reach end of the stack */
            char x = st.peek();
            st.pop();
            reverse();
            /* Insert all the items held in Function Call Stack
               one by one from the bottom to top. Every item is
               inserted at the bottom */
            insert_at_bottom(x);
        }
    }


    // Driver method
    public static void main(String[] args) {
        //push elements into the stack
        st.push('1');
        st.push('2');
        st.push('3');
        st.push('4');

        System.out.println("Original Stack");

        System.out.println(st);

        //function to reverse the stack
        reverse();

        System.out.println("Reversed Stack");

        System.out.println(st);
    }
}


// Java program to implement HisStack using linked
// list so that reverse can be done with O(1)
// extra space.
class HisStackNode {
    int data;
    HisStackNode next;

    public HisStackNode(int data) {
        this.data = data;
        this.next = null;
    }
}

class HisStack {
    HisStackNode top;

    // Push and pop operations
    public void push(int data) {
        if (this.top == null) {
            top = new HisStackNode(data);
            return;
        }
        HisStackNode s = new HisStackNode(data);
        s.next = this.top;
        this.top = s;
    }

    public HisStackNode pop() {
        HisStackNode s = this.top;
        this.top = this.top.next;
        return s;
    }

    // prints contents of HisStack
    public void display() {
        HisStackNode s = this.top;
        while (s != null) {
            System.out.print(" " + s.data);
            s = s.next;
        }
        System.out.println();
    }

    // Reverses the HisStack using simple
    // linked list reversal logic.
    public void reverse() {
        HisStackNode prev, cur, succ;
        cur = prev = this.top;
        cur = cur.next;
        prev.next = null;
        while (cur != null) {

            succ = cur.next;
            cur.next = prev;
            prev = cur;
            cur = succ;
        }
        this.top = prev;
    }
}

class reverseHisStackWithoutSpace {
    public static void main(String[] args) {
        HisStack s = new HisStack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println("Original HisStack");
        s.display();

        // reverse
        s.reverse();

        System.out.println("Reversed HisStack");
        s.display();
    }
}