Stack & Queue

Posted by

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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.