The Stack Data Structure

Definition

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to a stack will be the first one removed. Imagine a stack of plates: you add new plates to the top, when you need on you take the top plate off first.

Basic Operations

1. Push: Add an element to the top of the stack.
2. Pop: Remove and return the element from the top of the stack.
3. Peek/Top: Return the top element without removing it.
4. isEmpty: Check if the stack is empty.
5. isFull: (Optional) Check if the stack is full (used in implementations with a fixed size).

Illustration

In the diagram below you can visualize the series of operations that occur when pushing and popping elements on and off a stack. It begins with an empty stack and then pushes three integers onto the stack and finally pops the last element off the stack.

Applications of Stacks

• Expression Evaluation: Stacks are used to evaluate expressions (e.g., postfix expressions) and convert expressions between different forms (infix to postfix/prefix).
• Backtracking: Stacks are used in algorithms like backtracking, where you need to remember the previous state.
• Function Call Management: The call stack in programming languages manages function calls and their local variables.

Advantages of Stacks

• Simple Structure: Stacks have a simple structure and are easy to implement.
• Memory Efficient: In linked list implementation, memory is used only when needed.

Disadvantages of Stacks

• Limited Access: You can only access the top element directly.
• Fixed Size (Array Implementation): If implemented with an array, the stack has a fixed size, which can be limiting.

Implementation In Java

Examclass Node {
    int data;
    Node next;

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

class Stack {
    private Node top;

    public Stack() {
        this.top = null;
    }

    // Push operation
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }

    // Pop operation
    public int pop() {
        if (top == null) {
            System.out.println("Stack is empty");
            return -1;
        }
        int poppedData = top.data;
        top = top.next;
        return poppedData;
    }

    // Peek operation
    public int peek() {
        if (top == null) {
            System.out.println("Stack is empty");
            return -1;
        }
        return top.data;
    }

    // Check if the stack is empty
    public boolean isEmpty() {
        return top == null;
    }
}

Example Usage

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

        System.out.println("Top element: " + stack.peek()); // Output: 30
        System.out.println("Popped element: " + stack.pop()); // Output: 30
        System.out.println("Popped element: " + stack.pop()); // Output: 20
        System.out.println("Is stack empty? " + stack.isEmpty()); // Output: false
    }
}

Conclusion

This covers the essential concepts behind the stack data structure, along with its advantages, disadvantages, and common uses. Take the time to thoroughly understand the implementation and try to utilize it in your own applications. Check out this article if you want to practice using a stack in a real example: