terça-feira, 25 de setembro de 2012

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)