Implementing Generic Stack with Custom Backing (Array vs LinkedList)
Implementing Generic Stack with Custom Backing (Array vs LinkedList)
Introduction
जब हम Java में Stack implement करते हैं, तो हम चाहते हैं कि वो flexible और reusable हो। इसलिए हम Generic Stack बनाते हैं — ऐसा Stack जो किसी भी data type (जैसे Integer, String, Double आदि) को handle कर सके। Generic Stack की सबसे बड़ी खासियत ये होती है कि ये type safety provide करता है और हमें बार-बार अलग-अलग Stack classes नहीं बनानी पड़तीं।
अब बात आती है कि Stack को internally store कैसे करें — इसके लिए हमारे पास दो popular options होते हैं: Array और LinkedList। दोनों का performance, memory usage और behavior थोड़ा अलग होता है। इस blog में हम step-by-step समझेंगे कि कैसे एक Generic Stack को Array और LinkedList दोनों से implement किया जा सकता है।
What is Generic Stack?
Stack एक linear data structure होता है जो LIFO (Last In, First Out) principle पर काम करता है। यानी जो element सबसे बाद में आता है, वही सबसे पहले निकलता है।
जब हम Stack को Generic बनाते हैं, तो हम उसे किसी भी type के data के लिए usable बना देते हैं। उदाहरण के लिए:
Stack<Integer> intStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
इस approach से हमारा code reusable और efficient बनता है।
Core Stack Operations
किसी भी Stack में कुछ basic operations होते हैं:
- push(element) – Stack में नया element डालता है।
- pop() – Stack के top element को निकालता है।
- peek() – Top element को बिना निकाले देखता है।
- isEmpty() – चेक करता है कि Stack खाली है या नहीं।
- size() – Stack में कितने elements हैं, ये बताता है।
Implementing Generic Stack using Array
Array-backed Stack में हम internally एक Array का use करते हैं elements को store करने के लिए। ये implementation fast होती है क्योंकि indexing constant time में होती है।
Code Example: Generic Stack with Array
class GenericArrayStack<T> {
private Object[] data;
private int top;
private int capacity;
public GenericArrayStack(int size) {
data = new Object[size];
capacity = size;
top = -1;
}
public void push(T element) {
if (top == capacity - 1) {
throw new RuntimeException("Stack Overflow");
}
data[++top] = element;
}
@SuppressWarnings("unchecked")
public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack Underflow");
}
return (T) data[top--];
}
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is Empty");
}
return (T) data[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
Advantages of Array-backed Stack
- Fast access — indexing O(1) time में होती है।
- Simple implementation और memory layout predictable होता है।
Disadvantages of Array-backed Stack
- Fixed size – Stack overflow हो सकता है अगर space खत्म हो जाए।
- Resize करना manually handle करना पड़ता है।
Implementing Generic Stack using LinkedList
LinkedList-backed Stack में हर element एक node में store होता है, जो अगले node से link रहता है। इसका फायदा ये है कि हमें fixed size की limitation नहीं होती।
Code Example: Generic Stack with LinkedList
class GenericLinkedStack<T> {
private Node<T> top;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
public void push(T element) {
Node<T> newNode = new Node<>(element);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack Underflow");
}
T data = top.data;
top = top.next;
size--;
return data;
}
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is Empty");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
}
Advantages of LinkedList-backed Stack
- Dynamic size – elements add या remove होने पर memory auto adjust होती है।
- No overflow issue – जब तक memory है, elements add किए जा सकते हैं।
Disadvantages of LinkedList-backed Stack
- हर node में extra memory लगती है (data + next pointer)।
- Memory overhead थोड़ा ज़्यादा होता है Array की तुलना में।
Comparison Table: Array vs LinkedList Stack
| Feature | Array Stack | LinkedList Stack |
|---|---|---|
| Memory Usage | Fixed, कम overhead | Dynamic, extra pointer overhead |
| Performance | Fast access (O(1)) | O(1) insertion/deletion, लेकिन ज़्यादा memory |
| Flexibility | Fixed capacity | Dynamic size |
| Implementation Simplicity | Simple | Relatively complex |
| Use Case | जब size पहले से पता हो | जब size unpredictable हो |
Which Implementation Should You Use?
अगर आपको Stack का approximate size पहले से पता है और आप performance-critical environment में काम कर रहे हैं (जैसे game engine या embedded system), तो Array-based Stack बेहतर choice है।
लेकिन अगर आप dynamic data structure बना रहे हैं जहाँ elements कभी भी बढ़ या घट सकते हैं (जैसे parsing, recursion tracking, expression evaluation), वहाँ LinkedList-based Stack perfect रहेगा।
Real-life Example of Generic Stack
मान लीजिए आपको किसी expression को evaluate करना है, जैसे:
(5 + 3) * (2 - 1)
इसको evaluate करने के लिए compiler internally Stack use करता है ताकि वो operands और operators को manage कर सके।
Code Example
GenericArrayStack<Integer> numberStack = new GenericArrayStack<>(10);
numberStack.push(5);
numberStack.push(3);
int a = numberStack.pop(); // 3
int b = numberStack.pop(); // 5
System.out.println(a + b); // Output: 8
ऐसे ही Stack का use हर जगह होता है — चाहे वो recursion में हो, browser history में या undo-redo functionality में।
Notes for Exam
- Generic Stack किसी भी data type के लिए reusability provide करता है।
- Array-backed Stack fast होता है लेकिन size fixed होता है।
- LinkedList-backed Stack dynamic होता है लेकिन थोड़ा memory overhead देता है।
- LIFO principle हमेशा follow होता है।
- Stack operations के time complexities: push() O(1), pop() O(1), peek() O(1)
- LinkedList Stack overflow नहीं करता क्योंकि dynamic memory allocation होती है।
- Exam में implementation logic, code structure और differences पर focus करो।
- Stack का real use: Expression evaluation, Recursion, Syntax parsing, Function call stack।
- Generic Stack में type casting की जरूरत नहीं पड़ती (Type safety)।
Final Summary
तो अब आप समझ गए कि कैसे Generic Stack को Java में implement किया जा सकता है, चाहे वो Array के साथ हो या LinkedList के साथ। दोनों के अपने pros और cons हैं, लेकिन दोनों ही exam point of view से important हैं।
Practice के लिए आप खुद एक Generic Stack बनाकर experiment करें — push, pop, peek operations run करें और दोनों approaches की performance compare करें। ऐसा करने से concept crystal clear हो जाएगा।
