# 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();
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.