Stack & Queue

Stack is LIFO : Last in First Out

Queue is FIFO: First in First Out

Both of them are implemented the https://cankube.com/2020/02/16/linked-list/

Code example for Stack

public class Stack {
    private Node head;
    
    public boolean isEmpty() {
        return head == null;
    }
    
    public String peek(){
        return head.data;
    }
    
    public String pop() {
        if(head == null) throw new EmptyStackException();
        String data = head.data;
        head = head.next;
        return data;
    }
    
    private static class Node {
        String data;
        Node next;
        public Node(String data) {
            this.data = data;
        }
    }
    
}

Code example of Queue

public class Queue {
    private Node head;
    private Node tail;

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

    public String peek(){
        return head.data;
    }

    public void add(String data) {
        Node newNode = new Node(data);
        if (tail != null) {
            tail.next = newNode;
        }
        tail = newNode;
        if (head == null) {
            head = tail;
        }
    }

    public String remove() {
        String data = head.data;
        head = head.next;
        if(head == null) {
            tail = null;
        }
        return data;
    }

    private static class Node {
        String data;
        Node next;
        public Node(String data) {
            this.data = data;
        }
    }
}

Runtime Characteristics

• Access – O(n)
• Search – O(n)
• Insertion – O(1)
• Deletion – O(1)