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
