How to Implement a Stack in Java: A Step-by-Step Tutorial

📚 What is a Stack?

A stack is a fundamental data structure in computer science based on the Last-In, First-Out (LIFO) principle. Imagine a stack of plates; you can only add or remove plates from the top. This 'top' is where all actions occur in a stack.

📜 A Brief History of Stacks

The concept of stacks emerged early in computer science, closely tied to the development of programming languages and computer architecture. The idea of using a 'pushdown stack' for evaluating arithmetic expressions was proposed in the 1950s. Stacks are fundamental for managing function calls and memory allocation in modern computing.

🔑 Key Principles of Stacks

• ➕ Push: Adds an element to the top of the stack.
• ➖ Pop: Removes the element from the top of the stack.
• peek: Returns the element at the top of the stack without removing it.
• isEmpty: Checks if the stack is empty

💻 Implementing a Stack in Java: Step-by-Step

Java provides a built-in Stack class, but understanding how to implement one from scratch is crucial. Here's how you can do it using an array:

1. Create a Class: Define a class, for example, MyStack.
2. 🧱 Declare the Array: Declare an array to hold the stack elements. Also, declare an integer variable top to keep track of the index of the top element. Initialize top to -1, indicating an empty stack.
3. ➕ Implement the Push Method: This method adds an element to the top of the stack. First, increment top, then add the element at the top index.
4. ➖ Implement the Pop Method: This method removes and returns the element at the top of the stack. First, check if the stack is empty. If not, return the element at the top index and then decrement top.
5. Implement the Peek Method: This method returns the element at the top of the stack without removing it. Similar to pop, first check if the stack is empty. If not, return the element at the top index.
6. 🔎 Implement the isEmpty Method: This method returns true if the stack is empty (i.e., top is -1), and false otherwise.

✍️ Java Code Example

Here's the complete Java code for a stack implemented using an array:

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

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

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

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

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

    public int size() {
        return top + 1;
    }

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

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

    public static void main(String[] args) {
        MyStack stack = new MyStack(5);

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Top element is: " + stack.peek());
        System.out.println("Size of stack is : " + stack.size());
        System.out.println("Popped element is : " + stack.pop());
        System.out.println("Top element is: " + stack.peek());
        System.out.println("Size of stack is : " + stack.size());
    }
}

🏢 Real-world Examples of Stacks

• 🌐 Browser History: The back button on your browser uses a stack to keep track of the pages you've visited.
• ↩️ Undo/Redo Functionality: Many applications use stacks to implement undo/redo features.
• 🧮 Expression Evaluation: Compilers use stacks to evaluate arithmetic expressions.
• 📞 Function Calls: Stacks are used to manage function calls in programming languages.

📝 Practice Quiz

Test your knowledge with these questions:

1. What is the main principle behind the Stack data structure?
2. Explain the difference between the 'push' and 'pop' operations.
3. In the given Java code, what does the 'top' variable represent?
4. How would you check if the stack is empty in the provided Java implementation?

Conclusion

Stacks are a fundamental and versatile data structure with many applications in computer science. By understanding the LIFO principle and mastering the implementation of stack operations, you'll gain a valuable tool for solving a wide range of problems.