Array implementation of Stack

Definition of keywords of stack 

जब Stack का प्रयोग किया जा सकता है। इसके लिए Stack पर किए जाने वाले ऑपरेशन हमें समझने होंगे। इन ऑपरेशन को समझने के लिए निम्नांकित शब्दों का ज्ञान होना आवश्यक हैं:

• Push (पुश)
• Pop (पॉप)
• Peek (पीक)
• Top (टॉप)
• MAXSIZE (मैक्ससाइज़)
• Overflow (ओवेरफ्लो)
• Underflow  (अन्डरफ्लो) 
• Traversal (ट्रावर्ज़ल )

Push:-

Stack (स्टैक) में जब कोई नया Element (एलीमेंट) जोड़ा जाता है तो उस ऑपरेशन को Push कहा जाता है। Stack (स्टैक) में  Push (पुश) किया गया एलीमेंट हमेशा top (अंत) में ही जुड़ता है।

Pop:-

Stack (स्टैक) से जब कोई Stack (स्टैक) Delete (हटाया) किया जाता है तो उस ऑपरेशन को Pop (पॉप) कहा जाता है। Stack (स्टैक) से Pop (पॉप) किया गया एलीमेंट हमेशा अंत से ही Delete (हटाया) किया  जाता है। सामान्यतया एलीमेंट को डिलीट करने से पूर्व उसे प्रयोग में ले लिया जाता है।

Peek:-

Stack (स्टैक) से जब कोई एलीमेंट Use तो किया जाता है किंतु डिलीट नहीं किया जाता है तो उस ऑपरेशन को Peek (पीक) कहा जाता है। यह ऑपरेशन भी Pop (पॉप) की जैसे ही स्टैक के अंत पर ही किया जाता है।

Top:-

Stack (स्टैक) पर Operation करते  समय यह पता होना चाहिए कि Push / Pop (पुश / पॉप) करते समय कौनसा Element प्रयोग में आएगा। सामान्यतः यह कार्य top नाम के एक वेरिएबल के माध्यम से किया जाता है। इस प्रकार top ऐसा Pointer होता है जो स्टैक के अंतिम (top) एलीमेंट को दर्शाता है।

MAXSIZE:-

जब Stack (स्टैक) को एरे में माध्यम से प्रयोग में लिया जाता है तो यह बताना होता है तो कि Array Stack (स्टैक) में अधिकतम कितने एलीमेंट स्टोर किए जा सकेंगे। सामान्यतः यह कार्य MAXSIZE (मैक्ससाइज़) नाम के वेरिएबल के माध्यम से किया जाता है।

Overflow:-

जब Stack (स्टैक) पूरा भर जाता है तो इस Condition (कंडीशन) को Overflow (ओवरफ्लो) कहा जाता है। अन्य शब्दों में जब Top वेरिएबल की वैल्यू MAXSIZE की वैल्यू के बराबर हो जाती है तथा यूज़र नया एलीमेंट पुश करने कोशिश करता है तो ऐसी कंडीशन को Overflow (ओवरफ्लो) कहा जाता है। ऐसी स्थिति में User  सिर्फ एलीमेंट्स को Delete कर सकता है, किंतु नया एलीमेंट जोड़ नहीं सकता।

Underflow:-

जब Stack (स्टैक) खाली होता है तथा यूज़र किसी एलीमेंट को Delete करने की कोशिश करता है तो ऐसी स्थिति को Underflow (अंडरफ्लो) कहा जाता है। ऐसी स्थिति में User सिर्फ नया एलीमेंट जोड सकता है, किंतु Pop नहीं कर सकता है। ऐसी स्थिति में Top वेरिएबल की वैल्यू को 1 पर रखा जाता है।

Traversal:-

Traversal (ट्रावर्ज़ल) शब्द Travel (ट्रेवल) शब्द से बना है, जिसका अर्थ होता है घूमना। Stack (स्टैक) पर Traversal (ट्रावर्ज़ल)  Operation से आशय Stack (स्टैक) के सभी एलीमेंट्स को Visite करना । विज़िट करते समय प्रत्येक एलीमेंट को प्रिंट करवाया जा सकता है या कोई अन्य ऑपरेशन किया जा सकता है।

Representation as an Array

Stack (स्टैक) एक linear data structure है जो (Last-In-First-Out) LIFO के सिद्धांत का पालन करता है । Stack (स्टैक) में एक छोर होता है जिसके माध्यम से insertion and deletion होता है। जब भी Stack (स्टैक) में कोई Element insert किया जाता है, या Element को केवल स्टैक से delete जाता है, तो इसे स्टैक के Top (लास्ट) में insert किया जा सकता है। दूसरे शब्दों में, एक Stack (स्टैक) को एक Container के रूप में परिभाषित किया जा सकता है जिसमें एक छोर से insertion and deletion किया जा सकता है जिसे स्टैक के Top के रूप में जाना जाता है।

Elements की एक ordered list को Store करने के लिए एक Array का उपयोग किया जाता है। Stack (स्टैक) के representation के लिए एक Array का उपयोग करना Data को manage करने की आसान techniques में से एक है। लेकिन एक Array और एक Stack के बीच एक बड़ा difference है।

एक Array का आकार Fix होता है। जबकि, एक Stack (स्टैक) की size fix नहीं होती है क्योंकि Stack (स्टैक) की Size उसमें inserte या delete किए गए Element की संख्या के साथ change हो जाता है।

Push Operation (Adding an element onto the stack)

Stack के Top में एक Element जोड़ना Push Operation के रूप में जाना जाता है। Push Operation (पुश ऑपरेशन) में निम्नलिखित दो चरण शामिल हैं।

1. Variable Top को Increment ताकि यह अब अगले memory location पर refere कर सके।
2. incremente किए गए Top variable की position में Element जोड़ें। इसे Stack के Top पर new Element जोड़ने के रूप में जाना जाता है।

जब stack पूरा भरा हो (Top == MAXSIZE) और हम उस stack में एक element Add करने का प्रयास करते हैं तो स्टैक Overflow (ओवरफ्लो) हो जाता है, इसलिए हमारे main function को हमेशा stack overflow स्थिति से बचना चाहिए।

Algorithm

Algorithm for Push value in the stack

ST[] :    Array for Stack
MAXSIZE:    Size of the Array
Top: The last index of the Array  
Val:    value to be pushed 

push(ST[], MAXSIZE, Top, Val)

Step 1	// checking, overflow condition     if (Top = MAXSIZE - 1) then         print "Np More space (Overflow) in the Array"         return     end if
Step 2	// increment top by one     Top = Top + 1
Step 3	ST[Top] = Val
Step 4	return

Short:- 

    begin  

        if top = n then stack full  

        top = top + 1  

        stack (top) : = item;  

    end

Time Complexity: o(1)

implementation of push algorithm in C language

    void push(int val, int n) // n is size of the stack

    {

        if (top == n)

            printf("\n Overflow");

        else

        {

            top = top + 1;

            stack[top] = val;

        }

    }

   

Pop operation (Deletion of an element from a stack)

Stack (स्टैक) के Top से किसी Element को Delete करना Pop Operation (पॉप ऑपरेशन) कहलाता है। जब भी कोई Item Stack (स्टैक) से हटा दिया जाता है तो Variable Top का मान 1 से increment हो जाएगा। Stack का सबसे Top Element किसी अन्य variable में store किया जाता है और फिर Top को 1 से Decrement किया जाता है। Operation delete किए गए मान को return करता हैं जो result के रूप में किसी अन्य variable में store कर दिया जाता हैं ।

जब हम किसी empty stack से Element को Delete करने का प्रयास करते हैं तो Underflow की स्थिति होती है

Algorithm

Algorithm for pop value in the stack

ST[] :    Array for Stack
MAXSIZE:    Size of the Array
Top: The last index of the Array

pop(ST[], MAXSIZE, Top)

Step 1	// checking, Underflow condition     if (Top = -1) then         print "No More Elements (stack Underflow) in the Array"         return     end if
Step 2	Val = St[Top]
Step 3	Top = Top - 1
Step 4	return (Val)

Short:- 

    begin  

        if top = 0 then stack empty;  

        item := stack(top);  

        top = top - 1;  

    end;    

Time Complexity : o(1)

ऊपर दी गई algorithum में step 1 में यह जांच की गई हैं कि कहीं stack खाली तो नहीं हैं। ऐसी स्थिति में pop operation नहीं किया जा सकेगा। ऐसी condition को underflow कहा जाता हैं

Implementation of the POP algorithm using C language

    int pop()

    {

        if (top == -1)

        {

            printf("Underflow");

            return 0;

        }

        else

        {

            return stack[top - -];

        }

    }

Peek operation (Visiting each element of the stack)

किए Stack (स्टैक) से जब कोई एलीमेंट Use तो किया जाता है किंतु डिलीट नहीं किया जाता है तो उस ऑपरेशन को Peek (पीक) कहा जाता है। यह ऑपरेशन भी Pop (पॉप) की जैसे ही स्टैक के अंत पर ही किया जाता है।

Algorithm

PEEK (STACK, TOP)

    Begin  

        if top = -1 then stack empty    

        item = stack[top]  

        return item  

    End    

Time complexity: o(n)

Implementation of Peek algorithm in C language

    int peek()

    {

        if (top == -1)

        {

            printf("Underflow");

            return 0;

        }

        else

        {

            return stack[top];

        }

    }

Example #1

    #include <stdio.h>

    int stack[100], i, j, choice = 0, n, top = -1;

    void push();

    void pop();

    void show();

    void main()

    {

        printf("Enter the number of elements in the stack ");

        scanf("%d", &n);

        printf("*********Stack operations using array*********");

        printf("\n----------------------------------------------\n");

        while (choice != 4)

        {

            printf("Chose one from the below options...\n");

            printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");

            printf("\n Enter your choice \n");

            scanf("%d", &choice);

            switch (choice)

            {

            case 1:

            {

                push();

                break;

            }

            case 2:

            {

                pop();

                break;

            }

            case 3:

            {

                show();

                break;

            }

            case 4:

            {

                printf("Exiting....");

                break;

            }

            default:

            {

                printf("Please Enter valid choice ");

            }

            };

        }

    }

    void push()

    {

        int value;

        if (top == n)

            printf("\n Overflow");

        else

        {

            printf("Enter the value?");

            scanf("%d", &val);

            top = top + 1;

            stack[top] = val;

        }

    }

    void pop()

    {

        if (top == -1)

            printf("Underflow");

        else

            top = top - 1;

    }

    void show()

    {

        for (i = top; i >= 0; i--)

        {

            printf("%d\n", stack[i]);

        }

        if (top == -1)

        {

            printf("Stack is empty");

        }

    }

Example #02:-

    #include <stdio.h>

    #include <malloc.h>

    #define MAX 10

    int stack[MAX], top = -1;

    void push(int stack[], int val);

    int peek(int stack[]);

    void display(int stack[]);

    int main()

    {

        int val, choice;

        do

        {

            printf("\n 1. PUSH");

            printf("\n 2. PEEK");

            printf("\n 3. DISPLAY");

            printf("\n 4. EXIT");

            printf("\n Enter your option : ");

            scanf("%d", &choice);

            switch (choice)

            {

            case 1:

                printf("\n Enter the number to be pushed on stack : ");

                scanf("%d", &val);

                push(stack, val);

                break;

            case 2:

                val = peek(stack);

                if (val != -1)

                    printf("\n The value stored at top of stack is %d", val);

                break;

            case 3:

                display(stack);

                break;

            }

        } while (choice != 4);

        return 0;

    }

    void push(int stack[], int val)

    {

        if (top == MAX - 1)

        {

            printf("\n STACK OVERFLOW");

        }

        else

        {

            top++;

            stack[top] = val;

        }

    }

    int peek(int stack[])

    {

        if (top == -1)

        {

            printf("\n STACK IS EMPTY");

            return -1;

        }

        else

            return (stack[top]);

    }

    void display(int stack[])

    {

        int i;

        if (top == -1)

            printf("\n STACK IS EMPTY");

        else

        {

            for (i = top; i >= 0; i--)

                printf("\n%d", stack[i]);

        }

    }

Output:-

 1. PUSH
 2. PEEK
 3. DISPLAY
 4. EXIT
   Enter your option: 1
 Enter the number to be pushed on stack: 29

 1. PUSH
 2. PEEK
 3. DISPLAY
 4. EXIT
   Enter your option: 1
 Enter the number to be pushed on stack: 143

 1. PUSH
 2. PEEK
 3. DISPLAY
 4. EXIT
   Enter your option: 2
 The value stored at top of the stack is 143

 1. PUSH
 2. PEEK
 3. DISPLAY
 4. EXIT
   Enter your option : 3
 143
 29
 17

 1. PUSH
 2. PEEK
 3. DISPLAY
 4. EXIT
   Enter your option: 4