Stack data structure In Java

A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is an abstract data type that represents a collection of elements with two primary operations: push and pop.

A stack can be imagined as a vertical stack of objects, where elements are added or removed from the top of the stack. The topmost element is the one that was added most recently, and it is the first one to be removed.

Here are the key operations associated with a stack:

1. Push: This operation adds an element to the top of the stack. The newly added element becomes the top element of the stack.

2. Pop: This operation removes the topmost element from the stack. After the removal, the element below it becomes the new top element.

3. Peek (or Top): This operation returns the topmost element of the stack without removing it.

4. isEmpty: This operation checks if the stack is empty or not. It returns true if the stack contains no elements, and false otherwise.

Stacks are widely used in various computer science applications, including expression evaluation, function call management (using the call stack), undo/redo operations, backtracking algorithms, and more. They provide an efficient way to store and retrieve elements based on the LIFO principle.

Stacks can be implemented using various data structures, such as arrays or linked lists. The choice of implementation affects the efficiency of stack operations.

Here's an explanation of stack using an array:

• An array-based stack maintains an array to store the elements, along with a variable to keep track of the top element's index.

• When an element is pushed, it is added to the array at the index indicated by the top variable. The top is then incremented.

• When an element is popped, the topmost element is removed from the array, and the top is decremented.

• The peek operation simply returns the element at the top index without modifying the stack.

• The isEmpty operation checks if the top is -1, indicating an empty stack.

Here's an explanation of the stack using nodes:

Certainly! When implementing a stack using nodes, you can create a stack as a linked list data structure. Each node represents an element in the stack and contains two components: the data and a reference (or pointer) to the next node in the stack.

Using a linked list implementation, the stack operations have the following characteristics:

• Push and pop operations have a time complexity of O(1), as they involve updating the references of the top node.

• Peek operation also has a time complexity of O(1), as it only requires accessing the data in the top node.

• Checking if the stack is empty can be done in O(1) time by examining the top reference.

By using nodes to implement a stack, you can dynamically manage the elements in the stack without any fixed size restrictions. This makes it more flexible compared to an array-based implementation.

Here's the code for the stack using nodes in java:

public class Node<T> {
    private T data;
    private Node<T> next;    
    public Node() {
    }    
    public Node(T data) {
        this.data = data;
        this.next=null;
    }    
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }    
}

public class Stack<T> {
    private Node<T> top;
    public void push(T data) {
        Node<T> node = new Node<>();
        node.setData(data);
        if (top == null) {
            top = node;
            top.setNext(null);
        } else {
            node.setNext(top);
            top = node;
        }
    }
    public boolean pop() {
        if (top != null) {
            top = top.getNext();
            return true;
        } else
            return false;
    }
    public T peek() {
        return top != null ? top.getData() : null;
    }
    public boolean isEmpty() {
        return top == null ? true : false;
    }
    @Override
    public String toString() {
        StringBuilder output = new StringBuilder();
        Node n = top;
        output.append('[');
        while (n != null && n.getNext() != null) {
            output.append(n.getData()).append(',');
            n = n.getNext();
        }
        if (n != null)
            output.append(n.getData()).append(']');
        else
            output.append(']');

        return output.toString();
    }
}

public class StackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        int i = 1;        
        //insert data
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);
        stack.push(i++);

        System.out.println(stack.toString());
        System.out.println(stack.peek());

        stack.pop();
        stack.pop();        
        System.out.println(stack.toString());
        System.out.println(stack.peek());        
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.toString());
        System.out.println(stack.peek());    
        System.out.println(stack.isEmpty());
        stack.pop();
        System.out.println(stack.toString());
        System.out.println(stack.peek());    
        System.out.println(stack.isEmpty());        
    }
}

Output: