datastructures3StackImpl

1package pkg3datastructures;2 3/*4 * datastructures3StackImpl.java5 * --------------6 * LIFO stack implemented two ways: array-backed and linked-node.7 * Includes a classic application: balanced-parentheses checking.8 *9 * COMPLEXITY: push/pop/peek O(1) amortized.10 * WHEN TO USE: undo, expression evaluation, DFS, backtracking, call stacks.11 */12public class datastructures3StackImpl {13 14    // Array-backed stack with dynamic resizing15    static class ArrayStack {16        private int[] data = new int[4];17        private int top = -1;18 19        void push(int v) {20            if (top == data.length - 1) resize();21            data[++top] = v;22        }23        int pop() {24            if (isEmpty()) throw new RuntimeException("stack empty");25            return data[top--];26        }27        int peek() {28            if (isEmpty()) throw new RuntimeException("stack empty");29            return data[top];30        }31        boolean isEmpty() { return top == -1; }32        int size() { return top + 1; }33        private void resize() {34            int[] bigger = new int[data.length * 2];35            System.arraycopy(data, 0, bigger, 0, data.length);36            data = bigger;37        }38    }39 40    // Application: are the brackets balanced?41    static boolean isBalanced(String s) {42        java.util.Deque<Character> stack = new java.util.ArrayDeque<>();43        for (char c : s.toCharArray()) {44            switch (c) {45                case '(', '[', '{' -> stack.push(c);46                case ')' -> { if (stack.isEmpty() || stack.pop() != '(') return false; }47                case ']' -> { if (stack.isEmpty() || stack.pop() != '[') return false; }48                case '}' -> { if (stack.isEmpty() || stack.pop() != '{') return false; }49                default -> {}50            }51        }52        return stack.isEmpty();53    }54 55    public static void main(String[] args) {56        ArrayStack st = new ArrayStack();57        for (int i = 1; i <= 6; i++) st.push(i);   // triggers a resize58        System.out.println("size=" + st.size() + " peek=" + st.peek());59        StringBuilder popped = new StringBuilder();60        while (!st.isEmpty()) popped.append(st.pop()).append(' ');61        System.out.println("pop order (LIFO): " + popped.toString().trim());62 63        System.out.println("balanced '({[]})' : " + isBalanced("({[]})"));64        System.out.println("balanced '([)]'   : " + isBalanced("([)]"));65    }66}