Stack Data Structure, Push, Pop and Peek Operations , Applications of Stack

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 can use array and linked list representation to form Stack in memory. Daily life examples of stack is book self, almirah, cards etc.

स्टैक एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे LIFO (लास्ट इन फर्स्ट आउट) सिस्टम के नाम से भी जाना जाता है अर्थात स्टैक में यदि किसी एलिमेंट को अंत में इन्सर्ट(पुश) किया जाता है तब उसे सबसे पहले डिलीट(पॉप) किया जाता है। पुश एवं पॉप संक्रियाए स्टैक के टॉप पर की जाती है। हम अरे एवं लिंक्ड लिस्ट में से किसी एक का प्रयोग कर मेमोरी में स्टैक तैयार कर सकते है। दैनिक जीवन में स्टैक के उदाहरण है - बुक शेल्फ, अलमीराह, ताश के पत्ते इत्यादि।        

Following 3 types of operations are performed on stack-

स्टैक पर निम्न तीन संक्रियाए की जा सकती है -

1.) Push:- To insert or add a new element into the stack is called push operation. This work is performed on top of stack. When we insert a new element then we should make top = top + 1. if top=N-1 it means stack is full and push operation is performed then Overflow Condition will occur.

स्टैक में किसी नए एलिमेंट को जोड़ना, पुश ऑपरेशन कहलाता है। यह कार्य स्टैक के टॉप पर किया जाता है। जब किसी नए एलिमेंट को जोड़ा जाता है, तब टॉप को एक से बढाया जाता है। यदि top=N-1 अर्थात स्टैक फुल हो एवं पुश ऑपरेशन किया जाये , तब ओवरफ्लो कंडीशन उत्पन्न होती है।    

2.) Pop:- To remove or delete an element from stack is called pop operation. This work is also done on top of the stack. After deletion of element from stack we should make top = top -1. if top=-1 it means stack is Empty and pop operation is performed then Underflow Condition will occur.

स्टैक से किसी एलिमेंट को हटाना/ निकालना, पॉप ऑपरेशन कहलाता है। यह कार्य स्टैक के टॉप पर किया जाता है। जब किसी एलिमेंट को निकाला जाता है, तब टॉप को एक से घटाया जाता है। यदि top=-1 अर्थात स्टैक खाली हो एवं पॉप ऑपरेशन किया जाये, तब अंडरफ्लो कंडीशन उत्पन्न होती है।  

3.) Peek:- To access/print top element of stack is called peek operation. This work is performed from top of the stack. if top=-1 it means stack is empty then peek operation cant be performed.

स्टैक में उपस्थित टॉप एलिमेंट को एक्सेस/प्रिंट करना, पीक ऑपरेशन कहलाता है। यह कार्य स्टैक के top पर किया जाता है। यदि  top=-1 अर्थात स्टैक खाली है, तब पीक ऑपरेशन नहीं किया जा सकता है।   

Example :-

C++ or C Program for Stack Operations.

Application of Stack Data structure

C program to generate sparse matrix from given two dimensional array.

#include<stdio.h>

#include<conio.h>

void main()

{

 int A[10][10],B[10][3],m,n,s=0,i,j;

 clrscr();

 printf("\nEnter the order m x n of the sparse matrix\n");

 scanf("%d%d",&m,&n);

 printf("\nEnter the elements in the sparse matrix(mostly zeroes)\n");

 for(i=0;i<m;i++)

 {

  for(j=0;j<n;j++)

  {

   printf("\n%d row and %d column:   ",i,j);

   scanf("%d",&A[i][j]);

  }

 }

 printf("The given matrix is:\n");

 for(i=0;i<m;i++)

 {

  for(j=0;j<n;j++)

  {

   printf("%d ",A[i][j]);

  }

  printf("\n");

 }

 for(i=0;i<m;i++)

 {

  for(j=0;j<n;j++)

  {

   if(A[i][j]!=0)

   {

    B[s][0]=A[i][j];

    B[s][1]=i;

    B[s][2]=j;

    s++;

   }

  }

 }

 printf("\nThe sparse matrix is given by");

 printf("\n");

 for(i=0;i<s;i++)

 {

  for(j=0;j<3;j++)

  {

   printf("%d ",B[i][j]);

  }

  printf("\n");

 }

 getch();

}

C Program to check that given Matrix is Sparse Matrix or Not.

 #include <stdio.h>

#include<conio.h>

#define R 10

#define C 10 

void main ()

{

int array[R][C];

int i, j, m, n;

int count = 0;

clrscr();

printf("Enter the order of the matrix \n");

scanf("%d%d", &m,&n);

printf("Enter the coefficients of the matrix \n");

for (i = 0; i < m; i++){

for (j = 0; j < n; j++){

scanf("%d", &array[i][j]);

if (array[i][j] == 0){

count++;

}}}

if (count>((m * n) / 2)){

printf("The given matrix is sparse matrix \n");

}

else {

printf("The given matrix is not a sparse matrix \n");

}

printf("There are %d number of zeros", count);

getch();

}

Sparse Matrix स्पार्स मैट्रिक्स

 Sparse matrix is a special type of matrix in which maximum elements [m×n/2 or 50% and more] are zero and some elements are non zero.

स्पार्स मैट्रिक्स एक विशेष प्रकार का आव्यूह होता है जिसमे आधे या उससे अधिक अवयव शून्य होते है एवं कुछ अवयव अशून्य होते है। 

following two representations are used to store sparse matrix in a computer  - 

स्पार्स मैट्रिक्स को कंप्यूटर में निम्न दो प्रकार से संग्रहित किया जा सकता है - 

1. Static /Array/Triplet representation of sparse matrix:- Array representation of sparse matrix uses a 2D array of 3 columns and non zero values+1 rows. Here first row of 2D array shows total number of rows, total number of columns and total number of non zero values exists in sparse matrix and other rows represents row index , column index and non zero value. 

अरे रिप्रजेंटेशन में स्पार्स मैट्रिक्स के लिए एक 2D अरे का प्रयोग किया जाता है जिसमे 3 स्तम्भ एवं अशून्य संख्या +1 पंक्तियां होती है। प्रथम पंक्ति द्वारा कुल पंक्तियों की संख्या, कुल स्तंभों की संख्या एवं कुल अशून्य संख्या को प्रदर्शित किया जाता है एवं अन्य पंक्तियों द्वारा रो-इंडेक्स , कॉलम-इंडेक्स एवं अशून्य संख्या को प्रदर्शित किया जाता है।

Example (उदाहरण)-

Static /Array/Triplet representation of sparse matrix

2. Dynamic/Linked list representation of sparse matrix:- Linked list representation of sparse matrix uses Linked list data structure in which following 3 types of nodes are used to store sparse matrix :-

लिंक्डलिस्ट रिप्रजेंटेशन में स्पार्स मैट्रिक्स के लिए लिंक्ड लिस्ट डाटा स्ट्रक्चर का प्रयोग किया जाता है यहाँ निम्न तीन प्रकार के नोडस द्वारा स्पार्स मैट्रिक्स को संग्रहित किया जाता है-

Type A node:- type A node is also called header node. this node has three parts to store total number of rows and total number of columns and address of first type B node of sparse matrix. The address of type A node is stored in a pointer variable sparse.

टाइप A नोड को हैडर नोड भी कहा जाता है इस नोड में तीन भाग होते है जो क्रमशः कुल पंक्तियों की संख्या, कुल स्तंभों की संख्या एवं टाइप B नोड का एड्रेस रखते है। टाइप A नोड का एड्रेस स्पार्स पॉइंटर वेरिएबल में रखा जाता है।  

Type B node:- In type B node Row number , address of next type B node/NULL and address of type C node are stored . It is also known as row node. Address of first type B node is stored in type A node.

टाइप B नोड पंक्तियों की संख्या, अगले टाइप B नोड का एड्रेस एवं टाइप C नोड का एड्रेस रखता है। इसे रो-नोड भी कहा जाता है। प्रथम टाइप B नोड का एड्रेस, टाइप A नोड में रखा जाता है।

Type C node:- In type C node column number , non zero value and address of next type C node/ NULL are stored.  It is also known as column node. Type C node is prepared for each non zero value of type B node.

टाइप C नोड स्तंभ की संख्या, अशून्य संख्या एवं अगले टाइप C नोड का एड्रेस रखता है। इसे कॉलम-नोड भी कहा जाता है। टाइप C नोड का प्रयोग, टाइप B नोड की प्रत्येक अशून्य संख्या के लिए किया जाता है।

Example (उदाहरण)-

Dynamic/Linked list representation of sparse matrix

Example Program:-

• C Program to check that given Matrix is Sparse Mat...
• C program to generate sparse matrix from given two...

Three level architecture of data structure डाटा स्ट्रक्चर के तीन स्तर

 

On the basis of functioning, data structure is divided into following three levels -

कार्यप्रणाली के आधार पर डाटा स्ट्रक्चर को तीन स्तरों में बांटा गया है- 

1.) User/view/external level:- On this level, various views (output screens) are prepared for various users,who wants to use data of data structure. It means, here interface is provided to user for giving input and obtaining output. On this level, only essential details are displayed and other details are hidden in background. This is called data abstraction.This level is responsible for designing attractive views is useful for communication between user and data structure. 

इस लेवल पर विभिन्न यूजर के लिए , अलग-अलग व्यू तैयार किये जाते है। जो डाटा स्ट्रक्चर के डाटा का उपयोग  करते है अर्थात यहाँ यूजर को इनपुट देने और आउटपुट देखने के लिए इंटरफ़ेस प्रदान किया जाता है। इस लेवल पर केवल आवश्यक जानकारी दिखाई जाती है एवं अन्य जानकारी को बैकग्राउंड में छुपा कर रखा जाता है। इसे डाटा एबस्ट्रेक्शन कहा जाता है। यह लेवल आकर्षक व्यू तैयार करने के लिए जिम्मेदार होता है, जो यूजर एवं डाटा स्ट्रक्चर के मध्य संवाद के लिए उपयोगी होती है।   

2.) Logical/conceptual/abstract level:- On this level, designs and various related functions of data structure are defined by programmer. It means, user's data and their relationship are displayed in form of programs on logical level. This level is responsible for designing of objects like tables, index, procedure, cursor, sequence, trigger etc of data structure.

इस लेवल पर, प्रोग्रामर द्वारा डाटा स्ट्रक्चर से सम्बंधित फंक्शन एवं डिजाईन तैयार किये जाते है अर्थात यूजर डाटा एवं संबंधो को व्यक्त करने के लिए लॉजिकल लेवल पर प्रोग्राम तैयार किया जाता है। यह लेवल डाटा स्ट्रक्चर के ऑब्जेक्ट्स जैसे टेबल, इंडेक्स, प्रोसीजर, कर्सर, सीक्वेंस, ट्रिगर इत्यादि तैयार करने के लिए जिम्मेदार होता है।

3.) Physical/machine/internal level:- On this level, Internal processing and physical structure of data structure are prepared. It means, physical level provides information about type of data structure, where data structure stored(container), what is the type of read-write method etc. Physical level is responsible for providing access methods to access and store data in data structure.

इस लेवल पर, डाटा स्ट्रक्चर की आतंरिक प्रोसेसिंग एवं फिजिकल स्ट्रक्चर तैयार किया जाता है। फिजिकल लेवल कई प्रकार की जानकारी जैसे डाटा स्ट्रक्चर का प्रकार क्या होगा ?, डाटा स्ट्रक्चर को कहा स्टोर किया जायेगा?  (कंटेनर), रीड-राईट मेथड कौन सी होगी?, इत्यादि प्रदान करता है। यह लेवल डाटा स्ट्रक्चर के डाटा को एक्सेस एवं स्टोर करने से सम्बंधित एक्सेसींग मेथड प्रदान करने के लिए जिम्मेदार होता है।

Abstract Data Type (ADT) एबस्ट्राक्ट डाटा टाइप

 

The full form of ADT is Abstract Data Type. As we know that All programming languages have built-in data types like char,int,float,double etc and all types of operations can be performed on this basic data types. So, A data type defines memory size and type of value stored by any variable. but "When programmer decides operation performed on the data type with definition of the data type, then it is called Abstract Data Type." In other words, programmer cannot divide data members of ADT and operations performed on it. Both are considered as a single unit. In ADT, some operations works as an interface with the help of them, data members of ADT are accessed externally. For Example, Stack is an ADT and user can able to perform only predefined operations like push, pop, peep on data elements of stack.

ADT का पूरा नाम एबस्ट्राक्ट डाटा टाइप है। हमे ज्ञात है कि सभी प्रोग्रामिंग लैंग्वेज में बिल्ट-इन डाटा टाइप उपस्थित होते है जैसे - करैक्टर, इन्टिजर, फ्लोट डबल इत्यादि एवं इन पर सभी प्रकार के ऑपरेशन किये जा सकते है। अतः एक डाटा टाइप किसी वेरिएबल द्वारा रखी जाने वाली वैल्यू एवं उसके प्रकार को परिभाषित करता है परन्तु "जब प्रोग्रामर किसी डाटा टाइप की परिभाषा के साथ, उस पर किये जाने वाले ऑपरेशन को भी सुनिश्चित करता है तब इस प्रकार के डाटा टाइप को ADT(एबस्ट्राक्ट डाटा टाइप) कहा जाता है।" दुसरे शब्दों में प्रोग्रामर एबस्ट्राक्ट डाटा टाइप के रूप में परिभाषित डाटा मेम्बर एवं उस पर किये जाने वाले ऑपरेशन को अलग अलग नहीं कर सकता है दोनों को एक ही इकाई माना जाता है। ADT में कुछ ऑपरेशन इंटरफ़ेस का कार्य करते है जिनकी सहायता से डाटा मेम्बेर्स को बाह्य रूप से एक्सेस किया जा सकता है। उदाहरण के लिए, स्टैक एक ADT है क्यूंकि स्टैक पर केवल पूर्व परिभाषित पुश, पॉप एवं पीप ऑपरेशन ही किये जा सकते है।  

Primitive and Non-primitive data structure प्रिमिटिव एवं नॉन-प्रिमिटिव डाटा स्ट्रक्चर

 Primitive data structure :- This type of data structure are very old and defined during creation of programming language. These are also called basic or fundamental data structure/data type. These data structures are working on machine code of program.Various computer and programming languages have various representation of primitive data structure.

Example- char, int, float, double,pointer etc.

इस प्रकार के डाटा स्ट्रक्चर पुरातन या प्राचीन होते है एवं इन्हें प्रोग्रामिंग लैंग्वेज तैयार करते समय परिभाषित किया जाता है। इन्हें मूलभूत डाटा स्ट्रक्चर या डाटा टाइप भी कहा जाता है, ये प्रोग्राम के मशीन कोड पर कार्य करते है।भिन्न-भिन्न प्रोग्रामिंग लैंग्वेज में, इन्हें भिन्न-भिन्न रूपों में प्रदर्शित किया गया है।   

उदाहरण:- करैक्टर, इन्टिजर, फ्लोट, डबल इत्यादि। 

Non-Primitive data structure :- This type of data structures are non primitive(new) , latest and sophisticated. it is formed with the help of primitive data structure. It can also store two or more types of data elements. These are also called ADT (Abstract Data Type) or user defined data structures. Operations performed on data elements of these data structures are predefined and user cannot allow to make any change in it.

Example :- array, stack, queue, linked list, tree, graph.

इस प्रकार के डाटा स्ट्रक्चर नवीनतम एवं परिष्कृत होते है एवं इन्हें मूलभूत(प्रिमिटिव) डाटा स्ट्रक्चर या डाटा टाइप की सहायता से तैयार किया जाता है। इन्हें ADT (एबस्ट्राक्ट डाटा टाइप) या यूजर डिफाइंड डाटा स्ट्रक्चर भी कहा जाता है। इन पर किये जाने वाले ऑपरेशन पूर्व निर्धारित होते है एवं यूजर उनमे परिवर्तन नहीं कर सकता है।

उदाहरण:- अरे, स्टैक, क्यू, लिंक्ड लिस्ट, ट्री, ग्राफ इत्यादि। 

Static and Dynamic data structure स्टेटिक एवं डायनामिक डाटा स्ट्रक्चर

Static data structure :- if the memory size of any data structure is defined at compile time and No change can be made in its size by user at run time, then this type of data structure is called static data structure. Memory space is not effectively used by static data structure.

यदि किसी डाटा स्ट्रक्चर के मेमोरी साइज़ को कंपाइल टाइम पर परिभाषित किया गया है एवं रन टाइम पर यूजर द्वारा उसमे परिवर्तन नहीं किया जा सकता है तब इस प्रकार के डाटा स्ट्रक्चर को स्टेटिक डाटा स्ट्रक्चर कहा जाता है। स्टेटिक डाटा स्ट्रक्चर में मेमोरी का प्रभावी उपयोग नहीं हो पाता है।    

Example - array (अरे)

Dynamic data structure :- if memory size of any data structure is defined at run time and changes (Increase or decrease) can be made in its size by user at run time, then this type of data structure is called dynamic data structure. Memory is effectively used by dynamic data structure.

यदि किसी डाटा स्ट्रक्चर के मेमोरी साइज़ को रन टाइम पर परिभाषित किया गया है एवं रन टाइम पर यूजर द्वारा उसमे परिवर्तन (वृद्धि या कमी) किया जा सकता है तब इस प्रकार के डाटा स्ट्रक्चर को डायनामिक डाटा स्ट्रक्चर कहा जाता है। डायनामिक डाटा स्ट्रक्चर में मेमोरी का प्रभावी उपयोग होता है। 

Example - linked list (लिंक्ड लिस्ट)

Homogeneous and Non-homogeneous (heterogeneous) data structure होमोजिनस एवं नॉन-होमोजिनस या हेटेरोजिनस डाटा स्ट्रक्चर

Homogeneous data structure :- if a data structure stores similar types of data elements then this type of data structure is called homogeneous data structure.

यदि किसी डाटा स्ट्रक्चर द्वारा केवल एक ही प्रकार के डाटा एलेमेंट्स को संग्रहित किया जाता है तब इस प्रकार के डाटा स्ट्रक्चर को होमोजिनस डाटा स्ट्रक्चर कहा जाता है। 

Example :- array (अरे)

Non homogeneous (Heterogeneous) data structure :- if a data structure stores two or more types of data elements then this type of data structure is called non homogeneous or heterogeneous data structure.

यदि किसी डाटा स्ट्रक्चर द्वारा दो या दो से अधिक प्रकार के डाटा एलेमेंट्स को संग्रहित किया जाता है तब इस प्रकार के डाटा स्ट्रक्चर को नॉन होमोजिनस या हेटेरोजिनस डाटा स्ट्रक्चर कहा जाता है। 

Example - linked list (लिंक्ड लिस्ट).

Linear and Non-linear Data Structure लीनियर एवं नॉन- लीनियर डाटा स्ट्रक्चर

 I) Linear data structure:- In this type of data structure, data elements are processed one by one in linear order.(Increasing or decreasing) and every operation like Insertion, deletion, traversing etc are performed in definite order.Example:- array, stack, queue, linked list.

इस प्रकार के डाटा स्ट्रक्चर में डाटा एलेमेंट्स को एक के बाद एक (बढ़ते हुए या घटते हुए) श्रेणी क्रम में प्रोसेस किया जाता है एवं प्रत्येक संक्रिया जैसे  इंसर्शन, डिलीशन, ट्रेवर्सिंग इत्यादि भी एक निश्चित क्रम में की जाती है।

उदाहरण :- अरे , स्टैक, क्यू , लिंक्ड लिस्ट     

II) Non-linear data structure:- In this type of data structure, data elements are processed in random order and every operation like Insertion, deletion, traversing etc are performed randomly in this data structure. Example:- tree, graph.

इस प्रकार के डाटा स्ट्रक्चर में डाटा एलेमेंट्स को यादृच्छिक रूप से प्रोसेस किया जाता है एवं प्रत्येक संक्रिया जैसे  इंसर्शन, डिलीशन, ट्रेवर्सिंग इत्यादि किसी भी क्रम में की जाती है।

उदाहरण :- ट्री, ग्राफ