Стэк на аснове масіва, які можна нарасціць


Узровень складанасці серада
Часта пытаюцца ў MAQ Лабараторыі Walmart
масіў Стэк

Пастаноўка праблемы

Магутны стэк на аснове масіва выкарыстоўваецца ў выпадках "стэк поўны". Тут стары масіў замяняецца новым большым. Памер новага масіва вырашаецца з выкарыстаннем гэтых дзвюх стратэгій-

  • Шчыльная стратэгія - у гэтым выпадку пастаянная сума, напрыклад, 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

Тлумачэнне: Мы выканалі асноўныя аперацыі стэка. Такім чынам, спачатку мы націснулі 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.

Тут мы выкарыстоўвалі жорсткую стратэгію, дзе кожны раз, калі нам трэба павялічыць памер стэк. Мы проста працягваем дадаваць адно і тое ж Звязанае кожны раз. Такім чынам, кожны раз, калі нам трэба дадаць дадатковы памер масіў, нам трэба скапіяваць зыходны масіў у новы масіў, а потым дадаць новы элемент. Такі падыход добры, калі нас абмяжоўвае менш месца. Але калі мы хочам палепшыць складанасць часу, нам варта пайсці на стратэгію росту.

код

Праграма 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

Праграма Java для стрыгу на аснове масіва

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), таму што мы проста штурхаем элементы ў стэк. Тут N - колькасць націскаемых элементаў. Паколькі ўсе гэтыя аперацыі з'яўляюцца O (1), гэта аперацыі з пастаянным часам. Такім чынам, выкананне гэтых аперацый на працягу N часу прывядзе да лінейнага алгарытму складанасці часу.

Касмічная складанасць

O (N), дзе N - колькасць элементаў у стэку. Таму што мы выкарысталі адзін стэк, які захоўвае N элементаў. Такім чынам, алгарытм мае лінейную складанасць прасторы.