1

Preciso resolver uma questão, ela pede para mim exibir o conteúdo de uma pilha de forma invertida, pensei bastante e cheguei a conclusão de que só é possível criando uma pilha auxiliar e transferindo o conteúdo de uma pilha para outra, assim o resultado da pilha auxiliar seria a pilha invertida.

A ideia é fácil, porém estou tendo muita dificuldade em criar essa pilha auxiliar, sou iniciante com TAD's e estou quebrando muito a cabeça para resolver isso.

Meu código:

    #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;
}
1
  • Já pensou em removerPilha(topo) seguido de inserirPilha(topo_pilha_auxiliar), até que a pilha original esteja vazia?
    – anonimo
    Commented 22/11/2019 às 3:06

2 Respostas 2

1

Ao invés de criar uma pilha auxiliar, é mais otimizado você usar apenas uma variável auxiliar. Por exemplo:

#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;
}

Se nossa pilha inicial continha os valores [0,1,2,3,4]: Iterações: 1: [4,1,2,3,0] 2: [4,3,2,1,0] (a = 2) é igual a 2 (5/2 .... nImpar/2 arredonda para baixo) logo o loop para.

Link com o código rodando: http://cpp.sh/8zijy

Veja também, que diferentemente de se você tivesse criado um vetor auxiliar e adicionado o último valor a primeira posição do último e assim por diante, você teria percorrido o vetor inteiro, enquanto que dessa maneira você percorre metade do vetor, ou, metade do vetor - 1 caso o vetor seja impar.

Conselho, utilize estruturas já prontas e simples para testar se a forma de resolver seu problema é válida, antes de otimizar o tempo (velocidade) e espaço (memória) que seu programa utiliza. Criar suas próprias structs e alocar a memória manualmente lhe ensina muito sobre como o computador pensa e melhorar seu código, mas pouquíssimo sobre lógica.

EDIT 1: Agora que percebi que você esta dentro da pilha, logo, para não perder o estado inicial, basta criar uma cópia e depois de retornar a pilha invertida recuperá-la.

2
  • Mas se é uma pilha então, por definição desta estrutura de dados, você tem acesso somente ao topo da pilha.
    – anonimo
    Commented 22/11/2019 às 3:58
  • Correto, porém nada o impede de transformar todos os valores da pilha em uma lista e reordená-los, retornando eles de qualquer forma que ele queira, caso ele queira retorná-los em forma de pilha novamente, basta criar uma nova pilha agora com os valores invertidos. Commented 22/11/2019 às 4:03
0

No seu caso, você está utilizando uma pilha com lista. Para você poder utilizar uma pilha, é necessário a utilização dos métodos de push para inserir valor na pilha e pop para retirar valor da pilha. Existem alguns detalhes que precisam ser alterados em seu código. Em primeiro lugar, quando você cria um tipo pilha não é uma boa prática inserir o elemento. Deveria ter sido alocado uma posição em memória para o novo elemento ao invés disso, utilizando (Tipo *)malloc(sizeof(Tipo)). A inserção deve ser feito dentro do inserir (no caso, do push). Outro detalhe é que os elementos da pilha devem ser liberados após a pilha ser utilizada(pilhas auxiliares dentro do método e a pilha principal ao fim do programa).

Para imprimir é necessário utilizar uma pilha auxiliar, onde você utiliza o pop na pilha, guardando o valor em uma variável, imprime a variável e guarda seu valor na pilha auxiliar através de um push até que a pilha esteja vazia. Utilize outro loop para inserir de volta o conteúdo guardado na pilha auxiliar. Veja o código abaixo:

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);

}

Essa é uma impressão da pilha em sua ordem normal, do topo para baixo. Para imprimir de forma invertida, basta colocar a impressão no segundo 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);

}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .