Рубрики

Обратный стек, используя рекурсию

Напишите программу для реверсирования стека с помощью рекурсии. Вам не разрешено использовать конструкции цикла, такие как while, for..etc, и вы можете использовать только следующие функции ADT в стеке S:
IsEmpty (S),
толчок (S),
поп (S),

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

Например, пусть входной стек будет

    1  <-- top
    2
    3
    4   
First 4 is inserted at the bottom.
    4 <-- top

Then 3 is inserted at the bottom
    4 <-- top    
    3

Then 2 is inserted at the bottom
    4 <-- top    
    3 
    2
     
Then 1 is inserted at the bottom
    4 <-- top    
    3 
    2
    1

Итак, нам нужна функция, которая вставляет в конец стека, используя вышеуказанную базовую функцию стека.

void insertAtBottom ((): сначала извлекает все элементы стека и сохраняет извлеченный элемент в стеке вызовов функций с помощью рекурсии. А когда стек становится пустым, помещает новый элемент и все элементы, хранящиеся в стеке вызовов.

void reverse (): эта функция в основном использует insertAtBottom (), чтобы вытаскивать все элементы по одному и вставлять извлеченные элементы внизу.

C ++

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

using namespace std;

  
// используя std :: stack для
// стековая реализация

stack<char> st;

  
// инициализация строки для хранения
// результат обратного стека
string ns;

  
// Ниже приведена рекурсивная функция
// который вставляет элемент
// в нижней части стека.

char insert_at_bottom(char x)

{

  

    if(st.size() == 0)

    st.push(x);

  

    else

    {

          

        // Все элементы хранятся в вызове функции

        // укладываем в стек, пока не достигнем конца стека

        // Когда стек становится пустым,

        // st.size () становится 0, выше, если

        // часть выполнена и элемент

        // вставлено внизу

              

        char a = st.top();

        st.pop();

        insert_at_bottom(x);

  

        // толкаем все предметы, хранящиеся в

        // стек вызовов функций

        // как только элемент вставлен

        // внизу

        st.push(a);

    }

}

  
// Ниже приведена функция, которая
// переворачивает данный стек, используя
// insert_at_bottom ()

char reverse()

{

    if(st.size()>0)

    {

          

        // Удерживать все элементы в функции

        // Вызов стека, пока мы

        // достигаем конца стека

        char x = st.top();

        st.pop();

        reverse();

          

        // Вставляем все элементы

        // в стеке вызовов функций

        // один за другим снизу

        // к началу. Каждый предмет

        // вставлено внизу

        insert_at_bottom(x);

    }

}

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

int main()

{

      

    // вставляем элементы в

    // стек

    st.push('1');

    st.push('2');

    st.push('3');

    st.push('4');

      

    cout<<"Original Stack"<<endl;

      

    // печатаем элементы

    // оригинального стека

    cout<<"1"<<" "<<"2"<<" "

        <<"3"<<" "<<"4"

        <<endl;

      

    // функция для обратного

    // стек

    reverse();

    cout<<"Reversed Stack"

        <<endl;

      

    // сохраняем значения обратного

    // укладываем в строку для отображения

    while(!st.empty())

    {

        char p=st.top();

        st.pop();

        ns+=p;

    }

      

    // отображение перевернутого стека

    cout<<ns[3]<<" "<<ns[2]<<" "

        <<ns[1]<<" "<<ns[0]<<endl;

    return 0;

}

  
// Этот код предоставлен Гаутамом Сингхом

С

// C программа для обратного
// стек с использованием рекурсии
#include<stdio.h>
#include<stdlib.h>
#define bool int

  
// структура стекового узла

struct sNode

{

    char data;

    struct sNode *next;

};

  
// Прототипы функций

void push(struct sNode** top_ref, 

                   int new_data);

int pop(struct sNode** top_ref);

bool isEmpty(struct sNode* top);

void print(struct sNode* top);

  
// Ниже приведена рекурсивная функция
// который вставляет элемент
// в нижней части стека.

void insertAtBottom(struct sNode** top_ref,

                                 int item)

{

    if (isEmpty(*top_ref))

        push(top_ref, item);

    else

    {

  

        // Удерживать все элементы в вызове функции

        // Стек, пока мы не достигнем конца

        // стек. Когда стек становится

        // пусто, isEmpty (* top_ref) становится

        // true, выше, если часть выполнена

        // и элемент вставляется внизу

        int temp = pop(top_ref);

        insertAtBottom(top_ref, item);

  

        // Как только элемент вставлен

        // внизу, нажмите все

        // элементы, содержащиеся в функции

        // Стек вызовов

        push(top_ref, temp);

    }

}

  
// Ниже приведена функция, которая
// переворачивает данный стек, используя
// insertAtBottom ()

void reverse(struct sNode** top_ref)

{

    if (!isEmpty(*top_ref))

    {

        // Удерживать все элементы в функции

        // Вызов стека, пока мы

        // достигаем конца стека

        int temp = pop(top_ref);

        reverse(top_ref);

  

        // Вставляем все элементы (хранятся в

        // стек вызовов функций)

        // один за другим снизу

        // к началу. Каждый предмет

        // вставлено внизу

        insertAtBottom(top_ref, temp);

    }

}

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

int main()

{

    struct sNode *s = NULL;

    push(&s, 4);

    push(&s, 3);

    push(&s, 2);

    push(&s, 1);

  

    printf("\n Original Stack ");

    print(s);

    reverse(&s);

    printf("\n Reversed Stack ");

    print(s);

    return 0;

}

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

bool isEmpty(struct sNode* top)

{

    return (top == NULL)? 1 : 0;

}

  
// Функция для перемещения элемента в стек

void push(struct sNode** top_ref, 

                    int new_data)

{

      

    // выделить узел

    struct sNode* new_node =

        (struct sNode*) malloc(sizeof(struct sNode));

  

    if (new_node == NULL)

    {

        printf("Stack overflow \n");

        exit(0);

    }

  

    // вставляем данные

    new_node->data = new_data;

  

    // ссылка на старый список

    // с нового узла

    new_node->next = (*top_ref);

  

    // переместить голову в

    // указать на новый узел

    (*top_ref) = new_node;

}

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

int pop(struct sNode** top_ref)

{

    char res;

    struct sNode *top;

  

    // Если стек пуст, то ошибка

    if (*top_ref == NULL)

    {

        printf("Stack overflow \n");

        exit(0);

    }

    else

    {

        top = *top_ref;

        res = top->data;

        *top_ref = top->next;

        free(top);

        return res;

    }

}

  
// Функция для печати
// связанный список

void print(struct sNode* top)

{

    printf("\n");

    while (top != NULL)

    {

        printf(" %d ", top->data);

        top = top->next;

    }

}

Джава

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

import java.util.Stack;

  

class Test {

      

    // используя класс Stack для

    // стековая реализация

    static Stack<Character> st = new Stack<>();

      

    // Ниже приведена рекурсивная функция

    // который вставляет элемент

    // в нижней части стека.

    static void insert_at_bottom(char x)

    {

  

        if(st.isEmpty())

            st.push(x);

  

        else

        {

              

            // Все элементы хранятся в функции

            // Вызов стека до конца

            // стека Когда стек становится

            // пусто, st.size () становится 0,

            // выше, если часть выполнена и

            // элемент вставляется внизу

            char a = st.peek();

            st.pop();

            insert_at_bottom(x);

  

            // толкаем все предметы

            // в стеке вызовов функций

            // как только элемент вставлен

            // внизу

            st.push(a);

        }

    }

      

    // Ниже приведена функция, которая

    // переворачивает данный стек, используя

    // insert_at_bottom ()

    static void reverse()

    {

        if(st.size() > 0)

        {

              

            // Удерживать все элементы в функции

            // Вызов стека, пока мы

            // достигаем конца стека

            char x = st.peek();

            st.pop();

            reverse();

              

            // Вставляем все элементы

            // в стеке вызовов функций

            // один за другим снизу

            // к началу. Каждый предмет

            // вставлено внизу

            insert_at_bottom(x);

        }

    }

      

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

    public static void main(String[] args) 

    {

          

        // вставляем элементы в

        // стек

        st.push('1');

        st.push('2');

        st.push('3');

        st.push('4');

          

        System.out.println("Original Stack");

          

        System.out.println(st);

          

        // функция для обратного

        // стек

        reverse();

          

        System.out.println("Reversed Stack");

          

        System.out.println(st);

    }

}

python3

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

  
# Ниже приведена рекурсивная функция
# который вставляет элемент
# в нижней части стека.

def insertAtBottom(stack, item):

    if isEmpty(stack):

        push(stack, item)

    else:

        temp = pop(stack)

        insertAtBottom(stack, item)

        push(stack, temp)

  
# Ниже приведена функция, которая
# переворачивает данный стек
# используя insertAtBottom ()

def reverse(stack):

    if not isEmpty(stack):

        temp = pop(stack)

        reverse(stack)

        insertAtBottom(stack, temp)

  
# Ниже полный ход
# программа для тестирования выше
# функции.

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

def createStack():

    stack = []

    return stack

  
# Функция, чтобы проверить, если
# стек пуст

def isEmpty( stack ):

    return len(stack) == 0

  
# Функция нажать
# элемент в стек

def push( stack, item ):

    stack.append( item )

  
# Функция для всплывающего
# элемент из стека

def pop( stack ):

  

    # Если стек пуст

    # тогда ошибка

    if(isEmpty( stack )):

        print("Stack Underflow ")

        exit(1)

  

    return stack.pop()

  
# Функция для печати стека

def prints(stack):

    for i in range(len(stack)-1, -1, -1):

        print(stack[i], end = ' ')

    print()

  
Код водителя

  

stack = createStack()

push( stack, str(4) )

push( stack, str(3) )

push( stack, str(2) )

push( stack, str(1) )

print("Original Stack ")

prints(stack)

  
reverse(stack)

  

print("Reversed Stack ")

prints(stack)

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

C #

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

using System;

using System.Collections;

  

public class GFG 

  

    // используя класс Stack для

    // стековая реализация

    static Stack st = new Stack(); 

      

    // Ниже приведена рекурсивная функция

    // который вставляет элемент

    // в нижней части стека.

    static void insert_at_bottom(char x) 

    

  

        if(st.Count==0) 

            st.Push(x); 

  

        else

        

              

            // Все элементы хранятся в функции

            // Вызов стека до конца

            // стека Когда стек становится

            // пусто, st.size () становится 0,

            // выше, если часть выполнена и

            // элемент вставляется внизу

            char a = (char)st.Peek(); 

            st.Pop(); 

            insert_at_bottom(x); 

  

            // толкаем все предметы

            // в стеке вызовов функций

            // как только элемент вставлен

            // внизу

            st.Push(a); 

        

    

      

    // Ниже приведена функция, которая

    // переворачивает данный стек, используя

    // insert_at_bottom ()

    static void reverse() 

    

        if(st.Count > 0) 

        

              

            // Удерживать все элементы в функции

            // Вызов стека, пока мы

            // достигаем конца стека

            char x = (char)st.Peek(); 

            st.Pop(); 

            reverse(); 

              

            // Вставляем все элементы

            // в стеке вызовов функций

            // один за другим снизу

            // к началу. Каждый предмет

            // вставлено внизу

            insert_at_bottom(x); 

        

    

      

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

    public static void Main(String []args) 

    

          

        // вставляем элементы в

        // стек

        st.Push('1'); 

        st.Push('2'); 

        st.Push('3'); 

        st.Push('4'); 

          

        Console.WriteLine("Original Stack"); 

          

        foreach (char i in st)

        {

            Console.WriteLine(i);

        }

          

        // функция для обратного

        // стек

        reverse(); 

          

        Console.WriteLine("Reversed Stack"); 

        foreach (char i in st)

        {

            Console.WriteLine(i);

        }

    

  

  
// Этот код создан Арнабом Кунду


Выход:

 Original Stack 
 1  2  3  4 
 Reversed Stack 
 4  3  2  1 

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы

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

Обратный стек, используя рекурсию

0.00 (0%) 0 votes