ग्रोभेबल एरे आधारित स्ट्याक


कठिनाई तह मध्यम
बारम्बार सोधिन्छ MAQ वालमार्ट ल्याबहरू
एरे थाक

समस्या वक्तव्य

ग्रोएबल एर्रे-आधारित स्ट्याक "स्ट्याक पूर्ण" को केसहरूमा प्रयोग गरिन्छ। यहाँ पुरानो एरे नयाँ ठूलो संग बदलियो। नयाँ एर्रेको आकार यी दुई रणनीतिहरू-

  • कडा रणनीति - यस अवस्थामा, एक स्थिर रकमले c लाई पहिले नै अवस्थित स्ट्याकमा थपिएको छ अर्थात् n = n + c जहाँ n अवस्थित स्ट्याकको आकार हो।
  • विकास रणनीति - यस अवस्थामा, हामी अवस्थित स्ट्याकको आकारलाई डबल गर्छौं अर्थात् n = 2n।

बढ्न योग्य एरे-आधारित स्ट्याक कार्यान्वयन गर्न प्रोग्राम लेख्नुहोस्।

ग्रोभेबल एरे आधारित स्ट्याक

उदाहरणका

push(100)

push(200)

push(300)

display()

push(400)

display()
Stack: 100 200 300

Stack: 100 200 300 400

स्पष्टीकरण: हामीले स्ट्याकको आधारभूत कार्यहरू गरेका छौं। त्यसो भए, पहिले, हामी १००, २००, pushed०० धक्का दियौं, र त्यसपछि स्ट्याक सामग्री प्रदर्शित गर्‍यौं। हामीले pushed०० पछाडि धकेपछि र त्यसपछि, हामीले फेरि स्ट्याक सामग्री प्रदर्शन गर्‍यौं।

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.

यहाँ हामीले कडा रणनीति प्रयोग गरेका छौं, जहाँ कहिले पनि हामीले आकारको बढाउनु पर्छ स्ट्याक। हामी केवल प्रत्येक पटक समान बन्ड जोड्दै जान्छौं। त्यसो भए, जब पनि हामीले यसमा थप आकार थप्न आवश्यक पर्दछ array, हामीले नयाँ एरेमा मूल एरे प्रतिलिपि गर्न आवश्यक छ र त्यसपछि हामी नयाँ एलिमेन्ट थप्छौं। यो दृष्टिकोण राम्रो छ यदि हामी कम ठाउँको साथ बाध्य छौं। तर यदि हामी राम्रो समय जटिलता चाहान्छौं भने हामीले ग्रोथ रणनीतिको साथ जानु पर्छ।

कोड

C ++ प्रोग्राम बढ्न योग्य एरे-आधारित स्ट्याकको लागि

#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

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामीसँग केवल तत्वहरू स्ट्याकमा धकेल्दैछौं। यहाँ एन धकेल्ने तत्वहरूको संख्या हो। यी सबै अपरेशनहरू O (१) हुन् जुन स्थिर-समय कार्यहरू हुन्। त्यसोभए, N समयका लागि यी अपरेशन्स गर्दा परिणाम लिनेर समय जटिलता एल्गोरिथ्ममा हुन्छ

ठाउँ जटिलता

O (N)जहाँ N स्ट्याकमा तत्वहरूको संख्या हो। किनकि हामीले एकल स्ट्याक प्रयोग गरेका छौं N तत्वहरू भण्डारण गर्दैछ। यसैले एल्गोरिथ्ममा रेखा अन्तरिक्ष जटिलता छ।