2 minute read

Stack

interface StackAPI<T> {
    void push(T element);
    T pop();
}

List Implementation

class MyListStack implements StackAPI<T> {
    int size;
    Node head;
    Node tail;
    
    public MyListStack() {
        size = 0;
        head = null;
        tail = null;
    }
    
    @Override 
    public void push(int element) {
        // add the element to the tail of list
        if (head == null) { // initial status, no element in stack
            head = new Node(element);
            tail = head;
        } else {
            tail.next = new Node(element);
            tail.next.prev = tail;
            tail = tail.next;
        }
        size++;
    }
    
    @Override T pop() {
        if (size == 0) {
            return null;
        }
        Node res = null;
        // pop the element from the head of list
        if (head == tail) { // if there is only one element in list
            res = head;
            head = null;
            tail = null;
        } else {
            res = tail;
            tail = res.prev;
           	tail.next = null;
            res.prev = null;
        }
        size--;
        return res;
    }
}

class Node {
    int val;
    Node prev;
    Node next;
    public Node(int i) {
        this.val = i;
        this.prev = null;
        this.next = null;
    }
}

Array Implementation

class MyArrayStack implements StackAPI {
    int[] arr;
    int size;
    
    public MyArrayStack(int capacity) {
        arr = new int[capacity];
        size = 0;
    }
    
    @Override
    public void push(int element) {
        if (size == capacity) {
            return;
        }
        arr[size++] = element;
    }
    
    @Override
    public Integer pop() {
        if(size == 0) {
            return null;
        }
        return arr[--size];
    }
}

Queue

interface QueueAPI<T> {
    void push(T element);
    T pop();
}

List Implementation

public class MyListQueue implements QueueAPI<Integer>{
    
   @Override 
    public void push(int element) {
        // add the element to the tail of list
        if (head == null) { // initial status, no element in stack
            head = new Node(element);
            tail = head;
        } else {
            tail.next = new Node(element);
            tail.next.prev = tail;
            tail = tail.next;
        }
        size++;
    }
    
    @Override T pop() {
        if (size == 0) {
            return null;
        }
        Node res = null;
        // pop the element from the head of list
        if (head == tail) { // if there is only one element in list
            res = head;
            head = null;
            tail = null;
        } else {
            res = head;
            head = head.next;
            res.next = null;
            head.prev = null;
        }
        size--;
        return res;
    }
}

Array Implementation

public class MyArrayQueue implements QueueAPI<Integer> {
    int[] arr;
    int size;
    int head;
    int tail;
    
    public MyArrayQueue(int capacity) {
        arr = new int[capacity];
        size = 0;
        head = 0;
        tail = 0;
    }
    @Override 
    public void push(Integer element) {
        if(size == capacity) {
            return;
        }
        
        if (tail == arr.length) {
            tail = 0;
        }
        arr[tail++] = element;
        size++;
    }
    
    @Override
    public Integer pop() {
        if(size == 0) {
            return null;
        }
        if (head == arr.length) {
            head = 0;
        }
        return arr[head++];
    }
}