Stack

Intro

First in last out (FILO)

Applications

• Parenthesis Matching

• Iterative implementation of DFS

• Monotonic (Increasing/Decreasing) Stack

Interface

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

Array Implementation

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

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

Linked List Implementation

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

# 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 by Edd Mann

• How to Implement a Python Stack by Real Python