배열이 스택 정렬 가능한지 확인


난이도 중급
자주 묻는 질문 Accenture Accolite 아마존
배열 정렬 스택

확인하십시오 정렬 무작위 순서로 1부터 n까지의 요소를 포함하는 크기 n의 배열 a []를 제공 한 스택 정렬 문제입니다. 임시를 사용하여 오름차순으로 배열 정렬 스택 이 두 가지 작업 만 수행하면

  • 배열의 시작 인덱스에있는 요소를 제거하고 스택에 저장합니다.
  • 맨 위 From 스택을 꺼내 다른 배열의 끝에 추가합니다.

스택을 사용하여 주어진 배열을 정렬 할 수 있는지 확인하십시오.

배열이 스택 정렬 가능한지 확인

입력

a [] = {4, 1, 2, 3}

산출

주어진 배열은 스택을 사용하여 정렬 할 수 있습니다.

입력

a [] = {2, 3, 1}

산출

주어진 배열은 스택을 사용하여 정렬 할 수 없습니다.

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. 배열을 정렬 할 요소를 저장할 스택을 만들고 끝을 가리키는 변수 end = 0을 만듭니다.
  3. 0에서 n-1로 이동하고 스택이 비어 있는지 확인하고 스택의 현재 인덱스에서 배열 값을 푸시합니다. 그렇지 않으면 스택의 상단을 가변 상단에 저장합니다. 상단은 end + 1과 같지만 끝을 늘리고 상단을 팝합니다. 스택이 비어 있는지 확인하십시오. 변수 top을 스택의 현재 상단으로 업데이트합니다.
  4. 스택이 비어있는 경우 스택의 현재 인덱스에서 배열 값을 푸시합니다.
  5. 그렇지 않으면 스택의 상단을 가변 상단에 저장합니다. 현재 인덱스의 배열 값이 맨 위보다 작은 지 확인하고 스택의 배열 요소를 푸시합니다. 그렇지 않으면 false를 반환합니다.
  6. true를 반환합니다.

배열이 스택 정렬 가능한지 확인하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
bool check(int a[], int n){ 
    
    stack<int> S; 
  
    int end = 0; 
  
    for(int i = 0; i < n; i++){ 
        
        if(!S.empty()){ 
            
            int top = S.top(); 
  
            while(top == end + 1){ 
                end = end + 1; 
  
                S.pop(); 
  
                if(S.empty()){ 
                    break; 
                } 
  
                top = S.top(); 
            } 
  
            if(S.empty()) { 
                S.push(a[i]); 
            } 
            
            else{ 
                top = S.top(); 
  
                if(a[i] < top){ 
                    S.push(a[i]); 
                } 
                else{ 
                    return false; 
                } 
            } 
        } 
        else{ 
            S.push(a[i]); 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    int a[] = {4, 1, 2, 3}; 
    int n = sizeof(a) / sizeof(a[0]);
    
    check(a, n)? cout<<"Given array can be sorted using stack.": cout<<"Given array can not be sorted using stack.";    
    
    return 0; 
}
Given array can be sorted using stack.

배열이 스택 정렬 가능한지 확인하기위한 Java 프로그램

import java.util.Stack; 
  
class soryArray{ 
  
    static boolean check(int a[], int n){ 
        
        Stack<Integer> S = new Stack<Integer>(); 
  
        int end = 0; 
  
        for(int i = 0; i < n; i++) { 
            if(!S.empty()){ 
                int top = S.peek(); 
  
                while(top == end + 1){ 
                    end = end + 1; 
  
                    S.pop(); 
  
                    if(S.empty()){ 
                        break; 
                    } 
  
                    top = S.peek(); 
                } 
  
                if (S.empty()) { 
                    S.push(a[i]); 
                } 
                else{ 
                    top = S.peek(); 
  
                    if(a[i] < top) { 
                        S.push(a[i]); 
                    } 
                    else{ 
                        return false; 
                    } 
                } 
            } 
            else{ 
                S.push(a[i]); 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args) { 
  
        int a[] = {4, 1, 2, 3}; 
        int n = a.length; 
  
        if(check(a, n)){ 
            System.out.println("Given array can be sorted using stack."); 
        } 
        else{ 
            System.out.println("Given array can not be sorted using stack."); 
        } 
  
    } 
}
Given array can be sorted using stack.

배열이 스택 정렬 가능한지 확인하기위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 배열의 요소 수입니다.

공간 복잡성 : O (n) n 개의 요소를 저장하기 위해 공간을 사용했기 때문입니다.

참조