Table of Contents:

1. Introduction
2. Operations in Stack
3. Implementation using Java
4. Applications

Introduction

A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is named "stack" because it resembles a real-life stack of objects, such as a stack of plates or a stack of books. In a stack, new elements are added or removed from the top, which is the only position that is accessible for insertion or deletion.

The key characteristic of a stack is that the most recently added element is the first one to be removed. Think of it as a pile of items where you can only access or manipulate the item on the top. New elements are always placed on top of the stack, and when an element is removed, the next element below it becomes the new top.

The stack data structure is an abstract data type that provides a simple and efficient way to manage data. It is commonly used inprogramming languages, algorithms, and various applications.

Operations in Stack

The primary operations supported by a stack are:

Stacks can be implemented using various data structures such as arrays, linked lists, or dynamic arrays. The choice of implementation depends on the specific requirements and constraints of the application.

Implementation

In this article at OpenGenus, we will explore how to implement a stack using array in Java using OOP concepts and Generics.

1. To implement a stack and its methods, we create a class named Stack.

import java.util.ArrayList;

public class Stack<T> {
    private ArrayList<T> arr; //Creating arr to reference the stack internally
    private int count; //used count to keep track of values moving in and moving out.
    private int stackSize; //used to keep the stack size

Constructor of class Stack

public Stack(int stackSize){ //constructor used to create an object of stack.
        this.stackSize = stackSize; //passed the size of the stack we want.
         this.arr = new ArrayList<>(stackSize); //initialized the stack array.
        this.count = -1; //initialized the count to -1.
    }

2. We define the methods like push, pop, isFull, isEmpty and isFull.
   2.1 Push: This operation adds an element to the top of the stack. The element is inserted at the end of the stack, and the stack pointer is incremented.

When the push operation is performed, the following steps take place:

1. The element to be added is stored in a variable (element).
2. The stack pointer is incremented. The stack pointer is a variable that keeps track of the index of the top element in the stack. When the stack pointer is incremented, it points to the next available element in the stack.
3. The element that was stored in the variable is placed at the index pointed to by the stack pointer. This element is now the top element of the stack.

public void push(T element){
        if(this.count+1<stackSize){ //checking that the no. of elements in stack are not more than the stack size.
            arr.add(++this.count,element); //increasing the count before the element is inserted. 
        }
        else //Executed if the above check fails.
        System.out.println("The Stack has reached the limit.");
    }

2.2 Pop: This operation removes the top element from the stack. The element is removed from the end of the stack, and the stack pointer is decremented.

When the pop operation is performed, the following steps take place:

1. The stack pointer is decremented. The stack pointer is a variable that keeps track of the index of the top element in the stack. When the stack pointer is decremented, it points to the element below the top element.
2. The element at the index pointed to by the stack pointer is removed from the stack. This element is the top element of the stack.
3. The value of the element that was removed is returned. This value can be used by the calling code.

public T pop(){
        if(this.count>=0) { //Checking if the stack is storing any values.
            T returnValue = arr.get(this.count); //Getting the value from the stack.
            this.count--; //Reducing the the count to make the below element as the new top element. 
            return returnValue;
        }
        else{ //If the above condition fails we return null.
            System.out.println("The Stack is Empty!");
            return null;
        }
    }

2.3 Peek/Top: The top of a stack is the element that was inserted most recently. It is the element that will be removed first when the stack is popped. The top of the stack is also known as the stack pointer.

The stack pointer is a variable that points to the top of the stack. When an element is pushed onto a stack, the stack pointer is incremented. When an element is popped from a stack, the stack pointer is decremented.

public T top(){
      if(this.count<0){ //Checking if there's any element in the stack
          System.out.println("The Stack is Empty!");
          return null; //Returning null, if the stack is empty.
      }
      return this.arr.get(this.count); //Returning the top of the stack if the above condition fails (Stack not empty.)
  }

2.4 isEmpty: This operation checks if the stack is empty. If the stack is empty, the function returns true. Otherwise, the function returns false.

This code first checks the length of the stack. If the length of the stack is less than 0, then the stack is empty and the function returns True. Otherwise, the stack is not empty and the function returns False.

public boolean isEmpty(){
        if(this.count<0){ //if the count is less than zero, meaning the stack is empty.
            return true; //returns true.
        }
        return false; //returns false as the stack is not empty.
    }

2.5 isFull: This operation checks if the stack is full. If the stack is full, the function returns true. Otherwise, the function returns false.

This code first checks the length of the stack. If the length of the stack is less than stackSize, then the stack has space to accomadate more elements and the function returns False. Otherwise, if the stackSize is equal to the count+1, the function returns True.

public boolean isFull(){
        if(this.count+1==stackSize){ //Checking if the number of elements in the stack is equal to the number of elements a stack can store.
            return true; //returned true.
        }
        return false; //returned false if the above condition fails.
    }

3. We implement the methods created in the class Stack.

public static void main(String[] args) {

       Stack<Integer> obj = new Stack<>(5); //We created a stack of Integers having length of 5.
        obj.push(1); //Entering the elements.
        obj.push(2);
        obj.push(3);
        obj.push(4);
        obj.push(5);
        
        System.out.println(obj.top()); //Prints 5
        
        obj.push(6); //Prints (The Stack has reached the limit.)
        
        System.out.println(obj.isFull()); //Checking if the satck is full. (true)

        System.out.println(obj.pop()); //Prints 5
        System.out.println(obj.pop()); //Prints 4
        System.out.println(obj.pop()); //Prints 3
        System.out.println(obj.pop()); //Prints 2
        System.out.println(obj.pop()); //Prints 1
        System.out.println(obj.pop()); //Prints null as the Stack is empty.

        System.out.println(obj.isEmpty()); //Checking if the stack is empty. (true)

    }
}

Please note: Additional dailouges like "The Stack has reached the limit." and "The Stack is Empty!" are implemented for clear understanding.

OUTPUT:

Applications

Stacks have numerous applications in computer science, including but not limited to:

• Function call stack: Used by programming languages to manage function calls and returns.
• Expression evaluation: Stacks can be used to evaluate arithmetic expressions, infix to postfix conversion, etc.
• Undo/Redo functionality: Stacks can be employed to implement undo and redo operations.
• Backtracking algorithms: Stacks can help facilitate backtracking in algorithms like depth-first search.

Code:

import java.util.ArrayList;

public class Stack < T > {
  private ArrayList < T > arr;
  private int count;
  private int stackSize;

  public Stack(int stackSize) {
    this.stackSize = stackSize;
    this.arr = new ArrayList < > (stackSize);
    this.count = -1;
  }

  public void push(T element) {
    if (this.count + 1 < stackSize) {
      arr.add(++this.count, element);
    } else
      System.out.println("The Stack has reached the limit.");
  }

  public T pop() {
    if (this.count >= 0) {
      T returnValue = arr.get(this.count);
      this.count--;
      return returnValue;
    } else {
      System.out.println("The Stack is Empty!");
      return null;
    }
  }

  public T top() {
    if (this.count < 0) {
      System.out.println("The Stack is Empty!");
      return null;
    }
    return this.arr.get(this.count);
  }
  public boolean isEmpty() {
    if (this.count < 0) {
      return true;
    }
    return false;
  }

  public boolean isFull() {
    if (this.count + 1 == stackSize) {
      return true;
    }
    return false;
  }

  public static void main(String[] args) {

    Stack < Integer > obj = new Stack < > (5); //We created a stack of size 5.
    obj.push(1); //Entering the elements.
    obj.push(2);
    obj.push(3);
    obj.push(4);
    obj.push(5);

    System.out.println(obj.top()); //Prints 5

    obj.push(6); //Prints (The Stack has reached the limit.)

    System.out.println(obj.isFull()); //Checking if the satck is full. (true)

    System.out.println(obj.pop()); //Prints 5
    System.out.println(obj.pop()); //Prints 4
    System.out.println(obj.pop()); //Prints 3
    System.out.println(obj.pop()); //Prints 2
    System.out.println(obj.pop()); //Prints 1
    System.out.println(obj.pop()); //Prints Integer.MIN_VALUE as the Stack is empty.

    System.out.println(obj.isEmpty()); //Checking if the stack is empty. (true)

  }
}