Linked Stack:-
Linked Stack is a linear data structure. It is collection of ordered data elements. It is also known as LIFO system (last in first out). It means in this data structure if an element is inserted (push) at last then it will be deleted (pop) at first. Push and pop operations are performed on top of the stack.
We use linked list representation to store Linked Stack in memory.
In linked list representation of Stack, we create a SLL node to store data element of Stack which has two parts info part and link part.
लिंक्ड स्टैक एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे LIFO (लास्ट इन फर्स्ट आउट) सिस्टम के नाम से भी जाना जाता है अर्थात स्टैक में यदि किसी एलिमेंट को अंत में इन्सर्ट(पुश) किया जाता है तब उसे सबसे पहले डिलीट(पॉप) किया जाता है। पुश एवं पॉप संक्रियाए स्टैक के टॉप पर की जाती है।
हम लिंक्ड लिस्ट रिप्रजेंटेशन का प्रयोग कर मेमोरी में लिंक्ड स्टैक तैयार कर सकते है।
स्टैक के लिंक्ड लिस्ट रिप्रजेंटेशन में हम SLL के नोड की सहायता से स्टैक के डाटा एलिमेंट को स्टोर करते है इस नोड में दो भाग होते है इन्फो पार्ट एवं लिंक पार्ट।
struct node{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *top=NULL,*n=NULL;
Here info part is used to store information related with node and link is a self referential pointer variable which is used to point next node of the SLL.
The address of current node of SLL is stored in top external pointer variable.
n external pointer variable is used to get node from free memory pool(heap). if node is not allocated it returns null value.
यहाँ इन्फो पार्ट नोड से सम्बंधित जानकारी रखता है एवं लिंक पार्ट, एक सेल्फ रिफरेन्सीयल पॉइंटर वेरिएबल है जो SLL के अगले नोड का एड्रेस रखता है।
SLL के वर्तमान नोड का एड्रेस टॉप एक्सटर्नल पॉइंटर वेरिएबल द्वारा रखा जाता है।
n नामक एक्सटर्नल पॉइंटर वेरिएबल का प्रयोग फ्री मेमोरी पूल (हीप) से नोड लेन के लिए किया जाता है। यदि नोड प्राप्त नहीं होता है तब यह नल वैल्यू रिटर्न करता है।
Linked stack or Dynamic stack is more efficient than normal stack because it minimizes overflow condition of stack and it utilizes memory space of the computer by modifying number of nodes at run time.
लिंक्ड स्टैक या डायनामिक स्टैक, सामान्य स्टैक की तुलना में अधिक विश्वसनीय होता है क्यूंकि यह ओवरफ्लो कंडीशन को बहुत कम कर देता है एवं रन टाइम पर नोड्स की संख्या में परिवर्तन कर, कंप्यूटर मेमोरी का प्रभावी प्रयोग करता है।
Operations performed on linked stack are as follows:-
लिंक्ड स्टैक पर किये जाने वाले ऑपरेशन निम्न है:-
1.) Push:- To insert or add a new element (node) into the linked stack is called push operation. This work is performed on top of stack. When we insert a new element then we should make top = n. (insert first node in SLL)
लिंक्ड स्टैक में किसी नए एलिमेंट (नोड) को जोड़ना, पुश ऑपरेशन कहलाता है। यह कार्य स्टैक के टॉप पर किया जाता है। जब किसी नए एलिमेंट को जोड़ा जाता है, तब top = n सेट किया जाता है।
2.) Pop:- To remove or delete an element from linked stack is called pop operation. This work is also done on top of the stack. After deletion of element from linked stack we should make top = top->link. if top=NULL it means linked stack is Empty and pop operation is performed then Underflow Condition will occur.(delete first node in SLL)
लिंक्ड स्टैक से किसी एलिमेंट(नोड) को हटाना/ निकालना, पॉप ऑपरेशन कहलाता है। यह कार्य स्टैक के टॉप पर किया जाता है। जब किसी एलिमेंट को निकाला जाता है, तब टॉप को top = top->link सेट किया जाता है। यदि top=NULL अर्थात लिंक्ड स्टैक खाली हो एवं पॉप ऑपरेशन किया जाये, तब अंडरफ्लो कंडीशन उत्पन्न होती है।
3.) Peek:- To traverse/visit/access/print top element (node) exist in linked stack is called peek operation. This work is performed on top of the stack. if top=NULL it means stack is Empty then peek operation cant be performed.
लिंक्ड स्टैक में उपस्थित टॉप एलिमेंट (नोड) को ट्रेवर्स/ विजिट/एक्सेस/प्रिंट करना, पीक ऑपरेशन कहलाता है। यह कार्य स्टैक के top पर किया जाता है। यदि top=NULL अर्थात स्टैक खाली है, तब पीक ऑपरेशन नहीं किया जा सकता है।
Linked Stack or Dynamic Stack Program:-
File Name:- linkeds.cpp
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct node{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *top=NULL ,*n=NULL;
//push function
void push(){
int item;
clrscr();
n= new NODE;
if(n==NULL){
cout<<"Overflow condition"<<endl;
getch();
return;
}
cout<<"Enter an item"<<endl;
cin>>item;
n->info=item;
if(top==NULL) n->link=NULL;
else n->link=top;
top=n;
cout<<"Push operation completed"<<endl;
getch();
return;
}
//pop function
void pop(){
clrscr();
n=top;
if(n==NULL){
cout<<"Underflow condition"<<endl;
getch();
return;
}
if(top->link==NULL) top=NULL;
else top=top->link;
cout<<"Pop operation completed"<<endl;
delete n;
getch();
return;
}
//peek function
void peek(){
clrscr();
if(top==NULL){
cout<<"Stack is empty"<<endl;
getch();
return;
}
cout<<"Top element of the Stack is:-"<<endl<<"info part= "<<top->info<<" link part="<<top->link<<endl;
cout<<"Peek operation completed"<<endl<<"Top= "<<top<<endl;
getch();
return;
}
void main(){
int ch;
while(1){
clrscr();
cout<<"Linked Stack Operations:- "<<endl<<"1.Push"<<endl<<"2.Pop"<<endl<<"3.Peek"<<endl<<"4.exit"<<endl<<"Enter your choice"<<endl;
cin>>ch;
switch(ch){
case 1:
push();
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
exit(0);
default:
cout<<"Wrong choice selected"<<endl;
getch();
}}}
File Name:-
linkeds.c
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node{
int info;
struct node *link;
};
typedef struct node
NODE;
NODE *top=NULL ,*n=NULL;
void push(){
int item;
clrscr();
n= malloc(sizeof(NODE));
if(n==NULL){
printf("Overflow
Condition\n");
getch();
return;
}
printf("Enter an
item\n");
scanf("%d",&item);
n->info=item;
if(top==NULL){
n->link=NULL;}
else{
n->link=top;}
top=n;
printf("Push
Operation Completed\n");
getch();
return;
}
void pop(){
clrscr();
n=top;
if(n==NULL){
printf("Underflow
Condition\n");
getch();
return;
}
if(top->link==NULL){
top=NULL;}
else{
top=top->link;
}
printf("Pop
Operation Completed\n");
getch();
free(n);
return;
}
void peek(){
clrscr();
if(top==NULL){
printf("Stack is empty\n");
getch();
return;
}
printf("Top element of the Stack is:-\ninfo part= %d\nlink part=%u\n",top->info,top->link);
printf("Peek operation completed\nTop=%u\n",top);
getch();
return;
}
void main(){
int ch;
while(1){
clrscr();
printf("Linked
Stack Operations:-\n1.Push\n2.Pop\n3.Peek\n4.exit\nEnter Your Choice\n");
scanf("%d",&ch);
switch(ch){
case 1:
push();
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
exit(0);
default:
printf("Wrong choice selected\n");
getch();
}}}
No comments:
Post a Comment