数据结构相互实现（A.K.A）

Abstract class vs Interface

• Interface: no fields. only abstract methods, which is not have be implemented

• Abstract: can have abstract and non-abstract, can be implemented or not implemented, single inherent 必须实体必须实现

• benefit to create abstract: could be enforcement, so implement polimorfismo.

Design a Stack using LinkedList

• use single linked list, with head

• add the value at the head position

• head = head.next, the old head don't have to be deleted, but it may take some difficulties to the garbage collection in the future

public class MyStack{
    //fields
    private ListNode<T> head;
    
    //methods
    public MyStack(){
        head = null;
    }
    
    public void push(T item){
        ListNode<T> newNode = new ListNode<T>(item);
        newNode.next = head;
        head = newNode;
    }
    
    public T pop(){ //null pointer exception
        if(head == null) return null;
        ListNode<T> popNode = head;
        head = head.next;
        popNode.next = null;
        return popNode.item;
    }
    
    public T peek(){
        return head == null ? null : head.item;
    }
}

Design a Queue using LinkedList

single linked list: tail in, head out;

• double linked list 实现queue，既可以头进尾巴出，也可以尾巴出头进

  • offer: 看tail，need to check from 0 to 1, or 1 to many

  • poll: check if it is null, check 1 to 0, or many to 1

public class MyQueue<E> {
    //fields
    private ListNode<E> head;
    private ListNode<E> tail;
    int length;
    
    //methods
    MyQueue(){
        head = null; //head = tail = null;
        tail = null;
    }
    public void offer(E val){
        if(tail == null){
            tail = new ListNode<>(val);
            head = tail 
        }else{
            ListNode<E> newTail = new ListNOde<>(val);
            tail.next = newTail;
            newTail.prev = tail;
            tail = newTail;
            }
        length++;
    }
    
    pubic E poll(){
        if(head == null) return null;
        ListNode<E> temp = head;
        if(head == tail){
            head = null;
            tail = null;
        }else{
            head = head.next;
            head.prev = null;
            temp.next = null;
        }
        length--;
        return temp.val;
        
    }
    public E peek(){
        if(head == null) return null;
        return head.val;
    
    }
}

Design a Queue using Array with certain Capacity

• use destroy instead of delete, which is most safe, but high time use; delete is only delete the reference

  • offer:先赋值， 后tail++

  • poll: 先读值，head++

  • peek: read arr[head]

• head and tail position valid queue[head,tail)

• defaut: head tail all in the index 0

• cirular Array首尾相接 --> % array.length

• head == tail --> full or empty --> flag, size vs capacity

public class ArrayQueue<E>{
    //fields
    private E[] array;
    private int head;
    private int tail;
    private int size;
    
    private static final int DEFAULT_CAPACITY = 10;
    
    //method
    public ArrayQueue(int capacity){
        array = new E[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }
    public ArrayQueue(){
        this(DEFAULT_CAPACITY);
    }
    public boolean offer(E val){
        if(size == array.length) return false;
        aray[tail] = val;
        tail = (tail + 1) % array.length; //不会访问到一个出界的tail       
        size++;
        return true;
    }
    public E poll(){
        if(size == 0) return null;
        E res = array[head];
        head = (head + 1) % array.length;
        size--;
        return res;
    }
    public E peek(){
        return size == 0 ? null : array{head]; 
    }
}

Design a Stack using Array with certain capacity

• head

• push -> assign, head++

• pop --> head--, get

• peek --> array[head-1]

• [0,head)

• [0,head]

public class MyStack<T>{
    private T[] array;
    private int head;
    
    public MyStack(int c){
        array = new T[c];
        head = 0;
    }
    
    public boolean offer(T val){
        if(head >= array.length) return false;
        array[head++] = val;
        return true;
    }
    
   public T peek(){
       return (head == 0) ? null : array[head - 1];
   }
    
    public T poll(){
        if(head == 0)? return null;
        return array[--head];
    }
}