Day 8: Stacks

Stacks are a fundamental data structure used extensively in programming and algorithm design. They follow a Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. In this post, we’ll define stacks, explore their applications, implement them in Java, and solve example problems, including balancing parentheses.

Definition of Stacks

A stack is a collection of elements with two primary operations:

• Push: Add an element to the top of the stack.
• Pop: Remove and return the element from the top of the stack.

Stacks are often visualized as a vertical collection, where you can only access the top element, similar to a stack of plates.

Applications of Stacks

Stacks have a wide range of applications, including:

1. Function Call Management: Keeping track of function calls in programming languages through call stacks.
2. Expression Evaluation: Evaluating postfix and infix expressions using stacks.
3. Backtracking Algorithms: Implementing algorithms that require exploring multiple paths, such as maze solving.
4. Undo Mechanisms: Storing previous states in applications to allow users to undo actions.

Implementation in Java

Here’s a simple implementation of a stack using an array:

javaCopy codeclass Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // Stack is initially empty
    }

    public void push(int value) {
        if (top >= maxSize - 1) {
            System.out.println("Stack is full. Cannot push " + value);
            return;
        }
        stackArray[++top] = value;
    }

    public int pop() {
        if (top < 0) {
            System.out.println("Stack is empty. Cannot pop.");
            return -1; // Indicate empty stack
        }
        return stackArray[top--];
    }

    public int peek() {
        if (top < 0) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stackArray[top];
    }

    public boolean isEmpty() {
        return (top < 0);
    }
}

Example Problem: Balancing Parentheses

One classic problem that can be solved using stacks is checking whether the parentheses in an expression are balanced. This is done by using a stack to keep track of opening parentheses and ensuring that each closing parenthesis matches the last opened one.

Implementation in Java

javaCopy codeimport java.util.Stack;

public class ParenthesesChecker {
    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 (!isMatchingPair(top, ch)) return false;
            }
        }
        return stack.isEmpty();
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') ||
               (opening == '{' && closing == '}') ||
               (opening == '[' && closing == ']');
    }

    public static void main(String[] args) {
        String expression = "{[()]}";
        boolean result = isBalanced(expression);
        System.out.println("The expression is balanced: " + result); // Output: true
    }
}

Conclusion

Stacks are an essential data structure that supports various applications in programming. Understanding how to implement and use stacks effectively will enhance your problem-solving skills.

In our next post, we will delve into Queues, another fundamental data structure, and explore their operations and applications. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB