Stack

is an abstract data type that serves as a collection of elements, with two principal operations: push , which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.

Examine the item most recently added.

LIFO = "last in first out"

Application:

主要用于:

1. 暂且保存有效信息

2. 反转栈的运用

3. 优化DFS，转变为非递归

具体运用：

1. recursion

2. Backtracking

3. Expression evaluation and syntax parsing

   1. Reverse Polish notation
   2. calculation
4. Efficient Algorithm (单调栈)
5. Runtime memory management
6. Parsing in a compiler.
7. Java virtual machine.
8. Undo in a word processor.
9. Back button in a Web browser.
10. PostScript language for printers.
11. Implementing function calls in a compiler.

Typical Questions：

1. Min Stack

2. Implement Queue using Stacks (one regular sequence, another reverse order)

3. Valid Parentheses

4. Basic Calculator

5. Largest Rectangle in Histogram & Next Greater Element II &132 Pattern（单调栈）

Complexity：

The time complexity of push and _pop _operations should be O(1)

Implementation:

• overflow and underflow

• Null items (allow null in stack)

• Loitering

• Iterable

• Generic

another solution: here

pop(), push(), isEmpty(), peek()

interface Stack<T> {
    Stack<T> push(T ele);
    T pop();
}

Array:

// public class Stack<Item> implements Iterable<Item>
{ // 
public class StackArray<T> implements Stack<T> {

    private T[] arr;

    private int total;

    public StackArray() {
        // arr = new T[2]; generic array creation is not allowed in Java
        arr = (T[]) new Object[2];      // ugly cast 
    }

    private void resize(int capacity) {        // 这里如果是growArray实现的话，push()的复杂度可能增加
        T[] tmp = (T[]) new Object[capacity];
        System.arraycopy(arr, 0, tmp, 0, total);
        arr = tmp;
    }
    // resize() method only recalled when stack's size is a power of 2
    // There are ~log2N power of 2 between 1 and N
    // resize() recalled by logN times
    // Time complexity is N + (2 + 4 + 8 + ..+ N) = 3N 
    // amortized cost when add
    public StackArray<T> push(T ele) {
        if (arr.length == total) resize(arr.length * 2);                    // overflow
        arr[total++] = ele;
        return this;
    }

    public T pop() {
        if (isEmpty()) throw new java.util.NoSuchElementException();            // underflow
        T ele = arr[--total];
        arr[total] = null;                                                    // Avoid Loitering
        if (total > 0 && total == arr.length / 4) resize(arr.length / 2);     // shrink
        return ele;
    }

    @Override
    public String toString() {
        return java.util.Arrays.toString(arr);
    }
    public boolean isEmpty() {
        return total == 0;
    }

}

Linked List:

public class StackLinkedList<T> implements Stack<T> {

    private int total;

    private Node first;

    // Node should not be exposed to the outside. 
    // Users of the stack should not have to know its inner workings

    private class Node {
        private T ele;
        private Node next;
    }

    public StackLinkedList() { }

    public StackLinkedList<T> push(T ele) {
        Node current = first;
        first = new Node();
        first.ele = ele;
        first.next = current;
        total++;
        return this;
    }

    public T pop() {
        if (first == null) new java.util.NoSuchElementException();
        T ele = first.ele;
        first = first.next;
        total--;
        return ele;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node tmp = first;
        while (tmp != null) {
            sb.append(tmp.ele).append(", ");
            tmp = tmp.next;
        }
        return sb.toString();
    }

    public boolean isEmpty() {
        return total < 0 || first == null;
    }

}