Dynamic stack - Compare values

Question

Hey, how you doing? So, I needed to do a function on a dynamic stack to test whether two stacks containing integers are equal, i.e., to see if two values are of the same content and in the same order. For now what I have is this code, which stacks, pops and displays values, but still lacks the function to compare. Can anyone help me?

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

/// Estrutura TipoPilha
typedef struct {
    char letra;     
}TipoItem;
typedef struct TipoCelula *TipoApontador; 
typedef struct TipoCelula {
    TipoItem Item;
    TipoApontador Prox;
} TipoCelula; 
typedef struct { 
    TipoApontador Fundo, Topo; 
    int Tamanho; 
} TipoPilha;

// Funções de manipulação da pilha
void FPVazia(TipoPilha *Pilha) {
    Pilha ->Topo=(TipoApontador) malloc(sizeof(TipoCelula ));
    Pilha ->Fundo = Pilha ->Topo;
    Pilha ->Topo->Prox = NULL;
    Pilha ->Tamanho;
}

int Vazia(TipoPilha Pilha) {
    return (Pilha.Topo == Pilha.Fundo);
}

void Empilha(TipoItem x, TipoPilha *Pilha) {
    TipoApontador Aux; 
    Aux = (TipoApontador) malloc(sizeof(TipoCelula)); 
    Pilha->Topo->Item = x; 
    Aux->Prox = Pilha ->Topo; 
    Pilha ->Topo = Aux; 
    Pilha ->Tamanho++; 
}

void Desempilha(TipoPilha *Pilha , TipoItem *Item) {
    TipoApontador q; 
    if (Vazia(*Pilha ) ) { 
        printf ( "Erro : lista vazia\n" ) ; return; 
    }
    q = Pilha ->Topo; 
    Pilha ->Topo = q ->Prox; 
    *Item = q ->Prox->Item; 
    free(q) ;
    Pilha ->Tamanho--; 
}

int Tamanho(TipoPilha Pilha) {
    return (Pilha.Tamanho) ;
}

void ExibePilha(TipoPilha Pilha){
    TipoApontador aux=Pilha.Topo->Prox;
    while(aux!=NULL){
        printf("\n %c", aux->Item.letra);
        aux=aux->Prox;
    }
}

main(){
    TipoPilha pilha;
    FPVazia(&pilha);
    TipoItem item;
    int op=-1;
    while(op!=0){
        printf("\n0- Sair");
        printf("\n1- Empilha");
        printf("\n2- Desempilha");
        printf("\n3- Exibe a pilha");
        printf("\nDigite sua opcao: "); scanf("%d", &op);
        switch(op){
            case 1:
                printf("Digite a letra a ser empilhada: ");
                fflush(stdin);
                scanf("%c", &item.letra);
                Empilha(item, &pilha);
            break;
            case 2:
                Desempilha(&pilha, &item);
                printf("\nItem desempilhado: %c", item.letra);
            break;
            case 3:
                printf("\n*** Exibindo a pilha*** \n");
                ExibePilha(pilha);
            break;
        }
    }
}`

Answer 1

First check if they have equal sizes, if not you already know they are different. If they are equal then you need to pop the elements of the two stacks and compare the values. Example:

bool igual = true;
int elemento1, elemento2;

while(/* Repetir até a pilha ficar vazia */)
{
    desempilhar(pilha1, &elemento1);
    desempilhar(pilha2, &elemento2);

    if(elemento1 != elemento2) igual = false;
}

If you have a different element then igual will be fake at the end of the loop. With this you can already compare, the problem is that the stacks will be empty, to solve this you can use two auxiliary stacks or use recursiveness and so can stack the elements again.

Example with two auxiliary batteries

Maybe the most intuitive way is to do something like this:

while(/* Repetir até a pilha ficar vazia */)
{
    desempilhar(pilha1, &elemento1);
    desempilhar(pilha2, &elemento2);

    if(elemento1 != elemento2) igual = false;

    empilhar(&aux1, elemento1);
    empilhar(&aux2, elemento2);
}

while(/* Repetir até a pilha ficar vazia */)
{
    desempilhar(&aux1, &elemento1);
    desempilhar(&aux2, &elemento2);

    empilhar(pilha1, elemento1);
    empilhar(pilha2, elemento2);
}

Example with recursion

We can walk a pilha using the following example:

void pecorrerPilha(Pilha *pilha)
{
    int elemento;

    desempilhar(pilha, &elemento);

    if(/* Se não tiver vazia */) pecorrerPilha(pilha);

    empilhar(pilha, elemento);
}

Using this logic you can avoid having two more auxiliary stacks and so the code will look more elegant. Example:

int elemento1, elemento2;

desempilhar(pilha1, &elemento1);
desempilhar(pilha2, &elemento2);

if(elemento1 != elemento2) *igual = false;

if(/* Se não tiver vazia */ && *igual) pecorrerPilha(pilha1, pilha2, igual);

empilhar(pilha1, elemento1);
empilhar(pilha2, elemento2);

Using recursiveness you can use a pointer to change the value igual is in all, thus avoiding that the change is only in a single scope.