Stack एक विशेष प्रकार का linear डेटा स्ट्रक्चर होता है जो कि LIFO (last in first out) के सिद्धान्त पर कार्य करता है अर्थात वह item जो कि सबसे अंत में add किया जाता है उसे सबसे पहले remove कर दिया जाता है तथा जो item सबसे पहले add किया जाता है उसे सबसे अंत में remove किया जाता है।
स्टैक में किसी item को डालने (add) तथा remove (हटाने) के लिए सिर्फ एक end होता है जिसे हम top end कहते है। इसमें केवल top end से ही items को add और remove किया जा सकता है। दूसरे शब्दों में कहें तो, “Data Structure में, Stack एक abstract data type (ADT) है और इसमें एक limited size के elements या items को ही स्टोर किया जा सकता है”
स्टैक का प्रयोग ज्यादातर सभी programming languages में किया जाता है। और इसे stack इसलिए कहा जाता है क्योंकि यह real world के stack की तरह व्यवहार करता है. इसका real world example – किताबों का ढेर, चूड़ियाँ पहनना और निकालना, तथा plates का ढेर आदि।
Operations of Stack – स्टैक के ऑपरेशन
Stack में निम्नलिखित operations को perform किया जाता है:-
- Push() – जब स्टैक में item को insert किया जाता है तो वह push ऑपरेशन कहलाता है और यदि स्टैक full होता है तो तब overflow condition होती है.
- Pop() – जब स्टैक में से item को delete किया जाता है तो इस operation को pop operation कहते हैं. यदि स्टैक खाली होता है तो तब underflow condtion होती है. स्टैक को हम तब overflow कह सकते है जब वह पूरी तरह भरा हुआ होता है तथा तब underflow कह सकते है जब वह पूरी तरह खाली होता है।
- IsEmpty() – यह ऑपरेशन बताता है कि stack खाली है या नहीं.
- IsFull() – यह ऑपरेशन बताता है कि stack भरा हुआ है या नहीं.
- Peek() – यह दी गयी position पर element को return करता है,
- Count() – यह stack में मौजूद elements की कुल संख्या को return करता है.
- Change() – यह दी गयी position पर element को बदल देता है.
- Display() – यह स्टैक में मौजूद सभी elements (items) को print करता है.
Application of Stack – स्टैक के अनुप्रयोग
इसका प्रयोग निम्नलिखित स्थानों पर किया जाता हैं:-
- स्टैक का प्रयोग expression evaluation के लिए किया जाता है.
- इसका प्रयोग एक expression में parenthesis matching को check करने के लिए किया जाता है.
- इसका प्रयोग infix expression को postfix expression या prefix expression में convert करने के लिए किया जाता है.
- बहुत सारीं जगहों जैसे कि – photoshop, editors आदि में undo और redo के कार्य के लिए स्टैक का प्रयोग किया जाता है.
- web browsers में backward और forward के feature के लिए इसका use किया जाता है.
- इसका प्रयोग बहुत सारीं algorithms में किया जाता है जैसे कि – tree traversals, Stock span problem, histogram problem आदि.
- बहुत सारें compilers स्टैक का प्रयोग expressions के syntax को parsing करने के लिए करते है.
- इसका प्रयोग backtracking की problem को solve करने के लिए किया जाता है. backtracking का अर्थ है वापस पीछे जाना.
- मैमोरी मैनेजमेंट में इसका उपयोग किया जाता है.
- इसको graph traversal algorithms में use किया जाता है.
- इसका प्रयोग CPU scheduling और disk scheduling में किया जाता है.
Features of Stack – स्टैक की विशेषताएं
इसकी विशेषताएं निम्नलिखित हैं:-
- स्टैक समान data types का एक ordered list होता है.
- यह एक LIFO (last in first out) स्ट्रक्चर है और इसे FILO (first in last out) स्ट्रक्चर भी कहते हैं.
- हम इसमें elements को केवल एक ही end से add और remove कर सकते हैं और उस end को top कहा जाता है.
- इसे तब overflow कहते हैं जब यह पूरी तरह से full होता है और तब underflow कहते हैं जब यह पूरी तरह से empty होता है.
Working of Stack – स्टैक की कार्यविधि
जैसा कि आपको पता है कि स्टैक LIFO के सिद्धांत पर कार्य करता है. स्टैक के 5 memory blocks हैं। इसलिए इसका size 5 है। माना कि यह stack खाली है और हम इसमें elements को store करना चाहते हैं. हम इसमें elements को एक एक करके तब तक push करते हैं जब तक वह full नहीं हो जाता ।
अब हम इसमें elements को delete करना चाहते है तो हम इसके top end से ही delete कर सकते हैं क्योंकि स्टैक का दूसरा end बंद है। इसमें हम सबसे पहले उस element को delete करेंगे जिसे हमने सबसे पहले insert किया था. इसलिए इसे last in first out कहा जाता है। ऊपर दिए गये चित्र में हमने सबसे पहले 1 को insert किया है इसलिए इसे सबसे अंत में delete किया जायेगा ।
Stack का C Language Program –
#include<stdio.h>
#include<stdlib.h>
#define MAX 5
int top=-1,stack[MAX];
void push();
void pop();
void display();
void main()
{
int ch;
while(1)
{
printf("\n*** Stack Menu ***");
printf("\n\n1.Push\n2.Pop\n3.Display\n4.Exit");
printf("\n\nEnter your choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1: push();
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong Choice!!");
}
}
}
void push()
{
int val;
if(top==MAX-1)
{
printf("\nStack is full!!");
}
else
{
printf("\nEnter element to push:");
scanf("%d",&val);
top=top+1;
stack[top]=val;
}
}
void pop()
{
if(top==-1)
{
printf("\nStack is empty!!");
}
else
{
printf("\nDeleted element is %d",stack[top]);
top=top-1;
}
}
void display()
{
int i;
if(top==-1)
{
printf("\nStack is empty!!");
}
else
{
printf("\nStack is...\n");
for(i=top;i>=0;--i)
printf("%d\n",stack[i]);
}
}
इसका आउटपुट –
1.Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4):
Advantage of Stack – स्टैक के लाभ
इसकी access speed बहुत तेज होती है.
इसमें memory को बेहतर ढंग से manage किया जाता है इसलिए इसमें memory कभी भी fragment नहीं होती.
इसके द्वारा data को LIFO method से manage किया जाता है जो कि linked list और array में संभव नहीं है.
इसका use तब किया जाता है जब variable को function के बाहर नहीं प्रयोग किया जाता है.
स्टैक अपने आप ही object को clean कर देता है.
Disadvantage of Stack
इसकी हानियाँ निम्न हैं:-
- यह local variables को ही access कर सकता है.
- इसमें variables को resize नहीं किया जा सकता.
- इसका मुख्य नुकसान यह है कि इसमें memory की कमी होती है.