Stack (स्टैक)
Stack एक ऐसा Linear Data Structure है, जिसमें डेटा को एक विशेष क्रम (order) में रखा जाता है, जिसे कहते हैं LIFO — Last In First Out। इसका अर्थ है — जो Item सबसे Last में डाला जाता है (Inserted), वही सबसे पहले निकाला जाता है (Removed)। Stack में insertion (elements जोड़ना) और deletion (elements हटाना) दोनों काम केवल एक ही end से किए जाते हैं, जिसे Top of the Stack कहा जाता है।
उदाहरण :
Browser Back Button : आप जो पेज सबसे बाद में खोलते हैं, Back बटन दबाने पर वही सबसे पहले बंद होता है।
Stack as an ADT (ADT के रूप में Stack)
ADT (Abstract Data Type) का अर्थ है – Data Structure का ऐसा Logical मॉडल जो यह बताता है, कि डेटा पर कौन-कौन से Operations किए जा सकते हैं, लेकिन यह नहीं बताता कि उन्हें कैसे Implement किया जाएगा।
उदाहरण – आप एक TV खरीदने जाते हैं। आपको सिर्फ remote के buttons (जैसे Power, Volume, Channel) से मतलब होता है। TV के अंदर circuit कैसे काम कर रहा है, आपको उससे कोई लेना-देना नहीं होता।
Stack as an ADT भी वैसा ही है – यह सिर्फ कुछ set of operations define करता है, जैसे:
- push() : Stack में एक नया element add करना।
- pop() : Stack से सबसे top वाले element को हटाना।
- peek() या top() : Stack के सबसे ऊपर वाले element को देखना, बिना उसे हटाए।
- isEmpty() : Check करना कि Stack खाली है या नहीं।
- isFull() : Check करना कि Stack पूरा भरा हुआ है या नहीं।
Stack ADT की सबसे खास बात यह है कि, यह programmer को सिर्फ इन operations का access देता है। आप सीधे Stack के बीच में से कोई element नहीं निकाल सकते। आपको हमेशा top से ही काम करना होगा। यह एक तरह का discipline है जो Stack को Special बनाता है।
Different Implementations of Stack
Stack को दो प्रमुख तरीकों से Implement किया जा सकता है –
- Array Implementation (सरणी द्वारा)
- Linked List Implementation (लिंक्ड लिस्ट द्वारा)
1. Array-based Implementation
Array-based implementation सबसे सीधा और आसान तरीका है। इसमें हम एक fixed-size Array का इस्तेमाल करते हैं, और एक variable लेते हैं, जिसे top कहते हैं। यह top variable हमेशा Stack के सबसे ऊपर वाले element के index को point करता है।
Implementation Process
1. Initialization :
- हम एक Array बनाते हैं और top को -1 पर set करते हैं (जो बताता है कि Stack अभी खाली है)।
#define MAX 5
int stack[MAX];
int top = -1;
2. push() Operation :
- सबसे पहले, हम check करते हैं, कि Stack full तो नहीं है (isFull())। अगर top Array के last index पर पहुँच गया है, तो इसे Overflow condition कहते हैं।
- अगर Stack में space है, तो हम top को एक बढ़ा देते हैं (top++) और नए element को array[top] index पर store कर देते हैं।
void push(int item) {
if (top == MAX – 1)
printf(“Stack Overflow\n”);
else
stack[++top] = item;
}
3. pop() Operation :
- पहले, हम check करते हैं कि Stack खाली तो नहीं है (isEmpty())। अगर top -1 पर है, तो इसे Underflow condition कहते हैं।
- अगर Stack खाली नहीं है, तो हम array[top] पर मौजूद element को return करते हैं और top को एक घटा देते हैं (top–)।
void pop() {
if (top == -1)
printf(“Stack Underflow\n”);
else
printf(“Popped: %d\n”, stack[top–]);
}
4. peek() Operation :
- हम सिर्फ array[top] पर मौजूद element को return कर देते हैं, बिना top को change किए।
void peek() {
if (top == -1)
printf(“Stack is Empty\n”);
else
printf(“Top Element: %d\n”, stack[top]);
}
5. isFull() & isEmpty() Operations :
- isFull() : check करते हैं, कि top Array के max size – 1 के बराबर तो नहीं है।
- isEmpty() : check करते हैं, कि top -1 के बराबर तो नहीं है।
int isFull() {
if (top == MAX – 1)
return 1; // Stack Full
else
return 0; // Space Available
}
int isEmpty() {
if (top == -1)
return 1; // Stack is Empty
else
return 0; // Stack has elements
}
Advantages (लाभ)
- इसे implement करना बहुत आसान होता है।
- इसके operations (जैसे push और pop) बहुत fast होते हैं, क्योंकि Array में direct access मिलता है।
- यह memory efficient होता है, क्योंकि इसमें pointers के लिए कोई extra memory overhead नहीं होता।
Disadvantages (हानि)
- इसका सबसे बड़ा drawback है, इसका fixed size — यानी आप Array की size को run-time पर बदल नहीं सकते। अगर Stack full हो जाए, तो आप इसमें और elements नहीं डाल सकते।
- अगर आप बहुत बड़ा Array बना देते हैं, लेकिन उसे पूरा इस्तेमाल नहीं करते, तो memory waste होती है।
2. Linked List-based Implementation
Linked List-based implementation एक dynamic approach है। इसमें Stack का size fixed नहीं होता, बल्कि आवश्यकता के अनुसार बढ़ता या घटता रहता है। इस implementation में हम एक Singly Linked List का उपयोग करते हैं, जहाँ Stack का Top हमेशा Linked List के Head node को point करता है।
इस Implementation में Stack का प्रत्येक Element एक Node के रूप में होता है, जिसमें दो भाग होते हैं —
- Data (Actual Value)
- Next Pointer (अगले Node की Link)
Structure of Stack using Linked List
struct Node {
int data;
struct Node *next;
};
Implementation Process
1. Initialization :
- हम एक top pointer बनाते हैं, और उसे NULL पर set करते हैं, जिसका मतलब है कि Stack खाली है।
struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL; // Stack is empty
2. push() Operation :
- हमें एक नया Node बनाना होता है, जिसमें data और एक pointer (next) होता है।
- इस नए Node के next pointer को current top से link करते हैं।
- और फिर, इस नए Node को top बना देते हैं।
void push(int val) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = top;
top = newNode;
printf(“%d pushed to stack\n”, val);
}
3. pop() Operation :
- सबसे पहले, हम check करते हैं कि Stack खाली तो नहीं है (isEmpty())।
- अगर Stack खाली नहीं है, तो हम एक temporary pointer से top को point करते हैं, top को अगले node पर move करते हैं, और temporary pointer वाले node को delete कर देते हैं।
void pop() {
if (top == NULL)
printf(“Stack Underflow\n”);
else {
struct Node *temp = top;
printf(“Popped: %d\n”, top->data);
top = top->next;
free(temp);
}
}
4. peek() Operation :
- हम सिर्फ top node का data return कर देते हैं।
void peek() {
if (top == NULL)
printf(“Stack is Empty\n”);
else
printf(“Top Element: %d\n”, top->data);
}
Advantages (लाभ)
- Dynamic Size: इसका सबसे बड़ा लाभ यह है कि Stack का size run-time पर बढ़ाया या घटाया जा सकता है, इसलिए इसमें Overflow की समस्या नहीं होती।
- यह memory का बेहतर उपयोग करता है क्योंकि memory तभी allocate होती है जब उसकी जरूरत होती है।
Disadvantages (हानि)
- Array-based Stack की तुलना में यह थोड़ा धीमा होता है, क्योंकि हर नए node के लिए memory allocation करनी पड़ती है।
- प्रत्येक node में एक extra pointer field होने से इसमें थोड़ा additional memory overhead होता है।
Multiple Stacks
जब हम एक ही memory area में एक से अधिक stacks को implement करते हैं, तो उसे Multiple Stacks कहा जाता है।
इस concept का मुख्य उद्देश्य memory का efficient utilization करना होता है।
Why Multiple Stacks? (क्यों जरूरी हैं?)
कई बार हमें program में अलग-अलग purposes के लिए अलग-अलग stacks की जरूरत होती है —
- एक stack operands के लिए और दूसरा operators के लिए।
- ऐसे में हर stack के लिए अलग memory allocate करने के बजाय, हम एक ही array में कई stacks बना सकते हैं, ताकि memory का उपयोग बेहतर तरीके से किया जा सके।
Advantages (लाभ) :
- Efficient Memory Utilization : एक ही array में कई stacks को store करने से memory का wastage कम होता है।
- Reduced Space Requirement : अलग-अलग stacks के लिए अलग arrays बनाने की जरूरत नहीं पड़ती।
- Flexibility:Dynamic allocation method में एक stack दूसरे stack का खाली space use कर सकता है।
- Useful in Multi-tasking Systems : जहां एक से अधिक process या operations एक साथ चल रहे हों, वहां multiple stacks memory को share कर सकते हैं।
- Better Performance in Certain Applications : जैसे expression evaluation या multiple recursion handling में — अलग-अलग stacks use करने से processing आसान हो जाती है।
Disadvantage (हानि) :
- Complex Implementation : Multiple stacks को एक ही array में manage करना single stack की तुलना में कठिन होता है।
- Overflow Chances : Fixed division method में अगर एक stack भर जाए और दूसरे में space बचा हो, तो भी overflow हो सकता है।
- Difficult Debugging : कई stacks को एक memory block में handle करने से errors detect करना मुश्किल हो जाता है।
- Dynamic Shifting Problem : अगर एक stack बहुत बढ़ जाए तो memory reallocation या shifting करनी पड़ सकती है।
- Limited by Total Memory Size : चाहे कितने भी stacks हों, वे सभी एक ही fixed array size में सीमित रहते हैं।
