5

Olá, preciso implementar uma fila usando duas pilhas, ou seja, preciso inserir um inteiro na pilha 1, e quando for remover um elemento todos os itens da pilha 1 devem ser transferidos para a pilha 2, fazendo então com que se pareça com uma fila.

Os itens da pilha 1 só podem ser transferidos se a pilha 2 estiver vazia, enquanto não estiver os elementos devem ser removidos da pilha 2.

O código para inserção e remoção na pilha 1 está da seguinte maneira:

 #include<stdio.h>
#include<stdlib.h>

typedef struct noLista{
    int info;
    struct noLista *prox;
} Elemento;

    Elemento* criarNovo(int Caractere);
    Elemento* Push(Elemento *Topo, int Caractere);
    Elemento* Pop(Elemento *Topo);
    Elemento* Top(Elemento *Topo);

main () {
    int Dados, i, op;
    Elemento *Pilha = NULL, *aux;

    do{
    system("cls");
    printf("1 - Adicionar elemento\n");
    printf("2 - Remover elemento\n");
    printf("0 - Encerrar\n\n");

    printf("Opcao: ");
    scanf("%d", &op);

    switch(op){
        case 1:
            printf("Digite um inteiro: ");
            scanf("%d", &Dados);

            Pilha = Push(Pilha, Dados);
            printf("Elemento adicionado\n\n");
            system("pause");
            break;

        case 2:
            aux = Top(Pilha);

            if(aux != NULL){
                Pilha = Pop(Pilha);
                printf("Elemento removido\n\n");
                system("pause");
            } else{
                printf("A pilha esta vazia\n\n");
                system("pause");
            }
            break;

        case 3:

            break;

    }
    } while(op!=0);
}

Elemento* criarNovo(int Caractere){
    Elemento *novo;

    novo = (Elemento*) malloc(sizeof(Elemento));
    novo->info = Caractere;
    novo->prox = NULL;

    return novo;
}

Elemento* Push(Elemento *Topo, int Caractere){
    Elemento *novo;

    novo = criarNovo(Caractere);

    novo->prox = Topo;
    Topo = novo;
    return Topo;
}

Elemento* Pop(Elemento *Topo){
    Elemento *aux;

    aux = Topo;
    if(Topo != NULL) {
        Topo = Topo->prox;
        free(aux);
    }
    return Topo;
}

Elemento* Top(Elemento *Topo){
    return Topo;
}

O que devo fazer?

2
  • As implementações da pilha não estão muito bem, poderei responder com uma implementação "mais à minha maneira" se quiser, pois não faço dessa forma as funções do push, pop..etc 8/09/2018 às 21:27
  • Fábio, fique à vontade para implementar da sua maneira, ficarei grato. 8/09/2018 às 21:49

2 Respostas 2

3
typedef struct item_p
{
    int elemento;
    struct item_p *proximo;
} pilhaItem;

typedef struct
{
    pilhaItem *raiz;
    int tamanho;
} pilha;

pilha* pilha_nova()
{
    /* cria pilha */
    pilha *p = (pilha*) malloc(sizeof(pilha));
    if(p == NULL)
        return NULL;

    /* pilha esta' vazia */
    p->raiz = NULL;
    p->tamanho = 0;

  return p;
}

int pilha_tamanho(pilha *p)
{
    if (p == NULL)
        return -1;

    return p->tamanho;
}

int pilha_top(pilha *p)
{
    pilhaItem *aux;

    if (p == NULL || p->tamanho == 0)
        return NULL;

    aux = p->raiz;
    return aux->elemento;
}

pilhaItem* pilha_novo_elemento(int valor)
{
    /* aloca memoria para a estrutura pilhaItem */
    pilhaItem *item = (pilhaItem *) malloc(sizeof(pilhaItem));
    if(item == NULL)
        return NULL;

    item->elemento=valor;

    /* item ainda nao tem proximo */
    item->proximo = NULL;

    return item;
}

void pilha_push(pilha *p, int valor)
{
    pilhaItem *novo = NULL;

    if (p == NULL || valor == NULL)
        return;

    /* cria novo item */
    novo = pilha_novo_elemento(valor);
    if (novo == NULL)
    return;

    p->tamanho++;

    /* inserir no topo da pilha */
    /* se a pilha esta vazia */
    if (p->raiz == NULL)
    {
        p->raiz = novo;
        return;
    }

    /* primeiro elemento */
    novo->proximo = p->raiz;
    p->raiz = novo;
}

void pilha_pop(pilha *p)
{
    pilhaItem *curr;

    if (p == NULL || p->tamanho == 0)
        return;

    curr = p->raiz;
    p->raiz = curr->proximo;
    p->tamanho--;

    /* liberta memoria associada ao item removido */
    free(curr);
}

Testar estas funções no ideone (exemplo de como usar)


Ficheiro main

main () {
    int Dados, i, op;
    pilha *Pilha1=pilha_nova();
    do{
    system("cls");
    printf("1 - Adicionar elemento\n");
    printf("2 - Remover elemento\n");
    printf("0 - Encerrar\n\n");

    printf("Opcao: ");
    scanf("%d", &op);

    switch(op){
        case 1:
            printf("Digite um inteiro: ");
            scanf("%d", &Dados);

            pilha_push(Pilha1, Dados);
            printf("Elemento adicionado\n\n");
            system("pause");
            break;

        case 2:
            if(Pilha1 != NULL){
                pilha_pop(Pilha1);
                printf("Elemento removido\n\n");
                system("pause");
            } else{
                printf("A pilha esta vazia\n\n");
                system("pause");
            }
            break;

        case 3:

            break;

    }
    } while(op!=0);

    pilha *Pilha2=pilha_nova();
    while(pilha_tamanho(Pilha1)>0){
        pilha_push(Pilha2, pilha_top(Pilha1));
        pilha_pop(Pilha1);
    }
}

A parte final do codigo coloco todos os dados da pilha 1 na pilha 2 como queria.

    pilha *Pilha2=pilha_nova();
    while(pilha_tamanho(Pilha1)>0){
        pilha_push(Pilha2, pilha_top(Pilha1)); //inserir na pilha 2 o valor de pilha 1
        pilha_pop(Pilha1); // remover o topo da pilha 1
    }

O metodo de passar de uma pilha para outra pilha é:

LOOP: {

  1. Retornar o valor do topo da pilha 1 e colocar na pilha 2
  2. Remover o valor do topo da pilha 1

}

2

Uma vez que o @FabioMorais já respondeu com uma implementação alternativa possível para o problema, eu aproveito para mostrar uma implementação partindo do código que tem e alterando o mínimo possível.

Não posso deixar de fazer um aparte para a nomenclatura que está a utilizar que é mais importante do que parece. Vejamos estas linhas de código:

Elemento* criarNovo(int Caractere);
Elemento* Push(Elemento *Topo, int Caractere);
int Dados, i, op;

Aqui está a usar camelCase e PascalCase, para além de definir os parâmetros das funções e variáveis capitalizadas. O mais importante é ser consistente e utilizar sempre o mesmo estilo de nomenclatura, e o padrão mais adotado em C é snake_case. Neste padrão estas instruções ficariam:

Elemento* criar_novo(int caractere);
Elemento* push(Elemento *topo, int caractere);
int dados, i, op;

Nomes de estruturas e classes é comum de se deixarem capitalizadas.

Partindo agora para a solução. Primeiro tem de criar a segunda pilha:

Elemento *Pilha = NULL, *aux, *Pilha2 = NULL;
//                              ^---

Que será a pilha que irá ter os items a serem removidos. A ideia agora é:

  • Se a Pilha2 tem elementos então o remover remove o topo dessa diretamente.
  • Se essa tiver vazia tem de primeiro passar todos os elementos para da Pilha para a Pilha2 e depois remover o topo da Pilha2

Implementação:

case 2:
    if (Top(Pilha2) == NULL){  // se a pilha 2 está vazia
        while (Top(Pilha) != NULL){ //passa tudo da pilha1 para a pilha2
            int removido = Top(Pilha)->info;
            Pilha = Pop(Pilha);
            Pilha2 = Push(Pilha2, removido);
        }
    }
    if(Top(Pilha2) != NULL) { //se existem elementos
        int removido = Top(Pilha2)->info; //remove o primeiro da pilha2
        Pilha2 = Pop(Pilha2);
        printf("Elemento %d removido\n\n", removido);
    } else {
        printf("A pilha esta vazia\n\n");
    }
    break;

Veja a funcionar no Ideone, adicionando os elementos 5, 10 e 12 e depois removendo todos

Visualmente o que acontece primeiro é que primeiro é tudo adicionado à Pilha1

Pilha1:
12 -> 10 -> 5 -> NULL

Pilha2:
NULL

Depois na primeira remoção faz Pop a tudo da Pilha1 e faz Push para a Pilha2.

Passo 1:

Pilha1:
10 -> 5 -> NULL

Pilha2:
12 -> NULL

Passo 2:

Pilha1:
5 -> NULL

Pilha2:
10 -> 12 -> NULL

Passo 3:

Pilha1:
NULL

Pilha2:
5 -> 10 -> 12 -> NULL    

Após estes passos todas as remoções são feitas pela Pilha2 e por isso começam por remover no 5, dando a ordem 5, 10, 12 que funciona como uma fila e não uma pilha.

5
  • O problema maior é mesmo as funções do inserir e pop, se tentar imprimir a pilha verifica que dá errado. 9/09/2018 às 15:41
  • @FábioMorais Não vejo o problema que indica. Coloquei os testes que mencionou no Ideone e tudo parece dentro do esperado. Excetuando a parte do tamanho a lógica do push e pop é igual à da sua resposta considerando os nomes das variaveis e estruturas diferentes. Que parte em especifico desses dois métodos afirma que está errada ?
    – Isac
    9/09/2018 às 16:15
  • Não é dessa forma que se imprime a pilha, imprime o top e faz pop (etc...) Pois é dessa forma que se manipula a pilha. Primeiro exemplo, imprimir todos os elementos ideone, no seu codigo parece que está funcionando, porem não está 9/09/2018 às 16:24
  • @FábioMorais O que fez é fazer pop a tudo e ir mostrando que é diferente de apenas mostrar tudo sem alterar a pilha. No entanto fez apenas Pop(Pilha); quando de acordo com o retorno da função devia fazer Pilha = Pop(Pilha); Ora veja como dá o que é esperado
    – Isac
    9/09/2018 às 16:30
  • Ah sim, esqueci-me dessa particularidade na implementação. 9/09/2018 às 16:32

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 .