스택을 사용하여 문자열 반전

난이도 쉽게
자주 묻는 질문 수행자 캡 제미니 배달 광신자 포카이트
스택 끈조회수 70

우리는 현 소문자, 대문자, 정수 및 일부 특수 기호를 포함하는 길이 n의 s. 다음을 사용하여 주어진 문자열을 뒤집습니다. 스택. 더 나은 이해를 위해 몇 가지 예를 살펴 보겠습니다.

스택을 사용하여 문자열 반전핀

예

입력 

s =“TutorialCup”

산출 

푸클라이로투

입력

s = "스택"

산출

kcatS

스택 사용

스택을 사용하여 문자열을 반전하는 알고리즘

  1. 길이가 n 인 문자열을 초기화합니다.
  2. 동일한 크기의 스택을 만들어 문자를 저장합니다.
  3. 문자열을 가로 질러 각각의 모든 문자를 하나씩 스택으로 밀어 넣습니다.
  4. 다시 트래버스하여 문자를 꺼내어 문자열로 연결합니다.
  5. 반전 된 문자열을 인쇄합니다.

실시

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){
    
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1; 
}  
  
void push(Stack* stack, char item){  
    if (isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){
    if (isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  
  
void reverse(char s[]){  
    int n = strlen(s);  
    Stack* stack = createStack(n);  
  
    int i;  
    for(i = 0; i < n; i++){  
        push(stack, s[i]); 
    }    
  
    for(i = 0; i < n; i++){  
        s[i] = pop(stack);
    }    
}  
  
int main(){  
    char s[] = "TutorialCup";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}
puClairotuT

자바 프로그램

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return (top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if (top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
} 
  
  
class Main{ 
    public static void reverse(StringBuffer s){ 
        int n = s.length(); 
        Stack obj = new Stack(n); 
          
        int i; 
        for(i = 0; i < n; i++){ 
            obj.push(s.charAt(i));
        }    
      
        for(i = 0; i < n; i++){  
            char ch = obj.pop(); 
            s.setCharAt(i,ch); 
        } 
    }  
      
    public static void main(String args[]){ 
         
        StringBuffer s= new StringBuffer("TutorialCup"); 
          
        reverse(s); 
          
        System.out.println(s); 
    } 
}
puClairotuT

복잡성 분석

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

보조 공간 : O (n) n 문자를 저장하기 위해 스택의 공간을 사용했기 때문입니다.

스택을 사용하지 않고

스택을 사용하여 문자열을 반전하는 알고리즘

  1. 길이가 n 인 문자열을 초기화합니다.
  2. 길이의 절반이 될 때까지 문자열을 가로 질러 현재 인덱스의 문자를 길이 – 현재 인덱스 – 1 위치의 문자로 바꿉니다.
  3. 문자열을 인쇄하십시오.

실시

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void swap(char *a, char *b){  
    char temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
void reverse(char s[]){  
      
    int n = strlen(s), i;  
  
    for (i = 0; i < n/2; i++)  
        swap(&s[i], &s[n-i-1]);  
}  
  
int main(){  
    char s[] = "animatedworld";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}
dlrowdetamina

자바 프로그램

class stringRev{ 

    static void swap(char a[], int index1, int index2){ 
        char temp = a[index1]; 
        a[index1] = a[index2]; 
        a[index2] = temp; 
    } 
  
    static void reverse(char s[]){ 
    
        int n = s.length, i; 
  
        for(i = 0; i < n/2; i++) { 
            swap(s, i, n-i-1); 
        } 
    } 
  
    public static void main(String[] args){
        
        char s[] = "animatedworld".toCharArray(); 
  
        reverse(s); 
        System.out.printf(String.valueOf(s)); 
        
    } 
}
dlrowdetamina

스택을 사용하여 문자열 반전을위한 복잡성 분석

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

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용하기 때문입니다.

참조

Translate »