વધવા યોગ્ય એરે આધારિત સ્ટેક


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે MAQ વોલમાર્ટ લેબ્સ
અરે સ્ટેક

સમસ્યા નિવેદન

ગ્રોએબલ એરે-આધારિત સ્ટેકનો ઉપયોગ "સ્ટેક ફુલ" ના કિસ્સાઓમાં થાય છે. અહીં જૂની એરેને નવી મોટી સાથે બદલવામાં આવી છે. નવી એરેનું કદ આ બે વ્યૂહરચનાનો ઉપયોગ કરીને નક્કી કરવામાં આવ્યું છે-

  • ચુસ્ત વ્યૂહરચના - આ સ્થિતિમાં, પહેલેથી અસ્તિત્વમાં રહેલા સ્ટેક એટલે કે n = n + c માં n ઉમેરવામાં આવે છે ત્યાં n, n ઉમેરવામાં આવે છે, જ્યાં n એ હાલના સ્ટેકનું કદ છે.
  • વૃદ્ધિની વ્યૂહરચના - આ કિસ્સામાં, અમે હાલના સ્ટેકનું કદ બરાબર એટલે કે n = 2n.

વિકસિત એરે-આધારિત સ્ટેકને લાગુ કરવા માટે એક પ્રોગ્રામ લખો.

વધવા યોગ્ય એરે આધારિત સ્ટેક

ઉદાહરણ

push(100)

push(200)

push(300)

display()

push(400)

display()
Stack: 100 200 300

Stack: 100 200 300 400

સમજૂતી: અમે સ્ટેકની પાયાની કામગીરી કરી છે. તેથી, પહેલા, અમે 100, 200, 300 દબાણ કર્યું અને પછી સ્ટેક સામગ્રી પ્રદર્શિત કરી. અમે 400 દબાણ કર્યું અને તે પછી, અમે ફરીથી સ્ટેક સામગ્રી પ્રદર્શિત કરી.

push(1)

push(2)

display()

push(3)

display()
Stack: 1 2

Stack: 1 2 3

ગ્રોએબલ એરે આધારિત સ્ટેક માટે અલ્ગોરિધમનો

1. Create three global variables bound, top, and length, and initialize them as 3, -1, and 0 respectively.
2. After that, create a function to create extra space for an array-based stack that accepts an integer array as it's parameter.
3. Initialize a new array inside the function of length equals the sum of the length of given array and the bound variable.
4. Traverse through the given array and update the value at the current index in the new array as the value at the current index in the given array.
5. Update the variable-length as the sum of variable length itself and the bound variable and return the new array.
6. Similarly, create a function to push/insert the elements which accept an integer array and an integer variable as it's parameter.
7. Check if the value of top is equal to the length - 1, call the function to create a new array. Store the integer variable in the array at index equals to top + 1 and return the array.
8. After that, create a function to pop/remove the top element from the array. Decrement the variable top by 1.
9. Similarly, create a function to print the elements in the array which accepts an integer array as it's a parameter.
10. Check if the top is equal to -1, print "Stack is Empty".
11. Else print the array.

અહીં અમે ચુસ્ત વ્યૂહરચનાનો ઉપયોગ કર્યો છે, જ્યારે પણ જ્યારે આપણે કદ વધારવાની જરૂર હોય ત્યારે સ્ટેક. અમે દરેક વખતે તે જ બાઉન્ડ ઉમેરવાનું ચાલુ રાખીએ છીએ. તેથી, જ્યારે પણ આપણે એક વધારાનું કદ ઉમેરવાની જરૂર હોય એરે, આપણે મૂળ એરેને નવા એરેમાં ક copyપિ કરવાની જરૂર છે અને પછી આપણે નવું તત્વ ઉમેરવું જોઈએ. જો આપણે ઓછી જગ્યા સાથે બંધાયેલા હોઈએ તો આ અભિગમ સારો છે. પરંતુ જો આપણે વધુ સમયની જટિલતા જોઈએ છે તો આપણે વિકાસની વ્યૂહરચના સાથે ચાલવું જોઈએ.

કોડ

વિકસિત એરે-આધારિત સ્ટેક માટે સી ++ પ્રોગ્રામ

#include <iostream> 
using namespace std; 
  
#define BOUND 3
  
int top = -1; 
  
int length = 0; 
  
int* create_new(int* a){ 
    int* new_a = new int[length + BOUND]; 
  
    for(int i = 0; i < length; i++){ 
        new_a[i] = a[i]; 
    }
  
    length += BOUND; 
    return new_a; 
} 
  
int* push(int* a, int element){ 
    if(top == length - 1){ 
        a = create_new(a);
    }
  
    a[++top] = element; 
    return a; 
} 
  
void pop(int* a){ 
    top--; 
} 
  
void display(int* a){ 
    if(top == -1){ 
        cout << "Stack is Empty" << endl; 
    }
    
    else{ 
        cout << "Stack: "; 
        for(int i = 0; i <= top; i++){ 
            cout << a[i] << " "; 
        }
        cout << endl; 
    } 
} 
  
int main(){ 
    int *a = create_new(a); 
  
    a = push(a, 100); 
    a = push(a, 200); 
    a = push(a, 300); 
    display(a); 
    a = push(a, 400); 
    display(a); 
  
    return 0; 
}
Stack: 100 200 300 
Stack: 100 200 300 400

વિકસિત એરે-આધારિત સ્ટેક માટે જાવા પ્રોગ્રામ

class GrowableStack{ 
  
    static final int BOUND = 3; 
      
    static int top = -1; 
      
    static int length = 0; 
      
    static int[] create_new(int[] a){ 
        int[] new_a = new int[length + BOUND]; 
      
        for(int i = 0; i < length; i++){ 
            new_a[i] = a[i]; 
        }
      
        length += BOUND; 
        return new_a; 
    } 
      
    static int[] push(int[] a, int element){ 
        if(top == length - 1){ 
            a = create_new(a);
        }
      
        a[++top] = element; 
        return a; 
    } 
      
    static void pop(int[] a){ 
        top--; 
    } 
      
    static void display(int[] a){ 
        if(top == -1){ 
            System.out.println("Stack is Empty");
        }
        
        else{ 
            System.out.print("Stack: "); 
            for(int i = 0; i <= top; i++){ 
                System.out.print(a[i] + " ");
            }
            System.out.println(); 
        } 
    } 
      
    public static void main(String args[]){ 
        int []a = create_new(new int[length + BOUND]); 
      
        a = push(a, 100); 
        a = push(a, 200); 
        a = push(a, 300); 
        display(a); 
      
        a = push(a, 400); 
        display(a); 
    } 
}
Stack: 100 200 300 
Stack: 100 200 300 400

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે ખાલી તત્વોને સ્ટackકમાં ધકેલી રહ્યા છીએ. અહીં એન એ દબાણ કરેલા તત્વોની સંખ્યા છે. આ તમામ કામગીરી ઓ (1) છે જે સતત સમયની કામગીરી છે. તેથી, એન સમય માટે આ કામગીરી કરવાથી રેખીય સમય જટિલતા અલ્ગોરિધમનો પરિણમે છે.

અવકાશ જટિલતા

ઓ (એન), જ્યાં એન એ સ્ટેકમાં તત્વોની સંખ્યા છે. કારણ કે અમે એક જ સ્ટેકનો ઉપયોગ કર્યો છે જે એન તત્વો સ્ટોર કરે છે. આમ અલ્ગોરિધમનો રેખીય અવકાશ જટિલતા છે.