Рубрики

Стек | Набор 3 (перевернуть строку, используя стек)

Получив строку, переверните ее, используя стек. Например, «GeeksQuiz» следует преобразовать в «ziuQskeeG».

Ниже приведен простой алгоритм для обращения строки с использованием стека.

1) Create an empty stack.
2) One by one push all characters of string to stack.
3) One by one pop all characters from stack and put 
   them back to string.

Следующие программы реализуют вышеуказанный алгоритм.

C ++

// Программа CPP для обращения строки с использованием стека
#include <bits/stdc++.h>

using namespace std;

  
// Структура для представления стека

class Stack 

    public:

    int top; 

    unsigned capacity; 

    char* array; 

}; 

  
// функция для создания стека заданного
// вместимость. Инициализирует размер стека как 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; 

  
// стек заполнен, когда вершина равна последнему индексу

int isFull(Stack* stack) 

{ return stack->top == stack->capacity - 1; } 

  
// Стек пуст, когда вершина равна -1

int isEmpty(Stack* stack) 

{ return stack->top == -1; } 

  
// Функция для добавления элемента в стек.
// увеличивает вершину на 1

void push(Stack* stack, char item) 

    if (isFull(stack)) 

        return

    stack->array[++stack->top] = item; 

  
// Функция для удаления элемента из стека.
// Уменьшается вершина на 1

char pop(Stack* stack) 

    if (isEmpty(stack)) 

        return -1; 

    return stack->array[stack->top--]; 

  
// стековая функция для обращения строки

void reverse(char str[]) 

    // Создать стек емкости

    // равно длине строки

    int n = strlen(str); 

    Stack* stack = createStack(n); 

  

    // Поместить все символы строки в стек

    int i; 

    for (i = 0; i < n; i++) 

        push(stack, str[i]); 

  

    // Высовываем все символы строки и

    // положить их обратно на ул

    for (i = 0; i < n; i++) 

        str[i] = pop(stack); 

  
// Код драйвера

int main() 

    char str[] = "GeeksQuiz"

  

    reverse(str); 

    cout << "Reversed string is " << str; 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C-программа для обращения строки с использованием стека
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

  
// Структура для представления стека

struct Stack

{

    int top;

    unsigned capacity;

    char* array;

};

  
// функция для создания стека заданного
// вместимость. Инициализирует размер стека как 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;

}

  
// стек заполнен, когда вершина равна последнему индексу

int isFull(struct Stack* stack)

{ return stack->top == stack->capacity - 1; }

  
// Стек пуст, когда вершина равна -1

int isEmpty(struct Stack* stack)

{ return stack->top == -1; }

  
// Функция для добавления элемента в стек.
// увеличивает вершину на 1

void push(struct Stack* stack, char item)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = item;

}

  
// Функция для удаления элемента из стека.
// Уменьшается вершина на 1

char pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return INT_MIN;

    return stack->array[stack->top--];

}

  
// стековая функция для обращения строки

void reverse(char str[])

{

    // Создать стек емкости

    // равно длине строки

    int n = strlen(str);

    struct Stack* stack = createStack(n);

  

    // Поместить все символы строки в стек

    int i;

    for (i = 0; i < n; i++)

        push(stack, str[i]);

  

    // Высовываем все символы строки и

    // положить их обратно на ул

    for (i = 0; i < n; i++)

        str[i] = pop(stack);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char str[] = "GeeksQuiz";

  

    reverse(str);

    printf("Reversed string is %s", str);

  

    return 0;

}

Джава

/ * 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 str)

    {

        // Создать стек емкости

        // равно длине строки

        int n = str.length();

        Stack obj = new Stack(n);

          

        // Нажмите все символы строки

        // укладывать

        int i;

        for (i = 0; i < n; i++)

        obj.push(str.charAt(i));

      

        // Высовываем все символы строки

        // и вернуть их обратно в str

        for (i = 0; i < n; i++)

        

            char ch = obj.pop();

            str.setCharAt(i,ch);

        }

    

      

    // функция драйвера

    public static void main(String args[])

    {

        // создаем новую строку

        StringBuffer s= new StringBuffer("GeeksQuiz");

          

        // вызов метода обратного

        reverse(s);

          

        // выводим обратную строку

        System.out.println("Reversed string is " + s);

    }

}

питон

# Python программа для обращения строки с использованием стека

  
# Функция для создания пустого стека.
# Инициализирует размер стека как 0

def createStack():

    stack=[]

    return stack

  
# Функция для определения размера стека

def size(stack):

    return len(stack)

  
# Стек пуст, если размер равен 0

def isEmpty(stack):

    if size(stack) == 0:

        return true

  
# Функция для добавления элемента в стек.
# Увеличивает размер на 1

def push(stack,item):

    stack.append(item)

  
# Функция удаления элемента из стека.
# Уменьшает размер на 1

def pop(stack):

    if isEmpty(stack): return

    return stack.pop()

  
# Основанная на стеке функция для обращения строки

def reverse(string):

    n = len(string)

      

    # Создать пустой стек

    stack = createStack()

  

    # Вставить все символы строки в стек

    for i in range(0,n,1):

        push(stack,string[i])

  

    # Делаем строку пустой, так как все

    # символы сохраняются в стеке

    string=""

  

    # Вставьте все символы строки и

    # положить их обратно в строку

    for i in range(0,n,1):

        string+=pop(stack)

          

    return string

      
# Драйверная программа для проверки вышеуказанных функций

string="GeeksQuiz"

string = reverse(string)

print("Reversed string is " + string)

  
# Этот код предоставлен Sunny Karira

C #

/ * C # программа для реверса
Строка с использованием стека * /

using System;

using System.Text;

// стек

class Stack

{

    public int size;

    public int top;

    public char[] a; 

  

    // функция для проверки, если стек пуст

    public Boolean isEmpty()

    {

        return (top < 0);

    }

      

    public Stack(int n)

    {

        top = -1;

        size = n;

        a = new char[size];

    }

  

    // функция для вставки элемента в стек

    public Boolean push(char x)

    {

        if (top >= size)

        {

            Console.WriteLine("Stack Overflow");

            return false;

        }

        else

        {

            a[++top] = x;

            return true;

        }

    }

  

    // функция для извлечения элемента из стека

    public char pop()

    {

        if (top < 0)

        {

            Console.WriteLine("Stack Underflow");

            return ' ';

        }

        else

        {

            char x = a[top--];

            return x;

        }

    }

}

  

class GFG

{

    // функция для обращения строки

    public static void reverse(StringBuilder str)

    {

        // Создать стек емкости

        // равно длине строки

        int n = str.Length;

        Stack obj = new Stack(n);

          

        // Нажмите все символы строки

        // укладывать

        int i;

        for (i = 0; i < n; i++)

        obj.push(str[i]);

      

        // Высовываем все символы строки

        // и вернуть их обратно в str

        for (i = 0; i < n; i++)

        

            char ch = obj.pop();

            str[i] = ch;

        }

    

      

    // Код драйвера

    public static void Main(String []args)

    {

        // создаем новую строку

        StringBuilder s = new StringBuilder("GeeksQuiz");

          

        // вызов метода обратного

        reverse(s);

          

        // выводим обратную строку

        Console.WriteLine("Reversed string is " + s);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Reversed string is ziuQskeeG


Сложность времени:
O (n) где n — количество символов в стеке.
Вспомогательное пространство: O (n) для стека.

Строка также может быть перевернута без использования вспомогательного пробела. После программ на C, Java, C # и Python реализовать реверс без использования стека.

C ++

// C ++ программа для обращения строки без использования стека
#include <bits/stdc++.h>

using namespace std;

  
// Утилита для замены двух символов

void swap(char *a, char *b) 

    char temp = *a; 

    *a = *b; 

    *b = temp; 

  
// стековая функция для обращения строки

void reverse(char str[]) 

    // получаем размер строки

    int n = strlen(str), i; 

  

    for (i = 0; i < n/2; i++) 

        swap(&str[i], &str[n-i-1]); 

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

    char str[] = "abc"

  

    reverse(str); 

    cout<<"Reversed string is "<< str; 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C-программа для обращения строки без использования стека
#include <stdio.h>
#include <string.h>

  
// Утилита для замены двух символов

void swap(char *a, char *b)

{

    char temp = *a;

    *a = *b;

    *b = temp;

}

  
// стековая функция для обращения строки

void reverse(char str[])

{

    // получаем размер строки

    int n = strlen(str), i;

  

    for (i = 0; i < n/2; i++)

        swap(&str[i], &str[n-i-1]);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char str[] = "abc";

  

    reverse(str);

    printf("Reversed string is %s", str);

  

    return 0;

}

Джава

// Java программа для обращения строки без использования стека

public class GFG {

// Утилита для замены двух символов

  

    static void swap(char a[], int index1, int index2) {

        char temp = a[index1];

        a[index1] = a[index2];

        a[index2] = temp;

    }

  
// стековая функция для обращения строки

    static void reverse(char str[]) {

        // получаем размер строки

        int n = str.length, i;

  

        for (i = 0; i < n / 2; i++) {

            swap(str, i, n - i - 1);

        }

    }

  
// Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) {

        char str[] = "abc".toCharArray();

  

        reverse(str);

        System.out.printf("Reversed string is " + String.valueOf(str));

    }

}
// Этот код предоставлен 29AjayKumar

питон

# Python программа для обращения строки без стека

  
# Функция для обращения строки

def reverse(string):

    string = string[::-1]

    return string

  
# Драйверная программа для проверки вышеуказанных функций

string = "abc"

string = reverse(string)

print("Reversed string is " + string)

  
# Этот код предоставлен Sunny Karira

C #

// C # программа для обращения строки без использования стека

using System;

public class GFG { 

// Утилита для замены двух символов

  

    static void swap(char []a, int index1, int index2) { 

        char temp = a[index1]; 

        a[index1] = a[index2]; 

        a[index2] = temp; 

    

  
// стековая функция для обращения строки

    static void reverse(char []str) { 

        // получаем размер строки

        int n = str.Length, i; 

  

        for (i = 0; i < n / 2; i++) { 

            swap(str, i, n - i - 1); 

        

    

  
// Программа драйвера для проверки вышеуказанных функций

    public static void Main() { 

        char []str = "abc".ToCharArray(); 

  

        reverse(str); 

        Console.WriteLine("Reversed string is " + String.Join("",str)); 

    


// Этот код предоставлен PrinciRaj1992


Выход:

Reversed string is cba

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Стек | Набор 3 (перевернуть строку, используя стек)

0.00 (0%) 0 votes