Inverter a ordem dos nós de uma Lista usando Pilha

Boa Noite Folks!

      Nosso intuito com o blog é postar não apenas curiosidades sobre o avanço da tecnologia nas diversas ramificações da informática, mas também auxiliar o estudante nas mais "duras" barreiras que ele irá encontrar em seu meio universitário! xD

      Por isso hoje, em nosso primeiro post, iremos exemplificar o uso de Pilha em linguagem C para inverter a ordem de nós de uma lista usando pilha.

      

•  Implementar uma função em C que inverta a ordem dos nós de uma lista usando uma pilha:

void lstInverter(lista * l) { // função que inverta a ordem dos nós de uma lista usando uma pilha

int i = 0;

lstInfo x;

pilha p;

stackInit(&p); // função que inicia pilha

while (lstRemover(l, 0, &x)) //enquanto houver valor na lista para remover, remove o elemento da posição 0 da lista

push(&p, x); // e empilha no topo da pilha

while (!stackIsEmpty(p)) // enquanto a pilha não estiver vazia

lstInserir(l, i++, pop(&p)); //  remove o topo da pilha e insere na lista novamente, mas em ordem inversa

}

Figura 1 - Esquema inicial da lista e da pilha

while (lstRemover(l, 0, &x)) //Enquanto houver valor na lista para remover, remove o elemento da posição '0' da lista

push(&p, x); // E empilha no topo da pilha

Significa que o programa não sairá deste while (lstRemover(l, 0, &x))  enquanto houver valor para remover na lista e passar para pilha através do push(&p, x);  !

Quando terminar esse while (lstRemover(l, 0, &x))  ficaremos assim:

Figura 2 - Lista e Pilha após aplicar o laço While

•  Perceba que na pilha inserimos sempre no topo. O primeiro elemento que sai da lista é o 1, ele vai para o topo da pilha, que.. como estava vazia, insere o elemento 1 na sua posição 0, e outros vão sendo inseridos em cima. Pense na pilha como uma pilha de pratos (eu entendi assim rs):

Figura 3 -  Exemplo da inserção de elementos em uma pilha

• Você NÃO pode remover os pratos de baixo sem antes remover os de cima, senão vai derrubar toda a "pilha de pratos", então precisa REMOVER SEMPRE DO TOPO;

• Nem pode inserir pratos no meio ou embaixo, senão vai derrubar tudo também! Então tem que INSERIR SEMPRE NO TOPO!

     while (!stackIsEmpty(p)) // enquanto a pilha não estiver vazia

     lstInserir(l, i++, pop(&p)); //  remove o topo da pilha e insere na lista novamente, mas em ordem //inversa

     Então, faremos o contrário agora, while (!stackIsEmpty(p)), ou seja, enquanto a PILHA não estiver vazia:     

     

     lstInserir(l, i++, pop(&p)); //   vamos inserir NA LISTA o pop(&p) , função que remove o topo da PILHA. 

     Perceba que o topo da PILHA é 5 (figura 3).

    5 será inserido na posição ‘0’ da lista, 4 na posição ‘1’, e assim sucessivamente, invertendo assim a ordem        

    dos números na lista:

Figura 4 - Pilha Vazia e números na lista em ordem inversa

Espero ter ajudado, não esqueçam de deixar seus comentários para podermos sempre melhorar!

Att.,
InfoCuriosities