단일 어레이에서 k 스택을 효율적으로 구현하는 방법은 무엇입니까?

난이도 중급
자주 묻는 질문 아마존 포카이트
배열 스택조회수 32

단일 배열에서 k 스택을 구현하는 새로운 데이터 구조를 설계하고 구현합니다. 새 데이터 구조는 다음 두 작업을 지원해야합니다.

  • push (element, stack_number) : 주어진 수의 요소를 푸시합니다. 스택.
  • pop (stack_number) : 주어진 수의 스택에서 최상위 요소를 튀어 나옵니다.

단일 어레이에서 k 스택을 효율적으로 구현하는 방법은 무엇입니까?

입력 

푸시 (15, 2)
푸시 (45, 2)
푸시 (17, 1)
푸시 (49, 1)
푸시 (39, 1)
푸시 (11, 0)
푸시 (9, 0)
푸시 (7, 0)
팝 (2)
팝 (1)
팝 (0)

산출

스택 2:45에서 팝된 요소
스택 1:39에서 팝된 요소
스택 0:7에서 팝된 요소

입력 

푸시 (100, 1)
푸시 (200, 0)
푸시 (300, 0)
팝 (1)
팝 (0)

산출 

스택 1:100에서 팝된 요소
스택 0:300에서 팝된 요소

단일 어레이에서 k 스택을 효율적으로 구현하는 알고리즘

  1. 만들기 정렬 arr []는 스택의 요소를 저장하고 top []은 모든 스택의 최상위 요소의 인덱스를 저장하고 next []는 모든 스택의 다음 요소의 업데이트를 유지합니다.
  2. 자유 목록의 시작 인덱스를 저장할 자유 변수를 만듭니다.
  3. top []의 모든 값을 -1로 이동하고 next []의 값을 index + 1로 설정합니다.
  4. 요소와 스택 번호를 매개 변수로 받아들이는 함수 push ()를 생성하고 주어진 번호의 스택이 가득 찼는 지 확인하고“Stack Overflow”를 출력하고 반환합니다.
  5. 그렇지 않으면 변수를 초기화하고 i라고 말하고 무료로 업데이트하십시오. next (i), next (i)는 주어진 숫자의 스택의 맨 위, 주어진 숫자의 스택의 맨 위는 i로 업데이트하고 마지막으로 인덱스 i에서 배열의 요소를 푸시합니다.
  6. 스택 번호를 매개 변수로 받아들이는 함수 pop ()을 생성하고 주어진 번호의 스택이 비어 있는지 확인하고“Stack Underflow”를 출력하고 반환합니다.
  7. 그렇지 않으면 변수를 초기화하고 i라고 말하고 주어진 숫자 스택의 맨 위로 업데이트합니다. 주어진 숫자의 스택 상단을 next (i), next (i)를 free, free, free, 마지막으로 index I에있는 배열의 요소로 업데이트합니다.

단일 배열에서 k 스택을 효율적으로 구현하는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
class newStack{ 
    int *arr;   
    int *top;   
    int *next;  
    
    int n, k; 
    int free; 
public: 
    
    newStack(int k, int n); 
  
    bool isFull(){  
        return(free == -1);  
    } 
  
    void push(int item, int sn); 
  
    int pop(int sn); 
  
    bool isEmpty(int sn){  
        return (top[sn] == -1); 
    } 
}; 
  
newStack::newStack(int k1, int n1){ 
    
    k = k1, n = n1; 
    arr = new int[n]; 
    top = new int[k]; 
    next = new int[n]; 
  
    for(int i = 0; i < k; i++) 
        top[i] = -1; 
  
    free = 0; 
    for(int i=0; i<n-1; i++) 
        next[i] = i+1; 
    next[n-1] = -1; 
} 
  
void newStack::push(int item, int sn){ 
    
    if(isFull()){ 
        cout << "\nStack Overflow\n"; 
        return; 
    } 
  
    int i = free;     
  
    free = next[i]; 
  
    next[i] = top[sn]; 
    top[sn] = i; 
  
    arr[i] = item; 
} 
  
int newStack::pop(int sn){ 
    
    if(isEmpty(sn)){ 
         cout<<"\nStack Underflow\n"; 
         return INT_MAX; 
    } 
  
    int i = top[sn]; 
  
    top[sn] = next[i];  
  
    next[i] = free; 
    free = i; 
  
    return arr[i]; 
} 
  
int main(){ 
    
    int k = 3, n = 10; 
    newStack ks(k, n); 
  
    ks.push(15, 2); 
    ks.push(45, 2); 
  
    ks.push(17, 1); 
    ks.push(49, 1); 
    ks.push(39, 1); 
  
    ks.push(11, 0); 
    ks.push(9, 0); 
    ks.push(7, 0); 
  
    cout << "Popped element from stack 2 : " << ks.pop(2) << endl; 
    cout << "Popped element from stack 1 : " << ks.pop(1) << endl; 
    cout << "Popped element from stack 0 : " << ks.pop(0) << endl; 
  
    return 0; 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

단일 어레이에서 k 스택을 효율적으로 구현하는 Java 프로그램

class kstack{ 
    
    static class newStack{ 
        int arr[];   
        int top[];   
        int next[];  
        
        int n, k; 
        int free; 
  
        newStack(int k1, int n1){ 
            
            k = k1; 
            n = n1; 
            arr = new int[n]; 
            top = new int[k]; 
            next = new int[n]; 
  
            for(int i = 0; i < k; i++) 
                top[i] = -1; 
  
            free = 0; 
            for(int i = 0; i < n - 1; i++) 
                next[i] = i + 1; 
            next[n - 1] = -1;
        } 
  
        boolean isFull(){ 
            return (free == -1); 
        } 
  
        void push(int item, int sn){ 
            
            if(isFull()){ 
                System.out.println("Stack Overflow"); 
                return; 
            } 
  
            int i = free; 
  
            free = next[i]; 
  
            next[i] = top[sn]; 
            top[sn] = i; 
  
            arr[i] = item; 
        } 
  
        int pop(int sn){ 
            
            if(isEmpty(sn)){ 
                System.out.println("Stack Underflow"); 
                return Integer.MAX_VALUE; 
            } 
  
            int i = top[sn]; 
  
            top[sn] = next[i]; 
  
            next[i] = free; 
            free = i; 
  
            return arr[i]; 
        } 
  
        boolean isEmpty(int sn){ 
            return (top[sn] == -1); 
        } 
  
    } 
  
    public static void main(String[] args){ 
        
        int k = 3, n = 10; 
          
        newStack ks = new newStack(k, n); 
  
        ks.push(15, 2); 
        ks.push(45, 2); 
  
        ks.push(17, 1); 
        ks.push(49, 1); 
        ks.push(39, 1); 
  
        ks.push(11, 0); 
        ks.push(9, 0); 
        ks.push(7, 0); 
  
        System.out.println("Popped element from stack 2 : " + ks.pop(2)); 
        System.out.println("Popped element from stack 1 : " + ks.pop(1)); 
        System.out.println("Popped element from stack 0 : " + ks.pop(0)); 
    } 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

복잡성 분석

시간 복잡성 : push ()와 pop ()은 일정한 시간, 즉 O (1)을 사용합니다. top 및 next를 유지하려면 각각 O (k) 및 O (n) 시간이 필요합니다.

공간 복잡성 : O (n) 여기서 n은 요소가 저장됩니다.

참조

Translate »