Stack

first come last out

• LinkedList implementation
  • push to the first node by storing the original first node and then point the new node to the OG first node
  • pop, simple remove the first node
  • both OPs take O(1) even in the worst case, but use the extra space

• Array implementation

  • use an index as the pos of the head of the stack
  • push, add the new item to array
  • pop, decrement N and then use to index into array

  • Analysis:

    • Loitering Holding a reference to an object when it is no longer needed

    //loitering
    public String pop() { return s[--N];}
    //garbage collector can reclaim memory only if no outstanding references
    public String pop() {
      String item = s[--N];
      s[N] = null;
      return item;
    }
    

    • even faster, but require clients to provide capacity,
      • double the size of array when array is full
        • 虽然每次 resieze 都要copy 过去，所以操作复杂度为$$N+(2+4+8+...+N) $$~$$3N$$, 这里 N 为 N 次 push 的花费，$$2+...+N$$为每次 double size 的花销，这里用Amortized Analysis：Average running time per op over a worst-case sequence of ops 算起来仍为3N/N 仍然是 constant，
          • halve size of the array when array is one-quarter full
        • It will be very expensive doing half full when the case (push, pop, push, pop...)
          • Array is always between 25% and 100%
          • every op takes constant amoritzed time, and less wasted space

Stack 的另一个应用就是当题目所问涉及到先后的相对关系。（必须要先有a再有b之类的）

Min Stack

两种思路

1. Stack中需要保存的不一定就是直接的input值，有可能用别的，比如这题就可以保存currentVal - minVal的gap，利用了stack的特点，可以知道在变换minVal之前，可以通过minVal和gap恢复出input。那么现在唯一的问题就是，如果找到变换之前的minVal。可以发现变换后的minVal必定是某一次的input，那么就可以通过之前的gap的关系式，找回变换前的minVal
2. 把变换前的minVal也push到stack中。这样就可以保存minVal，并且知道在这种情况下，minVal在stack中存了两次（而且一定要在push input之前，这样就能保证top的时候拿到的是input值而非min）于是唯一的问题就是，在pop的时候，发现当前的minVal被pop出来，则要再pop一次

long min;
    Stack<Long> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
        }
        stack.push((long)(x - min));

        if (x < min) {
            min = x;
        } 
    }

    public void pop() {
        long val = stack.pop();
        if (val < 0) {
            min -= val;
        }
    }

    public int top() {
        long top = stack.peek();
        if (top > 0)
            return (int)(top + min);
        else 
            return (int) min;
    }

    public int getMin() {
        return (int)min;
    }

    // method 2
    class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) min=stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

Longest Absolute File Path

• 遇到路径问题，基本都用stack来做
• 因为在遍历的时候，需要往回找到parent，而DFS的方法又不好想，所以想到可以利用stack来做
• 在stack.pop或者peek操作的时候，要注意确保stack不为空，如果担心初始操作的影响，可以通过加入不影响结果的dummy value来防止这种情况
• 运用stack的关键，在于
  • 1. stack里存的是什么，这里很明显，存放的是这个『点』的长度
  • 1. 什么时候pop，这里要得到parent的时候，即当size比当前的level大，可以这么理解，因为要获得当前这个点的length，那么就要找到他的parent路径的length，所以stack里，只能存到他的parent节点（即上一层）。这一层的所有其他的点都不许存在

• 注意对题意的理解，只有到遇到文件的时候，才是要更新最大值的时候

• 解法2，用HashMap保存< level，到level的path的长度 >注意这里是永远update，不管是不是最大，因为每次更新的时候，之前的值要么已经保存到max中了，要么就没用了

• 这个解法同样可以从dp角度去理解