# Stack

## Intro

First in last out (FILO)

## Applications

* Parenthesis Matching
* Iterative implementation of DFS
* Monotonic (Increasing/Decreasing) Stack

## Interface

```java
public interface Stack<T> {
    public Stack<T> push(T ele);
    public T pop();
    public boolean isEmpty();
}
```

## Array Implementation

```java
public class StackArray<T> implements Stack<T> {
    private T[] arr;
    private int total;

    public StackArray() {
        arr = (T[]) new Object[2];
    }

    private void resize(int capacity) {
        T[] tmp = (T[]) new Object[capacity];
        System.arraycopy(arr, 0, tmp, 0, total);
        arr = tmp;
    }

    @Override
    public Stack<T> push(T ele) {
        if (arr.length == total)
            resize(total * 2);
        arr[total++] = ele;
        return this;
    }

    @Override
    public T pop() {
        if (total == 0)
            throw new NoSuchElementException();
        T ele = arr[--total];
        arr[total] = null;
//      if (total > 0 && total == arr.length / 4)
//          resize(arr.length / 2);
        return ele;
    }

    @Override
    public boolean isEmpty() {
        return total == 0;
    }
}
```

```python
# equivalent in python 
stack = []
stack.append(T)
stack.pop()
```

## Linked List Implementation

```java
public class StackLinkedList<T> implements Stack<T> {
    private class ListNode<T> {
        T data;
        ListNode<T> next;
        ListNode(T val) { data = val; }
    }

    private ListNode top;

    @Override
    public Stack<T> push(T ele) {
        ListNode previous = top;
        top = new ListNode(ele);
        top.next = previous;
        return this;
    }

    @Override
    public T pop() {
        if (top == null)
            throw new NoSuchElementException();
        ListNode current = top;
        top = top.next;
        return (T) current.data;
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }
}
```

```python
# Equivalent in Python 
from collections import deque 
# double ended queue (pronounced as "deck") 
stack = deque()
stack.append(T)
stack.pop() 
```

## References

* [Implementing a Stack in Java](http://eddmann.com/posts/implementing-a-stack-in-java-using-arrays-and-linked-lists/) by Edd Mann
* [How to Implement a Python Stack](https://realpython.com/how-to-implement-python-stack/) by Real Python&#x20;