스택 요소가 쌍으로 연속되어 있는지 확인

난이도 쉽게
자주 묻는 질문 배달 팩트 셋 포카이트
스택조회수 32

문제 정책

"스택 요소가 쌍으로 연속적인지 확인"문제는 스택 데이터 구조 정수 유형. 주어진 모든 요소가 쌍으로 연속적인지 (증가 또는 감소하는 순서로) 확인하는 함수를 만듭니다. 스택에 주어진 요소의 수가 짝수이면 다른 모든 쌍이 지정된 스택의 맨 위에 요소를 남겨 두는지 확인하십시오. 또한 프로그램 중에 주어진 스택의 요소를 유지하고 결과와 함께 인쇄하십시오.

스택 요소가 쌍으로 연속되어 있는지 확인

s = [4, 5, -2, -3, 11, 10, 5, 6, 20]
Yes

설명 : 함수 호출 [20 6 5 10 11 -3 -2 5 4] 후 컨텐츠 스택 (위부터). 스택의 요소 수가 홀수입니다. 따라서 20은 어떤 요소와도 짝을 이루지 않습니다. 그러나 다른 요소는 쌍을 이루며 연속적입니다.

s = [4, 6, 6, 7, 4, 3]
No

설명 : 함수 호출 [3 4 7 6 6 4] 후 컨텐츠 스택 (위부터). 그리고 4와 6은 2의 차이를 가지므로 연속적이지 않습니다. 따라서 결과는 아니오입니다.

스택 요소가 쌍으로 연속적인지 확인하는 알고리즘

1. Create a stack data structure of the integer type and insert/push the elements in it.
2. Create another auxiliary stack data structure of the integer type.
3. Traverse while the original stack is not empty and push the element at top of  the auxiliary stack and pop the element from the top of the original stack.
4. Create a variable result of the boolean type and set its value as true.
5. Traverse through the auxiliary stack and pop the top 2 elements in the auxiliary stack and store them in 2 integer variables.
6. Check if the absolute difference of both the integer variables is not equal to 1, update the boolean variable result as false. Push / insert both the integer variables in the original stack.
7. Check if the size of the auxiliary stack is equal to 1, Push/insert the element at the top of the auxiliary stack in the original stack.
8. Return the boolean variable result.
9. Check if the returned value is equal to true, print "Yes" else print "No".
10. Print the original stack.

이 문제에서는 확인해야 할 초기 원본 스택이 제공됩니다. 그래서 우리는 원래 스택을 잃고 싶지 않기 때문에 만들어진 보조 스택을 만듭니다. 초기 스택을 저장하고 싶지 않고 초기 스택을 수정할 수 있다면 단순히 원래 스택에서 요소를 제거 할 수 있습니다. 따라서 보조 스택은 스택 복사본 역할을합니다. 이제 보조 스택이 있으면 상단에서 2 개의 요소를 제거한 다음 연결을 확인할 수 있습니다.

암호

스택 요소가 쌍으로 연속되는지 확인하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
bool isConsecutive(stack<int> s){ 
    stack<int> aux; 
    
    while(!s.empty()){ 
        aux.push(s.top()); 
        s.pop(); 
    } 
  
    bool result = true; 
    
    while(aux.empty() > 1){ 
        int x = aux.top(); 
        aux.pop(); 
        int y = aux.top(); 
        aux.pop(); 
        
        if(abs(x - y) != 1){ 
            result = false; 
        }
  
        s.push(x); 
        s.push(y); 
    } 
  
    if(aux.size() == 1){ 
        s.push(aux.top());
    }
  
    return result; 
} 
  
int main(){ 
    stack<int> s;
    
    s.push(4); 
    s.push(5); 
    s.push(-2); 
    s.push(-3); 
    s.push(11); 
    s.push(10); 
    s.push(5); 
    s.push(6); 
    s.push(20); 
  
    if(isConsecutive(s)){ 
        cout << "Yes" << endl; 
    }
    
    else{
        cout << "No" << endl;
    }
  
    cout << "Stack content (from top)"
          " after function call\n"; 
    
    while(s.empty() == false){ 
       cout << s.top() << " "; 
       s.pop(); 
    } 
  
    return 0; 
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

스택 요소가 쌍으로 연속되는지 확인하는 Java 프로그램

import java.util.*; 

class CheckPair{ 
    
    static boolean isConsecutive(Stack<Integer> s){  
        Stack<Integer> aux = new Stack<Integer> ();  
        
        while(!s.isEmpty()){  
            aux.push(s.peek());  
            s.pop();  
        }  
      
        boolean result = true;  
        
        while(aux.size() > 1){  
            int x = aux.peek();  
            aux.pop();  
            int y = aux.peek();  
            aux.pop();  
            
            if(Math.abs(x - y) != 1){  
                result = false;  
            }
      
            s.push(x);  
            s.push(y);  
        }  
      
        if(aux.size() == 1){  
            s.push(aux.peek());
        }
      
        return result;  
    }  
      
    public static void main(String[] args){  
        Stack<Integer> s = new Stack<Integer> ();
        
        s.push(4);  
        s.push(5);  
        s.push(-2);  
        s.push(-3);  
        s.push(11);  
        s.push(10);  
        s.push(5);  
        s.push(6);  
        s.push(20);  
      
        if(isConsecutive(s)){  
            System.out.println("Yes");
        }
        
        else{
            System.out.println("No");  
        }
      
        System.out.println("Stack content (from top) after function call");  
        
        while(s.isEmpty() == false){  
            System.out.print(s.peek() + " ");  
            s.pop();  
        }  
      
    }  
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

복잡성 분석

시간 복잡성

의 위에), 여기서 N은 스택의 요소 수입니다.

공간 복잡성

의 위에), 스택을 사용하여 N 개의 요소를 저장했습니다. 따라서 선형 공간 복잡성이 달성됩니다.

Translate »