# 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;


---

# 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/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.