> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/stack.md).

# Stack

## 1.Introduction 

* Last element you add to the stack is the first one you access (**L**ast **I**n **F**irst **O**ut)
* 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

* [x] &#x20;[155. Min Stack](https://jenhsuan.gitbook.io/algorithm/leetcode/155.-min-stack-1)​
* [ ] 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();
    }
}
```