Stack

In this section, we will implement two naive simple Stack here which utilised java default array and linked list.

The first one will be using array, We first define the array, initialisation and size function.

class SSEStackArray{
    private int[] arr = null;

    public SSEQueueArray(){
        arr = new int[0]; //create array with 0 size
    }
    public int size(){
        return arr.length;
    }
}

Then we define the put function which is O(n) because it copy the array:

    public void put (int toBeAdded){
        int[] tempArr = arr.clone();
        arr = new int[this.size()+1];

        //copy actually is 0(n) operation
        System.arraycopy(tempArr, 0, arr, 0, tempArr.length);

        arr[this.size()-1] = toBeAdded;
    }

Then we define the pop function which internally use remove function which is O(n) because it copy the array :

     private int remove(int idx) throws Exception {
        if (idx >= this.size()){
            throw new Exception("index bigger or equal to size");
        }else {
            int toBeReturned = arr[idx];
            int[] tempArr = arr.clone();
            arr = new int[this.size() - 1];

            //shift array actually is 0(n) operation
            for (int i=0; i< tempArr.length; i++){
                if (i < idx){
                    arr[i] = tempArr[i];
                }else if (i> idx){
                    arr[i-1] = tempArr[i];
                }
            }
            return toBeReturned;
        }
    }

    public int pop() throws Exception{
        return remove(size()-1);
    }

Next one will be using linked list, We first define the head, tail and internal linked list.

class SSEStackLinkedList{

    private SSELinkedListInternal head;
    private SSELinkedListInternal tail;


    private class SSELinkedListInternal{
        private int val;
        private SSELinkedListInternal next;
        public SSELinkedListInternal(int val){
            this.val = val;
            this.next = null;
        }
    }

    public SSEQueueLinkedList(){
    }
}

Then we define the put function which is O(1) because it just assign in the head:

    public void put(int toBeAdded){
        SSELinkedListInternal sseLinkedListInternal = new SSELinkedListInternal(toBeAdded);
        if (head == null){
            head = sseLinkedListInternal;
            tail = sseLinkedListInternal;
        }else {
            SSELinkedListInternal sseLinkedListInternalTemp = head;
            head = sseLinkedListInternal;
            head.next = sseLinkedListInternalTemp;
        }
    }

Then we define the pop function which internally use remove function which is O(1) because it just remove from head:

     public int pop() throws Exception {
        if (head == null)
            throw new Exception("nothing in the stack");

        int toBeReturned = head.val;

        if (head.next != null) {
            head = head.next;
        } else {
            head = null;
        }

        return toBeReturned;
    }

Note: This implementation is naive and simple, haven't been thoroughly tested, please do not use in production, it is meant for simple explanation only. And also there can be better implementation.

You can try to run the code here:

Run on jdoodle