aula

Pilha

Um conjunto ordenado de itens e uma pilha onde novos itens podem ser inseridos e a partir do qual podem ser eliminados itens em uma extremidade chamada topo da pilha.
A pilha pode ser usada em situacoes que exija uma disciplina e sempre o ultima a entrar e o primeiro a sair.
Ex: A resolução de uma expressão do tipo:
{x + (y – [a + b]) * c – [(d + e)]} / (h – (j – (k – [l – n])))
So q expressao como essa tem diciplinas como:
a) Existe um número igual de parênteses esquerdos e direitos;
b) Todo parêntese da direita está precedido por um parêntese da esquerda correspondente;
c) A contagem dos parênteses no final da expressão é 0. Ou seja a quantidade de parênteses à esquerda e direita são iguais e nenhum escopo ficou aberto;
d) A contagem de parênteses em cada ponto da expressão é não-negativa.
Ex: ) A + B ( - C
Contagem: -1 -1 -1 -1 0 0 0 (veja que no início a contagem deu negativa, isso não é válido).
e) Quando um finalizador de escopo é encontrado, precisamos conhecer o símbolo com o qual o escopo foi aberto, pois eles necessitam ser iguais.
Então, podemos usar uma pilha para rastrear os tipos de escopos encontrados. Assim, sempre que um iniciador de escopo for encontrado, ele será empilhado e sempre que um finalizador de escopo for encontrado a pilha será examinada.
Se a pilha estiver vazia, significa que não tem a abertura do escopo, então, a expressão é inválida. Se a pilha não estiver vazia, iremos desempilhar e verificar se os escopos são iguais. Se não for, a expressão é inválida também. Quando o final da expressão (ou string) for alcançado, a pilha deverá estar vazia.
Existem várias maneiras de representar uma pilha em C. Cada uma tem vantagens e desvantagens, em termos de quão próxima pode refletir o conceito abstrato de uma pilha e quanto esforço o programador e o computador precisarão despender, ao usa-la.
Uma pilha é um conjunto ordenado de itens, e C já contém um tipo de dado que representa um conjunto ordenado