با استفاده از Stack یک رشته را معکوس کنید


سطح دشواری ساده
اغلب در همبستگی Capgemini تحویل کالا متعصبان فورکایت
پشته رشته

ما داده ایم رشته s از طول n که شامل حروف کوچک ، حروف بزرگ ، عدد صحیح و برخی از نمادهای خاص است. رشته داده شده را با استفاده از آن معکوس کنید پشته. برای درک بهتر چند نمونه را مشاهده می کنیم.

با استفاده از Stack یک رشته را معکوس کنید

مثال

ورودی 

s = "TutorialCup"

تولید 

puClairotuT

ورودی

s = "پشته"

تولید

kcatS

با استفاده از پشته

الگوریتم معکوس کردن یک رشته با استفاده از Stack

  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 کاراکتر از فضای موجود در پشته استفاده کردیم.

بدون استفاده از پشته

الگوریتم معکوس کردن یک رشته با استفاده از 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

برنامه جاوا

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) زیرا ما از فضای اضافی ثابت استفاده می کنیم.

منابع