Stack

What is a Stack?

A stack is a last-in-first-out (LIFO) data structure.

This means that the last element added to the stack is the first element removed.

Stacks are often used to implement function calls, backtracking algorithms, and undo/redo functionality.

How to Implement a Stack in Java

A stack can be implemented in Java using a variety of data structures, such as arrays, linked lists, and dynamic arrays. The simplest implementation is to use an array. To do this, we need to keep track of the top of the stack, which is the index of the next element to be added. When we add an element to the stack, we increment the top of the stack and add the element to the array at that index. When we remove an element from the stack, we decrement the top of the stack and return the element at that index.

Here is a simple implementation of a stack in Java:

public class Stack<T> {

    private int top;
    private T[] stack;

    public Stack() {
        this.top = -1;
        this.stack = (T[]) new Object[10];
    }

    public void push(T element) {
        if (top == stack.length - 1) {
            resize();
        }
        top++;
        stack[top] = element;
    }

    public T pop() {
        if (top == -1) {
            return null;
        }
        T element = stack[top];
        top--;
        return element;
    }

    public T peek() {
        if (top == -1) {
            return null;
        }
        return stack[top];
    }

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

    private void resize() {
        T[] newStack = (T[]) new Object[stack.length * 2];
        System.arraycopy(stack, 0, newStack, 0, stack.length);
        stack = newStack;
    }
}

Common Operations on Stacks

Here are some common operations that can be performed on stacks:

• push(): Adds an element to the top of the stack.
• pop(): Removes the element at the top of the stack and returns it.
• peek(): Returns the element at the top of the stack without removing it.
• isEmpty(): Returns True if the stack is empty, False otherwise.

Applications of Stacks

Stacks are used in a variety of applications, including:

• Function calls: When a function is called, its parameters are pushed onto a stack. When the function returns, its parameters are popped off the stack.
• Backtracking algorithms: Backtracking algorithms use stacks to keep track of the different states of the algorithm. This allows the algorithm to backtrack if it reaches a dead end.
• Undo/redo functionality: Undo/redo functionality in many software applications is implemented using stacks. When an action is performed, the state of the application is pushed onto a stack. To undo the action, the previous state of the application is popped off the stack and restored.

Using in-built Stack in Java

In Java, the Stack class is part of Java’s java.util package. Here is an example on how to use it.

import java.util.Stack;

public class StackDemo {

    public static void main(String[] args) {
        // Creating a Stack of integers
        Stack<Integer> stack = new Stack<>();

        // Pushing elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        System.out.println("Stack after pushes: " + stack);

        // Checking the top element without removing it
        System.out.println("Top element: " + stack.peek());

        // Popping (removing) elements from the stack
        stack.pop();
        System.out.println("Stack after first pop: " + stack);

        stack.pop();
        System.out.println("Stack after second pop: " + stack);

        // Checking if the stack is empty
        System.out.println("Is the stack empty? " + stack.isEmpty());

        // Searching for an element in the stack
        int position = stack.search(10);
        if (position != -1) {
            System.out.println("Element 10 is found at position: " + position);
        } else {
            System.out.println("Element 10 is not in the stack.");
        }
    }
}

Exercises for Practice

1. Balancing Symbols: Check if a given expression has balanced parentheses, curly braces, and square brackets.
2. Reverse a String: Use a stack to reverse the characters in a string.
3. Evaluate Postfix Expression: Given an expression in postfix notation (AB+), evaluate its result.

Conclusion

Stacks are a fundamental data structure in computer science. They are used in a variety of applications, including function calls, backtracking algorithms, and undo/redo functionality. Freshman computer science students should learn how to implement and use stacks in order to write efficient and robust code.