Tech Jargon - Decoded

Balanced Parentheses Checker using Stack

import java.util.Stack;

public class BalancedParentheses {

    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String expression1 = "{([])}";
        String expression2 = "([)]";
        System.out.println(expression1 + " is balanced: " + isBalanced(expression1));
        System.out.println(expression2 + " is balanced: " + isBalanced(expression2));
    }
}

Stack Implementation using LinkedList

import java.util.LinkedList;

public class StackUsingLinkedList {

    private LinkedList<Integer> stackList;

    public StackUsingLinkedList() {
        stackList = new LinkedList<>();
    }

    public void push(int data) {
        stackList.addFirst(data);
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stackList.removeFirst();
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stackList.getFirst();
    }

    public boolean isEmpty() {
        return stackList.isEmpty();
    }

    public int size() {
        return stackList.size();
    }

    public static void main(String[] args) {
        StackUsingLinkedList stack = new StackUsingLinkedList();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped: " + stack.pop());
        System.out.println("Top element after pop: " + stack.peek());
        System.out.println("Stack size: " + stack.size());
    }
}

Stack Implementation using Array

public class StackArray {
    private int[] arr;
    private int top;
    private int capacity;

    public StackArray(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    public void push(int data) {
        if (isFull()) {
            System.out.println("Stack Overflow");
            return;
        }
        arr[++top] = data;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return -1; 
        }
        return arr[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is Empty");
            return -1; 
        }
        return arr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public static void main(String[] args) {
        StackArray stack = new StackArray(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }
}

Java Program Execution Flow

(Queue):** Useful when you need to process items in the order they arrived, like serving customers or handling requests. **6. Solving Problems with Stacks and Queues ✅** - **Problem:** Reverse a string. - **Solution:** Use a Stack. Push each character onto the stack, then pop them off one by one to get the reversed string. - **Problem:** Process tasks in the order they were submitted. - **Solution:** Use a Queue. Enqueue each task as it arrives, and dequeue them to process them in the correct order. **7. Tips and Best Practices 💡** - Choose the correct data structure based on the problem's requirements (LIFO or FIFO). - Use the appropriate Java classes (`Stack`, `LinkedList`, `ArrayDeque`). - Always check for empty stacks/queues before attempting to `pop()` or `dequeue()` to avoid errors. ⚠️ **In a nutshell:** Stacks and Queues are your essential tools for managing data in a specific order, enabling you to solve a variety of real-world and coding problems efficiently. Keep practicing, and you'll become a master of data structures! 🎉

Hey there, future Java wizards! 👋 Let's dive into the world of Stacks and Queues – two fundamental data structures that are super helpful in solving many programming problems. We'll make it easy to understand and see how they're used in real life! **1. What are Stacks and Queues? 🤔** Think of Stacks and Queues as special containers for storing data. The key difference lies in how you add and remove items from them. - **Stack:** Imagine a stack of pancakes 🥞. You add new pancakes to the top, and when you want to eat one, you take it from the top as well. This is called **LIFO (Last-In, First-Out)**. The last pancake you put on is the first one you eat! - **Queue:** Think of a queue (or line) at a grocery store 🛒. People join the back of the line and are served from the front. This is called **FIFO (First-In, First-Out)**. The first person in line is the first one served! **2. Stacks in Detail (LIFO)** A Stack follows the LIFO principle. Think of it as a vertical tower of items. - **Key Operations:** - `push(item)`: Adds an item to the top of the stack. Imagine adding a pancake to the top of the stack. - `pop()`: Removes and returns the item from the top of the stack. You're taking the top pancake to eat. - `peek()`: Returns the item at the top of the stack without removing it. You're just looking at the top pancake. - `isEmpty()`: Checks if the stack is empty. Is there any pancake left? - **Implementation:** In Java, you can implement a stack using the `Stack` class or an `ArrayDeque`. - **Real-world use cases:** - Undo/Redo functionality: Editor, Drawing tools. - Browser history: Back button. - Expression evaluation: Compilers use stacks to process mathematical expressions. **3. Queues in Detail (FIFO)** A Queue follows the FIFO principle. It's like a line where the first one to enter is the first to exit. - **Key Operations:** - `enqueue(item)` (or `add(item)`): Adds an item to the back of the queue. Someone joining the back of the grocery line. - `dequeue()` (or `remove()`): Removes and returns the item from the front of the queue. Serving the person at the front. - `peek()`: Returns the item at the front of the queue without removing it. Checking who's next in line. - `isEmpty()`: Checks if the queue is empty. Is anyone in the queue? - **Implementation:** In Java, you can implement a queue using the `Queue` interface with classes like `LinkedList` or `ArrayDeque`. `LinkedList` is commonly used. - **Real-world use cases:** - Task scheduling: Operating systems use queues to manage tasks. - Print queues: Documents are printed in the order they are received. - Message queues: Handling asynchronous communication between systems. **4. Implementing Stacks and Queues in Java 💻** Let's see some simple Java examples:

// Stack Example
import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> myStack = new Stack<>();
        myStack.push("First");
        myStack.push("Second");
        myStack.push("Third");

        System.out.println(myStack.pop()); // Output: Third
        System.out.println(myStack.peek()); // Output: Second
    }
}

// Queue Example
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> myQueue = new LinkedList<>();
        myQueue.add("First");
        myQueue.add("Second");
        myQueue.add("Third");

        System.out.println(myQueue.remove()); // Output: First
        System.out.println(myQueue.peek());  // Output: Second
    }
}

**5. Applying LIFO/FIFO Logic 🧠** The power of stacks and queues comes from their specific order of operation. - **LIFO (Stack):** Useful when you need to reverse the order of items or keep track of a series of operations to undo them. - **FIFO

Detect and Remove Loop in a Singly Linked List

class LinkedList {
 static class Node {
 int data;
 Node next;
 Node(int d) { data = d; next = null; }
 }
 Node head;
 public void detectAndRemoveLoop() {
 Node slow = head, fast = head;
 while (fast != null && fast.next != null) {
 slow = slow.next;
 fast = fast.next.next;
 if (slow == fast) {
 removeLoop(slow);
 return;
 }
 }
 }
 void removeLoop(Node loopNode) {
 Node ptr1 = head, ptr2 = loopNode;
 while (ptr1.next != ptr2.next) {
 ptr1 = ptr1.next;
 ptr2 = ptr2.next;
 }
 ptr2.next = null;
 }
 public void push(int new_data) {
 Node new_node = new Node(new_data);
 new_node.next = head;
 head = new_node;
 }
 public void printList() {
 Node tnode = head;
 while (tnode != null) {
 System.out.print(tnode.data + " ");
 tnode = tnode.next;
 }
 }
 public static void main(String[] args) {
 LinkedList list = new LinkedList();
 list.push(20); list.push(4); list.push(15); list.push(10);
 list.head.next.next.next.next = list.head.next;
 list.detectAndRemoveLoop();
 System.out.println("Linked List after removing loop : ");
 list.printList();
 }
}

Find Intersection Point of Two Linked Lists

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListIntersection {

    public Node getIntersectionNode(Node headA, Node headB) {
        if (headA == null || headB == null) return null;

        Node a = headA;
        Node b = headB;

        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }

    public static void main(String[] args) {
        Node headA = new Node(4);
        headA.next = new Node(1);
        Node intersection = new Node(8);
        headA.next.next = intersection;
        intersection.next = new Node(4);
        intersection.next.next = new Node(5);

        Node headB = new Node(5);
        headB.next = new Node(6);
        headB.next.next = new Node(1);
        headB.next.next.next = intersection;

        LinkedListIntersection sol = new LinkedListIntersection();
        Node intersectionNode = sol.getIntersectionNode(headA, headB);

        if (intersectionNode != null) {
            System.out.println("Intersection Node: " + intersectionNode.data);
        } else {
            System.out.println("No Intersection");
        }
    }
}

Delete a Node in a Singly Linked List (Without Head Reference)

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class DeleteNodeWithoutHead {

    public static void deleteNode(Node node) {
        if (node == null || node.next == null) {
            node = null; 
            return;
        }

        node.data = node.next.data;
        node.next = node.next.next;
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        Node nodeToDelete = head.next;
        head.next.next = new Node(30);

        deleteNode(nodeToDelete);

        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }
}

Reverse a Doubly Linked List

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    Node head;

    public void push(int new_data) {
        Node new_Node = new Node(new_data);

        new_Node.next = head;
        new_Node.prev = null;

        if (head != null) {
            head.prev = new_Node;
        }

        head = new_Node;
    }

    public void reverse() {
        Node temp = null;
        Node current = head;

        while (current != null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }

        if (temp != null) {
            head = temp.prev;
        }
    }

    public void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.push(2);
        dll.push(4);
        dll.push(8);
        dll.push(10);

        System.out.println("Original list:");
        dll.printList();

        dll.reverse();

        System.out.println("Reversed list:");
        dll.printList();
    }
}

Doubly Linked List with Insert and Delete

public class DoublyLinkedList {
    class Node {
        int data;
        Node prev;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    Node head;
    Node tail;

    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }

    public void delete(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                if (current == head) {
                    head = current.next;
                    if (head != null) {
                        head.prev = null;
                    }
                } else if (current == tail) {
                    tail = current.prev;
                    tail.next = null;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insert(10);
        dll.insert(20);
        dll.insert(30);
        dll.printList();
        dll.delete(20);
        dll.printList();
    }
}

Palindrome Linked List Checker

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class PalindromeLinkedList {

    Node head;\    boolean isPalindrome(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        Node secondHalfHead = reverseList(slow);
        Node firstHalfHead = head;

        while (secondHalfHead != null) {
            if (firstHalfHead.data != secondHalfHead.data) {
                return false;
            }
            firstHalfHead = firstHalfHead.next;
            secondHalfHead = secondHalfHead.next;
        }

        return true;
    }

    Node reverseList(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        PalindromeLinkedList list = new PalindromeLinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(2);
        list.head.next.next.next = new Node(1);

        boolean isPal = list.isPalindrome(list.head);
        System.out.println("Is Palindrome: " + isPal);
    }
}

Remove Duplicates from Sorted Singly Linked List

public class RemoveDuplicates {

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public static Node removeDuplicates(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node current = head;

        while (current.next != null) {
            if (current.data == current.next.data) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(1);
        head.next.next = new Node(2);
        head.next.next.next = new Node(3);
        head.next.next.next.next = new Node(3);

        Node newHead = removeDuplicates(head);

        Node temp = newHead;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

Find the nth Node from the End of a Singly Linked List

public class NthNodeFromEnd {

    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; next = null; }
    }

    Node head;

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    int getNthFromLast(int n) {
        if (head == null) return -1;

        Node slow = head, fast = head;

        for (int i = 0; i < n; i++) {
            if (fast == null) return -1; 
            fast = fast.next;
        }

        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow.data;
    }

    public static void main(String[] args) {
        NthNodeFromEnd list = new NthNodeFromEnd();
        list.push(20);
        list.push(4);
        list.push(15);
        list.push(35);

        System.out.println("Nth node from end is " + list.getNthFromLast(4));
    }
}

Find Middle Node of a Singly Linked List

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public Node findMiddleNode() {
        if (head == null) {
            return null;
        }

        Node slow_ptr = head;
        Node fast_ptr = head;

        while (fast_ptr != null && fast_ptr.next != null) {
            slow_ptr = slow_ptr.next;
            fast_ptr = fast_ptr.next.next;
        }
        return slow_ptr;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.push(6);
        list.push(5);
        list.push(4);
        list.push(3);
        list.push(2);
        list.push(1);

        Node middle = list.findMiddleNode();
        if (middle != null) {
            System.out.println("Middle element is: " + middle.data);
        } else {
            System.out.println("List is empty");
        }
    }
}

Merge Two Sorted Linked Lists

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeSortedLists {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        tail.next = (list1 != null) ? list1 : list2;

        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        MergeSortedLists merger = new MergeSortedLists();
        ListNode mergedList = merger.mergeTwoLists(list1, list2);

        while (mergedList != null) {
            System.out.print(mergedList.val + " ");
            mergedList = mergedList.next;
        }
    }
}

Detect Cycle in Singly Linked List using Floyd's Algorithm

class LinkedList {
    Node head;

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public boolean detectLoop() {
        Node slow_ptr = head, fast_ptr = head;
        while (slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
            slow_ptr = slow_ptr.next;
            fast_ptr = fast_ptr.next.next;
            if (slow_ptr == fast_ptr) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);

        llist.head.next.next.next.next = llist.head;

        if (llist.detectLoop())
            System.out.println("Loop found");
        else
            System.out.println("No Loop");
    }
}

Reverse Linked List

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void reverseIterative() {
        Node prev = null;
        Node current = head;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    public void reverseRecursive() {
        head = reverseRecursiveHelper(head, null);
    }

    private Node reverseRecursiveHelper(Node current, Node prev) {
        if (current == null) {
            return prev;
        }
        Node next = current.next;
        current.next = prev;
        return reverseRecursiveHelper(next, current);
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.print("Original List: ");
        list.printList();

        list.reverseIterative();
        System.out.print("Reversed (Iterative): ");
        list.printList();

        list.reverseRecursive();
        System.out.print("Reversed (Recursive): ");
        list.printList();
    }
}

Singly Linked List: Insert and Delete

public class SinglyLinkedList {

    Node head;

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void insertAfter(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("Previous node cannot be null");
            return;
        }
        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }

    public void deleteNode(int key) {
        Node current = head, prev = null;

        if (current != null && current.data == key) {
            head = current.next;
            return;
        }

        while (current != null && current.data != key) {
            prev = current;
            current = current.next;
        }

        if (current == null) return;

        prev.next = current.next;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.insertAtEnd(6);
        list.insertAtBeginning(7);
        list.insertAtEnd(4);
        list.insertAfter(list.head.next, 8);

        System.out.println("Created Linked list is:");
        list.printList();

        list.deleteNode(7);

        System.out.println("
Linked List after Deletion of 7:");
        list.printList();
    }
}

Create and Traverse Singly Linked List

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void traverse() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(10);
        list.add(20);
        list.add(30);

        System.out.print("Linked List: ");
        list.traverse();
    }
}