Stack

1.Introduction

• Last element you add to the stack is the first one you access (Last In First Out)

• Top (最後一個)

• Push: Adding a new element to the top of the stack

• Pop: Removing an element from the top of the stack

• Peek

2.The complexity

• Push, pop: O(1)

• isEmpty, IsFull, size: O(1)

3.Where can stacks be used

• Implementing undo in an application

• Implementing the back button on the web browser

• Holding the memory for recursive calls in a programming language

• Translating infix notation for expressions to postfix

4.Match parenthesis in an expression

• map: 存放} {, ) (, ] [

• set: 存放{, (, [

• stack: 後進先出, 用來確認上一個元素是否符合map的值

private static final Map<Character, Character> matchingParentsMap = new HashMap<>();
private static final Set<Character> openingParentSet = new HashSet<>();
static {
    matchingParentsMap.put(')', '(');
    matchingParentsMap.put(']', '[');
    matchingParentsMap.put('}', '{');
    openingParentSet.addAll(matchingParentsMap.values());
}

public static boolean hasMatchingParents(String input) {
    try {
        Stack<Character> parentStack = new Stack();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            // Add to the stack for an opening parent
            if (openingParentSet.contains(ch)) {
                parentStack.push(ch); 
            }
            if (matchingParentsMap.contains(ch)) {
                Character lastParent = parentStack.pop();
                if (lastParent != matchingParentsMap.get(ch)) {
                    return false;
                }
            }
        }
        return parentStack.isEmpty();
    } catch (Stack.StackOverflowException soe) {
        System.err.println("Stack StackOver");
    } catch (Stack.StackUnderflowException sue) {
        System.err.println("Stack StackUnder");
    }
}

5.Find the minimum element in a stack in constant time

• 155. Min Stack​
• Keep track of the minimum element for each element pushed on to th stack

• Have 2 stacks, one to hold the actual elements, and another to hold the minimum element corresponding to every element added to the stack

public static class MinimumStack{
    private Stack<Integar> stack = new Stack<>;
    private Stack<Integar> minimumStack = new Stack<>;
    
    public void push(int data) throws
        Stack.StackOverflowException,Stack.StackUnderflowException {
        int min = data;
        if (!miniStack.isEmpty()) {
            if (min > minimumStack.peek()) {
                min = minimumStack.peek();
            }
        }
        stack.push(data);
        minimumStack.push(min);
    } 
    
    public int pop() throw Stack.StackUnderflowException {
        minimumStack.pop();
        return stack.pop();
    }
    
    public int getMinimum() throw Stack.StackUnderflowException {
        return minimumStack.peek();
    }
}