Transfer content from one stack to another C++

Question

I need to solve a question, she asks me to display the contents of a stack in reverse form, I thought a lot and I came to the conclusion that it is only possible to create an auxiliary stack and transferring the contents from one stack to another, so the result of the auxiliary stack would be the reversed stack.

The idea is easy, but I’m having a lot of trouble creating this auxiliary stack, I’m beginner with ADT’s and I’m breaking my head to solve this.

My code:

    #include<iostream>

using namespace std;

struct no{

    char n;
    no *prox;
};

struct pilha{

    no *topo;
};

int menu(){

    int op;
    cout << "\n1. Inserir na pilha\n";
    cout << "2. Remover da pilha\n";
    cout << "3. Imprimir pilha\n";
    cout << "4. Imprimiir pilha invertida\n";
    cout << "5. Sair\n";
    cout << "Opcao: ";
    cin >> op;
    return op;  
}
no* criarNo(){

    char num;
    cout << "Qual caractere deseja inserir: ";
    cin >> num;
    no *novo = new no;
    novo->n = num;
    novo->prox = NULL;
    return novo;
}

void inserirPilha(pilha *inicio){

    no *insere = criarNo();
    if(inicio->topo == NULL){
        inicio->topo = insere;
    }       
    else{
        insere->prox = inicio->topo;
        inicio->topo = insere;
    }   
}

void imprimirPilha(pilha *inicio){

    if(inicio->topo == NULL)
        cout << "pilha vazia\n";
    else{
        no *aux = inicio->topo;
        while(aux->prox != NULL){
            cout << aux->n << " ";
            aux = aux->prox;
        }
        cout << aux->n << " ";      
    }
}

void imprimirPilhaInvertida(pilha *inicio){

    //Função para exibir a pilha auxiliar.
}


void removerPilha(pilha *inicio){

    if(inicio->topo == NULL)
        cout << "Fila vazia\n";
    else
        inicio->topo = inicio->topo->prox;          
}


int main(){

    int opcao;
    pilha *inicio = new pilha;
    inicio->topo = NULL;
    while(true){
        opcao = menu();
        switch(opcao){
            case 1:
                inserirPilha(inicio);
                break;
            case 2:
                removerPilha(inicio);
                break;
            case 3:
                imprimirPilha(inicio);
                break;
            case 4:
                imprimirPilhaInvertida(inicio);
                break;
            case 5:
                return -1;
            default:
                cout << "Opcao invalida\n";
                break;
        }
    }

    return 0;
}

Answer 1

Instead of creating an auxiliary stack, it is more optimized to use only an auxiliary variable. For example:

#include <iostream>
#include <vector>
void printVector(std::vector<int> myVector) {
    int vectorSize = myVector.size();
    std::cout << "[";
    for(int i = 0; i < vectorSize; i++) {
        std::cout << myVector[i];
        if (i < vectorSize - 1) {
            std::cout << ",";    
        }
    }
    std::cout << "]" << std::endl;
}

int main()
{
    std::vector<int> pilha;
    int aux = 0;
    // popula a pilha
    for(int i = 0; i < 5; i++){
       pilha.push_back(i);
    }
    printVector(pilha);
    int pilhaSize = pilha.size();
    for(int a = 0; a < pilhaSize/2; a++){
       std::cout << "loop qtts: " << pilhaSize/2 << std::endl;
       std::cout << "loop iteration: " << a + 1 << std::endl;
       // aux = armazena posicao mais a direita da pilha baseado em a
       aux = pilha[(pilhaSize - 1) - a];
       std::cout << "aux: " << aux << std::endl;
       //sobrescreve o valor mais a direita com o valor mais a esquerda
       pilha[(pilhaSize - 1) - a] = pilha[a];
       //sobrescreve o valor mais a esquerda, com o antigo valor mais a direita
       pilha[a] = aux;
       // caso necessário para o seu problema, limpe o buffer
       printVector(pilha);
       aux = 0;
    }
    return 0;
}

If our initial stack contained the values [0,1,2,3,4]: Iterations: 1: [4,1,2,3,0] 2: [4,3,2,1,0] (a = 2) is equal to 2 (5/2 .... nImpar/2 round down) then the loop to.

Link with code running: http://cpp.sh/8zijy

See also, that unlike if you had created an auxiliary vector and added the last value to the first position of the last and so on, you would have traversed the entire vector, while in this way you traverse half of the vector, or half of the vector - 1 if the vector is odd.

Advice, use ready-made and simple structures to test if the way to solve your problem is valid, before optimizing the time (speed) and space (memory) that your program uses. Creating your own structs and allocating memory manually teaches you a lot about how the computer thinks and improves its code, but very little about logic.

EDIT 1: Now that I realize that you are inside the stack, so to not lose the initial state, just create a copy and after returning the reversed stack recover it.

Answer 2

In your case, you are using a stack with list. To be able to use a stack, you need to use the push methods to insert value into the stack and pop to remove value from the stack. There are some details that need to be changed in your code. First, when you create a stack type it is not a good practice to insert the element. A memory position should have been allocated to the new element instead, using (Type *)malloc(sizeof(Type)). The insertion should be done inside the insert (in this case, push). Another detail is that the stack elements must be released after the stack is used(auxiliary cells within the method and the main stack at the end of the program).

To print it is necessary to use an auxiliary stack, where you use the stack pop, storing the value in a variable, print the variable and save its value in the auxiliary stack through a push until the stack is empty. Use another loop to insert back the contents stored in the auxiliary stack. See the code below:

void imprime_p(TPilha *p){
TPilha *aux = inicializa_p();
while (!vazia_p(p)){
    int x = pop(p);
    printf("%d ",x);
    push(aux,x);
}
while(!vazia_p(aux)){
    push(p,pop(aux));
}

libera_p(aux);

}

This is an impression of the stack in its normal order, from top to bottom. To reverse print, simply place the print on the second loop:

void imprime_invertido_p(TPilha *p){
TPilha *aux = inicializa_p();
while (!vazia_p(p)){        
    push(aux,pop(p));
}
while(!vazia_p(aux)){
    int x = pop(aux);
    printf("%d ",x);
    push(p,x);
}

libera_p(aux);

}