성장 가능한 어레이 기반 스택

난이도 중급
자주 묻는 질문 MAQ 월마트 연구소
배열 스택조회수 90

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

확장 가능한 어레이 기반 스택은 "스택이 가득 찬"경우에 사용됩니다. 여기서 이전 어레이는 더 큰 새 어레이로 대체됩니다. 새 어레이의 크기는 다음 두 가지 전략을 사용하여 결정됩니다.

  • 엄격한 전략 –이 경우 일정한 양으로 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.

여기서 우리는 타이트한 전략을 사용했습니다. 스택. 우리는 매번 동일한 BOUND를 계속 추가합니다. 따라서 추가 크기를 추가해야 할 때마다 정렬, 원래 배열을 새 배열에 복사 한 다음 새 요소를 추가해야합니다. 이 접근 방식은 우리가 더 적은 공간으로 묶여 있다면 좋습니다. 그러나 더 나은 시간 복잡성을 원한다면 성장 전략을 따라야합니다.

암호

확장 가능한 어레이 기반 스택을위한 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

복잡성 분석

시간 복잡성

의 위에), 왜냐하면 우리는 단순히 요소를 스택으로 밀어 넣기 때문입니다. 여기서 N은 푸시되는 요소의 수입니다. 이러한 작업은 모두 O (1)이므로 일정 시간 작업입니다. 따라서 N 시간 동안 이러한 작업을 수행하면 선형 시간 복잡도 알고리즘이 생성됩니다.

공간 복잡성

의 위에), 여기서 N은 스택의 요소 수입니다. N 개의 요소를 저장하는 단일 스택을 사용했기 때문입니다. 따라서 알고리즘은 선형 공간 복잡성을 갖습니다.

균열 시스템 설계 인터뷰
Translate »