재귀를 사용하여 스택 반전

재귀 문제를 사용하는 스택을 반대로하면 스택 데이터 구조. 재귀를 사용하여 요소를 뒤집습니다. 아래 나열된 스택 기능 만 사용할 수 있습니다.

• push (element) – 스택에 요소를 삽입합니다.
• pop () – 스택 맨 위에있는 요소를 제거 / 삭제합니다.
• isEmpty () – 스택에 요소가 있는지 확인합니다.

핀

예

입력 : 5 4 3 2 1

출력 : 1 2 3 4 5

입력 : +300 200 100 XNUMX

출력 : +100 200 300 XNUMX

방법

스택과 두 개의 함수를 만듭니다. 먼저 bottom_insert () 스택의 맨 아래에 요소를 삽입하고 다른 요소를 역전() 모든 요소를 ​​팝하고 bottom_insert ()를 호출하면 스택이 반전됩니다.

재귀를 사용하는 스택 반전 알고리즘

1. 스택을 초기화하고 그 안에 요소를 푸시합니다.
2. 요소를 매개 변수로 받아들이는 스택의 맨 아래에 요소를 삽입하는 함수를 만듭니다. 스택의 크기가 0인지 확인하고 스택의 요소를 푸시합니다.
3. 그렇지 않으면 변수 a를 만들고 그 안에 스택의 맨 위를 저장합니다. 스택의 맨 위를 팝하고 함수 자체를 재귀 적으로 호출합니다. 스택에서 변수 a를 푸시합니다.
4. 마찬가지로 reverse () 함수를 만듭니다. 스택의 크기가 0보다 큰지 확인하고 변수 x를 생성 한 다음 스택의 상단을 저장합니다. 스택 상단을 팝합니다. 함수 자체를 재귀 적으로 호출합니다. 함수를 호출하여 스택 맨 아래에 요소를 삽입합니다.
5. main ()에서 reverse 함수를 호출하십시오. 문자열을 초기화합니다.
6. 스택이 비어 있지 않은 상태에서 트래버스하고 변수 p를 만들고 스택의 맨 위를 저장합니다. 스택 상단을 팝합니다. 팝된 요소를 문자열에 추가하십시오.
7. 인쇄 현.

재귀를 사용하여 스택을 반전하는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
stack<char> st; 
  
string s; 
  
char bottom_insert(char x){ 
  
    if(st.size() == 0){ 
        st.push(x); 
    }
  
    else{ 
        char a = st.top(); 
        st.pop(); 
        bottom_insert(x); 
  
        st.push(a); 
    } 
} 
  
char reverse(){ 
    
    if(st.size()>0){ 
        char x = st.top(); 
        st.pop(); 
        reverse(); 
          
        bottom_insert(x); 
    } 
} 
  
int main(){ 
      
    st.push('1'); 
    st.push('2'); 
    st.push('3'); 
    st.push('4');
    st.push('5');
      
    reverse(); 
    
    while(!st.empty()){ 
        char p=st.top(); 
        st.pop(); 
        s+=p; 
    } 
    
    cout<<"[";
    for(int i=s.size()-1; i>=0; i--){
        cout<<s[i]<<", ";
    }
    cout<<"]";
    return 0; 
}

[5, 4, 3, 2, 1]

재귀를 사용하여 스택을 되 돌리는 Java 프로그램

import java.util.Stack; 
  
class ReverseStack{ 
      
    static Stack<Character> st = new Stack<>(); 
      
    static void bottom_insert(char x){ 
  
        if(st.isEmpty()){ 
            st.push(x); 
        }    
  
        else{ 
            char a = st.peek(); 
            st.pop(); 
            bottom_insert(x); 
  
            st.push(a); 
        } 
    } 
      
    static void reverse(){
        
        if(st.size() > 0){ 
              
            char x = st.peek(); 
            st.pop(); 
            reverse(); 
              
            bottom_insert(x); 
        } 
    } 
      
    public static void main(String[] args){ 
          
        st.push('1'); 
        st.push('2'); 
        st.push('3'); 
        st.push('4'); 
        st.push('5'); 
          
        reverse(); 
        
        System.out.print(st);
        
    } 
}

[5, 4, 3, 2, 1]

복잡성 분석

시간 복잡성 : O (n * n) 여기서 n은 스택에 푸시 된 요소의 수입니다.

보조 공간 : O (n * n) n * n 추가 스택 공간을 사용하고 있기 때문입니다.

레퍼런스 1   참조 2