확인하십시오 정렬 무작위 순서로 1부터 n까지의 요소를 포함하는 크기 n의 배열 a []를 제공 한 스택 정렬 문제입니다. 임시를 사용하여 오름차순으로 배열 정렬 스택 이 두 가지 작업 만 수행하면
- 배열의 시작 인덱스에있는 요소를 제거하고 스택에 저장합니다.
- 맨 위 From 스택을 꺼내 다른 배열의 끝에 추가합니다.
스택을 사용하여 주어진 배열을 정렬 할 수 있는지 확인하십시오.
차례
예
입력
a [] = {4, 1, 2, 3}
산출
주어진 배열은 스택을 사용하여 정렬 할 수 있습니다.
입력
a [] = {2, 3, 1}
산출
주어진 배열은 스택을 사용하여 정렬 할 수 없습니다.
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 배열을 정렬 할 요소를 저장할 스택을 만들고 끝을 가리키는 변수 end = 0을 만듭니다.
- 0에서 n-1로 이동하고 스택이 비어 있는지 확인하고 스택의 현재 인덱스에서 배열 값을 푸시합니다. 그렇지 않으면 스택의 상단을 가변 상단에 저장합니다. 상단은 end + 1과 같지만 끝을 늘리고 상단을 팝합니다. 스택이 비어 있는지 확인하십시오. 변수 top을 스택의 현재 상단으로 업데이트합니다.
- 스택이 비어있는 경우 스택의 현재 인덱스에서 배열 값을 푸시합니다.
- 그렇지 않으면 스택의 상단을 가변 상단에 저장합니다. 현재 인덱스의 배열 값이 맨 위보다 작은 지 확인하고 스택의 배열 요소를 푸시합니다. 그렇지 않으면 false를 반환합니다.
- 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 개의 요소를 저장하기 위해 공간을 사용했기 때문입니다.
