Stack and Queue Problems

Algorithm

---

Learn the Data Structure first:

    class Node:
        int val;
        Node next;
        Node(int val):
            this.val = val;
    - Stack
        Node top;
        stack():
            top = null;
        pop():
            Node node;
            if(isEmpty()):
                node = null;
            else:
                node = top;
                top = top.next;
            return node;
        push(int val):
            Node node = new Node(val);
                node.next = top;
                top = node;
        peek():
            Node node;
                if(isEmpty()):
                    node = null;
                else:
                    node = top;
            return node;
        isEmpty():
            return top == null? true:false;
    - Queue
        Node head;
        Node tail;
        Queue();
            head = null;
            tail = null;
        enqueue(int val):
            Node node = new Node(val); 
            if(isEmpty()):
                first = node;
                last = node;
            else
                last.next = node;
                last = node;
        dequeue();
            if(isEmpty()):
                return null;
            else:
                Node node = first;
                first = first.next;
                return first;

Questions

1.1 Two Stacks for Queue

        Queue:
                Stack<Node> input = new Stack<Node>();
                Stack<Node> output = new Stack<Node>();
                void enqueue(int val):
                    Node node = new Node(val);
                    input.push(node);
                Node dequeue():
                    if(size()==0)
                        return null;
                    if(output.isEmpty()):
                        while(!input.isEmpty()):
                            Node tmp = input.pop();
                            output.push(tmp);
                    return output.pop();
                int size():
                    return input.size()+output.size();

1.2 Two Queues for Stack

        Stack: 
                Queue<Node> q1 = new Queue<Node>();
                Queue<Node> q2 = new Queue<Node>();
                void push(val):
                    Node node = new Node(val);              
                    q1.add(node);
                Node pop():
                    if(size()==0)
                        return null;
                    if(q1.isEmpty()):
                        while(q2.size()>1):
                            q1.add(q2.remove());
                        return q2.remove();
                    else
                        while(q1.size()>1):
                            q2.add(q1.remove());
                        return q1.remove();                     
                int size():
                    return q1.size()+q2.size();

2. Min/Max Stack

- Approach 1: Multiple Stacks:

                    Stack<E> stack = new Stack<E>();  
                    Stack<E> stackMin = new Stack<E>();//存放求最小值的栈  
                    Stack<E> stackMax = new Stack<E>();//存放求最大值的栈  
                    void push(E e):
                        if(stackMin.isEmpty()||e.comparteTo(stackMin.peek())<0)
                            stackMin.push(e);
                        if(stackMax.isEmpty()||e.comparteTo(stackMax.peek())>0)
                            stackMax.push(e);
                        stack.push(e);
                    E pop():
                        if(stack.peek()==stackMin.peek())
                            stackMin.pop();
                        if(stack.peek()==stackMax.peek())                       
                            stackMax.pop();
                        return stack.pop();
                    E max():
                        return stackMax.peek();
                    E min():
                        return stackMin.peek();

- Approach 2: Customized Data Structure:

                    class Node{
                        E e;
                        E eMin;
                        E eMax;
                        Node(E e,E eMin,E eMax):
                            this.e = e;
                            this.eMin = eMin;
                            this.eMax = eMax;
                    }
                    Stack<Node> stack = new Stack<Node>()
                    void push(E e):
                        E newMin = e.compareTo(min())<0?e:min();
                        E newMax = e.compareTo(max())>0?e:max();                    
                        Node node = new Node(e,newMin,newMax);
                        stack.push();
                    E pop():
                        return stack.pop();
                    E min():
                        return stack.peek().min;
                    E max():
                        return stack.peek().max;

3. Valid Parentheses

    boolean isValid(String s):
                Stack<Character> stack = new Stack<Character>();
                    for(int i=0;i<s.length();i++):
                        char c = s.charAt(i);
                        switch(c){
                            case '(': case '{': case '[':
                                stack.push(c);
                                break;
                            case ')':
                                if(stack.isEmpty() ||stack.pop()!='('){
                                    return false;
                                }else
                                    break;
                            case '}':
                                if(stack.isEmpty() ||stack.pop()!='{'){
                                    return false;
                                }else
                                    break;
                            case ']':
                                if(stack.isEmpty() ||stack.pop()!='['){
                                    return false;
                                }else
                                    break;
                        }
                return stack.isEmpty();

4. Evaluate Reverse Polish Notation

            enum OperatorEnum { // 注意 enumeration type 写法
                add("+"), sub("-"), mul("*"), div("/"), leftkh("("), rightkh(")");
                            // 最后一个必须是分号。
                private String value;
                public String getValue() {
                    eturn value;
                }
                OperatorEnum(String s) {
                    value = s;
                    }
            }
            int evalRPN(String[] tokens):
                        int result=Integer.MIN_VALUE;
                        Stack<Integer> stack = new Stack<Integer>();
                        for(int i=0;i<tokens.length;i++):
                                if(tokens[i].equals(OperatorEnum.add.getValue())):
                                    result = stack.pop()+stack.pop();
                                else if(tokens[i].equals(OperatorEnum.sub.getValue())):
                                    result = stack.pop()-stack.pop();
                                else if(tokens[i].equals(OperatorEnum.mul.getValue())):
                                    result = stack.pop()*stack.pop();
                                else if(tokens[i].equals(OperatorEnum.div.getValue())):
                                    int div = stack.pop();
                                    int dived = stack.pop();
                                    if(dived == 0):
                                        result = Integer.MIN_VALUE;
                                    else:
                                        result = div / dived;
                                else:
                                    result = Integer.parseInt(tokens[i]);
                                stack.push(result);
                        if (!stack.isEmpty()):
                            result = stack.pop();
                        return stack.isEmpty() ? result : Integer.MIN_VALUE;

6. Single Array implement multiple stacks(e.g. 3 stacks?)

            static array approach:

                        int stackSize = 300;
                        int[] array = new int[stackSize];
                        int[] spointer = {0,0,0};
                        void push(int sNum, int val):
                            int index = sNum*stackSize +spointer[sNum]+1;
                            spointer[sNum]++;
                            array[index] = val;
                        int pop(int sNum):
                            int index = sNum*stackSize +spointer[sNum];
                            int pop = array[index];
                            array[index] = 0;
                            spointer[sNum]--;
                            return pop;
                        int peek(int sNum):
                            return array[sNum*stackSize +spointer[sNum]];
                        boolean isEmpty(int sNum):
                            return sPointer[sNum]==0;

            dynamic linked list approach:

                        class StackNode:
                            int prev;
                            int val;
                            StackNode(int prev,int val):
                                this.val = val;
                                this.prev = prev;
                        int stackSize = 300;
                        int indexUsed = 0;
                        int[] spointer = {-1,-1,-1};
                        StackNode[] buf = new StackNode[stackSize*3];
                        void push(int sNum, int val):
                            int lastIndex = spointer[sNum];
                            spointer[sNum] = indexUsed;
                            indexUsed++;
                            buf[spointer[sNum]] = new StackNode(lastIndex, val);
                        int pop(int sNum):
                            int val = buf[spointer[sNum]].val;
                            int lastIndex = spointer[sNum];
                            spointer[sNum] = buf[spointer[sNum]].prev;
                            buf[lastIndex] = null;
                            indexUsed --;
                            return val;
                        int peek(int sNum):
                            return buf[spointer[sNum]].val;

7. Hanoi Towers

                Stack<Integer> disks;
                int index;
                Tower():
                    disks = new Stack<Integer>();
                    index= i;

将n个圆盘从柱子src移动到柱子dst，其中可以借助柱子bri(bridge)。
注：n个圆盘从上到下依次的标号依次为1到n，表示圆盘从小到大。
移动的过程中，不允许大圆盘放在小圆盘的上面。
我们定义一组元组来表示三根柱子的状态：(src上的圆盘，bri上的圆盘，dst上的圆盘) 初始状态是：(1~n, 0, 0)
 表示src上有1到n共n个圆盘，另外两个柱子上没有圆盘。 目标状态是：(0, 0, 1~n)表示dst上有1到n共n个圆盘，另外两个柱子上没有圆盘。
 由于最大的圆盘n最后是放在dst的最下面，且大圆盘是不能放在小圆盘上面的， 所以，一定存在这样一个中间状态：(n, 1~n-1, 0)，这样才能把最大的圆盘n 移动到dst的最下面。现在手头上的工具(可用的函数)只有hanoi，自然要想办法创造可以使用这个函数的情景，而不是其它情景。

            void hanoi(int n, char src, char bri, char dst):
                    if(n>0):
                        hanoi(n-1,dst,bri);
                        moveTopTo(dst);
                        bri.hanoi(n-1,this,dst);
            void moveTopTo():
                    int top = disks.pop();
                    t.add(top);
            void add(int d):
                    if(!disks.isEmpty()&&disks.peek()<=0):
                        "Error placing"
                    else
                        disks.push(d)

8. Simplify Path(For UNIX file path)

                String simplifyPath(String path):
                        Stack<String> stack = new Stack<String>();
                        String[] paths = path.split("/+");
                        for(String elem:paths):
                            if(elem.equals("."))
                                continue;
                            else if(elem.equals(".."))
                                if(stack.isEmpty()):
                                    continue;
                                stack.pop();
                            else
                                stack.push(elem);
                        String result = "";
                        while(!stack.isEmpty()):
                            result = "/" + stack.pop()+result;
                        if(result.length()==0):
                            result = "/";
                        return result;