ປີ້ນກັບຄືນສະຕິງໂດຍໃຊ້ Stack


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Capgemini ເດລີ ສະ ເໜ່ ສີ່ພັນ
Stack string

ພວກເຮົາໄດ້ມອບໃຫ້ string s ຂອງຄວາມຍາວ n ເຊິ່ງປະກອບດ້ວຍຕົວອັກສອນໃຫຍ່, ຕົວອັກສອນໃຫຍ່, ຕົວເລກ, ແລະບາງສັນຍາລັກພິເສດ. ປີ້ນກັບສາຍທີ່ໃຫ້ໂດຍໃຊ້ stack. ຂໍໃຫ້ເບິ່ງບາງຕົວຢ່າງເພື່ອຄວາມເຂົ້າໃຈດີຂື້ນ.

ປີ້ນກັບຄືນສະຕິງໂດຍໃຊ້ Stack

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ 

s =“ TutorialCup”

ຜົນຜະລິດ 

puClairotuT

ການປ້ອນຂໍ້ມູນ

s =“ ສະເຕກ”

ຜົນຜະລິດ

kcatS

ການໃຊ້ Stack

ສູດການຄິດໄລ່ ສຳ ລັບການປ່ຽນເສັ້ນເຊືອກໂດຍໃຊ້ Stack

  1. ເລີ່ມຕົ້ນເສັ້ນຄວາມຍາວ n.
  2. ສ້າງ stack ຂອງຂະຫນາດດຽວກັນເພື່ອເກັບຮັກສາຕົວອັກສອນ.
  3. ລອກເອົາເຊືອກແລະຍູ້ແຕ່ລະຄົນແລະທຸກໆລັກສະນະເຂົ້າໄປໃນ stack ແຕ່ລະຄົນ.
  4. Traverse ອີກເທື່ອຫນຶ່ງແລະເລີ່ມຕົ້ນ popping ລັກສະນະອອກແລະ concatenate ໃຫ້ເຂົາເຈົ້າຮ່ວມກັນເຂົ້າໄປໃນຊ່ອຍແນ່.
  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

ໂຄງການ Java

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.

ໂດຍບໍ່ຕ້ອງໃຊ້ Stack

ສູດການຄິດໄລ່ ສຳ ລັບການປ່ຽນເສັ້ນເຊືອກໂດຍໃຊ້ Stack

  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

ໂຄງການ Java

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການປ່ຽນສາຍເຊືອກໂດຍໃຊ້ Stack

ຄວາມສັບສົນທີ່ໃຊ້ເວລາ: O (n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຕົວອັກສອນໃນສາຍ.

ອະວະກາດ: O (1) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມທີ່ຄົງທີ່.

ເອກະສານ