در این مطلب، روش «معکوس کردن رشته» (Reverse) با استفاده از «پشته» (Stack) آموزش داده شده است. برای مثال، هدف آن است که «GeeksQuiz» به «ziuQskeeG» تغییر پیدا کند. در ادامه، یک الگوریتم ساده برای معکوس کردن رشته با استفاده از پشته ارائه و سپس، پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

روش اول معکوس کردن رشته با پشته

1. یک پشته خالی بساز.
2. یکی یکی همه کاراکترهای رشته را در پشته Push کن.
3. یکی یکی همه کاراکترها را از پشته Pop کن و آن‌ها را مجددا در رشته قرار بده.

برنامه معکوس کردن رشته با پشته در ++C

// CPP program to reverse a string using stack  
#include <bits/stdc++.h> 
using namespace std; 
  
// A structure to represent a stack  
class Stack  
{  
    public: 
    int top;  
    unsigned capacity;  
    char* array;  
};  
  
// function to create a stack of given  
// capacity. It initializes size of stack as 0  
Stack* createStack(unsigned capacity)  
{  
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
// Stack is full when top is equal to the last index  
int isFull(Stack* stack)  
{ return stack->top == stack->capacity - 1; }  
  
// Stack is empty when top is equal to -1  
int isEmpty(Stack* stack)  
{ return stack->top == -1; }  
  
// Function to add an item to stack.  
// It increases top by 1  
void push(Stack* stack, char item)  
{  
    if (isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
// Function to remove an item from stack.  
// It decreases top by 1  
char pop(Stack* stack)  
{  
    if (isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  
  
// A stack based function to reverse a string  
void reverse(char str[])  
{  
    // Create a stack of capacity  
    //equal to length of string  
    int n = strlen(str);  
    Stack* stack = createStack(n);  
  
    // Push all characters of string to stack  
    int i;  
    for (i = 0; i < n; i++)  
        push(stack, str[i]);  
  
    // Pop all characters of string and  
    // put them back to str  
    for (i = 0; i < n; i++)  
        str[i] = pop(stack);  
}  
  
// Driver code  
int main()  
{  
    char str[] = "GeeksQuiz";  
  
    reverse(str);  
    cout << "Reversed string is " << str;  
  
    return 0;  
}  
  
// This code is contributed by rathbhupendra

برنامه معکوس کردن رشته با پشته در C

// C program to reverse a string using stack 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <limits.h> 
  
// A structure to represent a stack 
struct Stack 
{ 
    int top; 
    unsigned capacity; 
    char* array; 
}; 
  
// function to create a stack of given  
// capacity. It initializes size of stack as 0 
struct Stack* createStack(unsigned capacity) 
{ 
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); 
    stack->capacity = capacity; 
    stack->top = -1; 
    stack->array = (char*) malloc(stack->capacity * sizeof(char)); 
    return stack; 
} 
  
// Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ return stack->top == stack->capacity - 1; } 
  
// Stack is empty when top is equal to -1 
int isEmpty(struct Stack* stack) 
{ return stack->top == -1; } 
  
// Function to add an item to stack.  
// It increases top by 1 
void push(struct Stack* stack, char item) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = item; 
} 
  
// Function to remove an item from stack.  
// It decreases top by 1 
char pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top--]; 
} 
  
// A stack based function to reverse a string 
void reverse(char str[]) 
{ 
    // Create a stack of capacity  
    //equal to length of string 
    int n = strlen(str); 
    struct Stack* stack = createStack(n); 
  
    // Push all characters of string to stack 
    int i; 
    for (i = 0; i < n; i++) 
        push(stack, str[i]); 
  
    // Pop all characters of string and  
    // put them back to str 
    for (i = 0; i < n; i++) 
        str[i] = pop(stack); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    char str[] = "GeeksQuiz"; 
  
    reverse(str); 
    printf("Reversed string is %s", str); 
  
    return 0; 
} 

برنامه معکوس کردن رشته با پشته در جاوا

/* Java program to reverse  
String using Stack */
      
import java.util.*; 
  
//stack 
class Stack 
{ 
    int size; 
    int top; 
    char[] a;  
  
    //function to check if stack is empty 
    boolean isEmpty() 
    { 
        return (top < 0); 
    } 
      
    Stack(int n) 
    { 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    //function to push element in Stack 
    boolean push(char x) 
    { 
        if (top >= size) 
        { 
        System.out.println("Stack Overflow"); 
        return false; 
        } 
        else
        { 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    //function to pop element from stack 
    char pop() 
    { 
        if (top < 0) 
        { 
        System.out.println("Stack Underflow"); 
        return 0; 
        } 
        else
        { 
            char x = a[top--]; 
            return x; 
        } 
    } 
} 
  
  
// Driver code 
class Main 
{ 
    //function to reverse the string 
    public static void reverse(StringBuffer str) 
    { 
        // Create a stack of capacity  
        // equal to length of string 
        int n = str.length(); 
        Stack obj = new Stack(n); 
          
        // Push all characters of string  
        // to stack 
        int i; 
        for (i = 0; i < n; i++) 
        obj.push(str.charAt(i)); 
      
        // Pop all characters of string  
        // and put them back to str 
        for (i = 0; i < n; i++) 
        {  
            char ch = obj.pop(); 
            str.setCharAt(i,ch); 
        } 
    }  
      
    //driver function 
    public static void main(String args[]) 
    { 
        //create a new string 
        StringBuffer s= new StringBuffer("GeeksQuiz"); 
          
        //call reverse method 
        reverse(s); 
          
        //print the reversed string 
        System.out.println("Reversed string is " + s); 
    } 
} 

برنامه معکوس کردن رشته با پشته در پایتون

# Python program to reverse a string using stack 
  
# Function to create an empty stack.  
# It initializes size of stack as 0 
def createStack(): 
    stack=[] 
    return stack 
  
# Function to determine the size of the stack 
def size(stack): 
    return len(stack) 
  
# Stack is empty if the size is 0 
def isEmpty(stack): 
    if size(stack) == 0: 
        return true 
  
# Function to add an item to stack .  
# It increases size by 1  
def push(stack,item): 
    stack.append(item) 
  
#Function to remove an item from stack.  
# It decreases size by 1 
def pop(stack): 
    if isEmpty(stack): return
    return stack.pop() 
  
# A stack based function to reverse a string 
def reverse(string): 
    n = len(string) 
      
    # Create a empty stack 
    stack = createStack() 
  
    # Push all characters of string to stack 
    for i in range(0,n,1): 
        push(stack,string[i]) 
  
    # Making the string empty since all  
    #characters are saved in stack  
    string="" 
  
    # Pop all characters of string and  
    # put them back to string 
    for i in range(0,n,1): 
        string+=pop(stack) 
          
    return string 
      
# Driver program to test above functions 
string="GeeksQuiz"
string = reverse(string) 
print("Reversed string is " + string) 
  
# This code is contributed by Sunny Karira

خروجی:

Reversed string is ziuQskeeG

اگر تعداد کاراکترهای موجود در رشته n باشد، پیچیدگی زمانی این روش از درجه (O(n است. «فضای کمکی» (Auxiliary Space) برای پشته نیز از درجه (O(n است.

روش دوم برای برنامه معکوس کردن رشته با پشته

یک رشته را می‌توان بدون استفاده از فضای کمکی نیز معکوس کرد. در ادامه، کدهای پیاده‌سازی برنامه معکوس کردن پشته بدون استفاده از فضای کمکی، ارائه شده است.

برنامه معکوس کردن رشته با پشته در ++C

// C++ program to reverse a string without using stack  
#include <bits/stdc++.h> 
using namespace std; 
  
// A utility function to swap two characters  
void swap(char *a, char *b)  
{  
    char temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
// A stack based function to reverse a string  
void reverse(char str[])  
{  
    // get size of string  
    int n = strlen(str), i;  
  
    for (i = 0; i < n/2; i++)  
        swap(&str[i], &str[n-i-1]);  
}  
  
// Driver program to test above functions  
int main()  
{  
    char str[] = "abc";  
  
    reverse(str);  
    cout<<"Reversed string is "<< str;  
  
    return 0;  
}  
  
//This is code is contributed by rathbhupendra 

برنامه معکوس کردن رشته با پشته در C

// C program to reverse a string without using stack 
#include <stdio.h> 
#include <string.h> 
  
// A utility function to swap two characters 
void swap(char *a, char *b) 
{ 
    char temp = *a; 
    *a = *b; 
    *b = temp; 
} 
  
// A stack based function to reverse a string 
void reverse(char str[]) 
{ 
    // get size of string 
    int n = strlen(str), i; 
  
    for (i = 0; i < n/2; i++) 
        swap(&str[i], &str[n-i-1]); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    char str[] = "abc"; 
  
    reverse(str); 
    printf("Reversed string is %s", str); 
  
    return 0; 
}

برنامه معکوس کردن رشته با پشته در جاوا

// Java program to reverse a string without using stack  
public class GFG { 
// A utility function to swap two characters  
  
    static void swap(char a[], int index1, int index2) { 
        char temp = a[index1]; 
        a[index1] = a[index2]; 
        a[index2] = temp; 
    } 
  
// A stack based function to reverse a string  
    static void reverse(char str[]) { 
        // get size of string  
        int n = str.length, i; 
  
        for (i = 0; i < n / 2; i++) { 
            swap(str, i, n - i - 1); 
        } 
    } 
  
// Driver program to test above functions  
    public static void main(String[] args) { 
        char str[] = "abc".toCharArray(); 
  
        reverse(str); 
        System.out.printf("Reversed string is " + String.valueOf(str)); 
    } 
} 
// This code is contributed by 29AjayKumar

برنامه معکوس کردن رشته با پشته در پایتون

# Python program to reverse a string without stack 
  
# Function to reverse a string 
def reverse(string): 
    string = string[::-1] 
    return string 
  
# Driver program to test above functions 
string = "abc"
string = reverse(string) 
print("Reversed string is " + string) 
  
# This code is contributed by Sunny Karira

برنامه معکوس کردن رشته با پشته در #C

// C# program to reverse a string without using stack  
using System; 
public class GFG {  
// A utility function to swap two characters  
  
    static void swap(char []a, int index1, int index2) {  
        char temp = a[index1];  
        a[index1] = a[index2];  
        a[index2] = temp;  
    }  
  
// A stack based function to reverse a string  
    static void reverse(char []str) {  
        // get size of string  
        int n = str.Length, i;  
  
        for (i = 0; i < n / 2; i++) {  
            swap(str, i, n - i - 1);  
        }  
    }  
  
// Driver program to test above functions  
    public static void Main() {  
        char []str = "abc".ToCharArray();  
  
        reverse(str);  
        Console.WriteLine("Reversed string is " + String.Join("",str));  
    }  
}  
// This code is contributed by PrinciRaj1992

خروجی

خروجی قطعه کدهای بالا، به صورت زیر است.

Reversed string is cba

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• برنامه چاپ جایگشت‌های رشته — به زبان ساده
• برنامه تشخیص اعداد اول در پایتون — به زبان ساده
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده