Monday 8 April 2024

Implementing a Stack Data Structure in Java Using ArrayList

 

A stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates where you can only add or remove the top plate. Similarly, in a stack data structure, elements are added and removed from the top, allowing for efficient last-in, first-out access.

 

Key operations of Stack

a.   Push Operation: The push operation adds an element to the top of the stack. When you push an element onto a stack, it becomes the new top element.

b.   Pop Operation: The pop operation removes the top element from the stack. It returns the removed element and updates the stack's top pointer to the next element.

c.    Size Operation: The size operation returns the number of elements currently present in the stack.


 

Use Cases of Stack

Stacks is used in various areas of computer science and software development:

 

1.   Function Call Stack: In programming languages like Java, C++, and Python, a function call stack is used to manage function calls and local variables.

2.   Expression Evaluation: Stacks are commonly used to evaluate arithmetic expressions, postfix, and infix expressions.

3.   Undo Mechanisms: Many applications use stacks to implement undo functionality, where each operation performed is pushed onto the stack, allowing users to undo their actions in reverse order.

4.   Browser History: Web browsers use a stack to store the history of visited web pages, enabling users to navigate back and forth.

5.   Backtracking Algorithms: Stack-based backtracking algorithms are used to solve problems such as maze traversal, graph traversal, and puzzle solving.

 

Implementing a Stack using ArrayList in Java:

Below is a simple implementation of a stack data structure using the ArrayList class in Java:

 

ArrayStack.java 

package com.sample.app.util;

import java.util.ArrayList;

public class ArrayStack<T> {

	private final ArrayList<T> stack;

	public ArrayStack() {
		stack = new ArrayList<>();
	}

	public ArrayStack(int initSize) {
		stack = new ArrayList<T>(initSize);
	}

	public void push(T obj) {
		stack.add(obj);
	}

	public T pop() {
		if (isEmpty()) {
			throw new IllegalStateException("Stack is empty");
		}
		return stack.remove(stack.size() - 1);
	}

	public boolean isEmpty() {
		return stack.isEmpty();
	}

	public int size() {
		return stack.size();
	}

	public void clear() {
		stack.clear();
	}

	public void print() {
		System.out.println("\nElements in the stack are");
		for (int i = stack.size() - 1; i >= 0; i--) {
			System.out.println(stack.get(i));
		}
	}

}

 

ArrayStackDemo.java

package com.sample.app;

import com.sample.app.util.ArrayStack;

public class ArrayStackDemo {
	
	public static void main(String[] args) {
		ArrayStack<Integer> stack = new ArrayStack<> ();
		
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);
		
		stack.print();
		
		System.out.println("\nPop two elements from stack");
		
		stack.pop();
		stack.pop();
		
		stack.print();
		
		System.out.println("\nAdd an element 6 to the stack");
		stack.push(6);
		stack.print();
		
	}

}

 

Output

Elements in the stack are
5
4
3
2
1

Pop two elements from stack

Elements in the stack are
3
2
1

Add an element 6 to the stack

Elements in the stack are
6
3
2
1

 

You may like


No comments:

Post a Comment