Stacks and Queues

Last Updated: 2024-01-17

Basic Stack

class Stack<T> {
    class Node {
        T data;
        Node next;
    }

    protected int size;
    protected Node top;

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

    public int size() {
        return size;
    }

    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return top.data;
    }

    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is Empty.");
        }

        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public void push(T data) {
        Node tmp = top;
        top = new Node();
        top.data = data;
        top.next = tmp;
        size++;
    }
}

Stack with O(1) Min Operation

Store a min value in each node. Could be redundant.

class StackWithMin extends Stack<Integer> {

    class NodeWithMin extends Stack<Integer>.Node {
        int min;
    }

    public void push(int data) {
        int m = Math.min(data, min());
        NodeWithMin tmp = ((NodeWithMin) top);
        top = new NodeWithMin();
        top.data = data;
        ((NodeWithMin) top).min = m;
        top.next = tmp;
        size++;
    }

    public int min() {
        if (isEmpty()) {
            return Integer.MAX_VALUE;
        }
        return ((NodeWithMin) top).min;
    }
}

Use another stack to store min values.

class StackWithMin extends Stack<Integer> {
    private Stack<Integer> minStack;

    public StackWithMin() {
        minStack = new Stack<Integer>();
    }

    public Integer pop() {
        int data = super.pop();
        if (data == min()) {
            minStack.pop();
        }
        return data;
    }

    public void push(int data) {
        if (data < min()) {
            minStack.push(data);
        }
        super.push(data);
    }

    public Integer min() {
        if (isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }
}

By Language

Java

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(i);
stack.pop();

stack.isEmpty();

Python

List can be used as a stack:

stack = []
stack.append(1)
stack.pop()

# Check empty
not stack

Use collections.deque for quicker append() and pop():

from collections import deque

stack = deque()

stack.append(1)
stack.pop()