Yetişdirilə bilən massiv əsaslı yığın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur MAQ Walmart Laboratoriyaları
Geyim QalaqBaxılıb 30

Problem bəyanat

Yetişdirilə bilən massiv əsaslı yığın “yığın dolu” hallarda istifadə olunur. Burada köhnə massiv yenisi ilə əvəzlənir. Yeni massivin ölçüsünə bu iki strategiyadan istifadə etməklə qərar verilir.

  • Sıx Strateji - Bu vəziyyətdə sabit bir c miqdarı onsuz da mövcud yığına əlavə edilir, yəni n = n + c olduğu yerdə n mövcud yığının ölçüsüdür.
  • Böyümə Stratejisi - Bu vəziyyətdə mövcud yığının ölçüsünü iki dəfə artırırıq, yəni n = 2n.

Böyütülə bilən massiv əsaslı yığını tətbiq etmək üçün bir proqram yazın.

Yetişdirilə bilən massiv əsaslı yığınPin

misal

push(100)

push(200)

push(300)

display()

push(400)

display()
Stack: 100 200 300

Stack: 100 200 300 400

İzahat: Bir yığının əsas əməliyyatlarını yerinə yetirdik. Beləliklə, əvvəlcə 100, 200, 300-i itələdik və sonra yığın məzmununu göstərdik. 400'ü itirdikdən sonra və bundan sonra yığın içeriğini yenidən göstərdik.

push(1)

push(2)

display()

push(3)

display()
Stack: 1 2

Stack: 1 2 3

Yetişdirilə bilən massiv əsaslı yığın üçün alqoritm

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.

Burada ölçüsünü artırmalı olduğumuz yerdə sıx bir strategiyadan istifadə etdik qalaq. Sadəcə hər dəfə eyni BOUND əlavə etməyə davam edirik. Beləliklə, hər dəfə əlavə ölçüsü əlavə etməyimiz lazım olduqda array, orijinal massivi yeni massivə kopyalamalıyıq və sonra yeni element əlavə edirik. Daha az yerlə bağlı olsaq, bu yanaşma yaxşıdır. Ancaq daha yaxşı bir zaman mürəkkəbliyi istəsək, böyümə strategiyasına davam etməliyik.

Kodu

Yetişdirilə bilən massiv əsaslı yığın üçün C ++ proqramı

#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

Yetişdirilə bilən sıra əsaslı yığın üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki sadəcə elementləri yığına itələyirik. Burada N itələnən elementlərin sayıdır. Bu əməliyyatların hamısı sabit zaman əməliyyatları olan O (1) olduğundan. Beləliklə, bu əməliyyatları N müddətində etmək xətti zaman mürəkkəbliyi alqoritminə səbəb olacaqdır.

Kosmik Mürəkkəblik

O (N), burada N yığındakı elementlərin sayıdır. Çünki N elementi saxlayan tək bir yığını istifadə etdik. Beləliklə, alqoritm xətti kosmik mürəkkəbliyə malikdir.

Translate »