Pilhas

Estruturas de Dados
Aula 11: TAD Pilha

09/05/2011

Fontes Bibliográficas
• Livros:
– Projeto de Algoritmos (Nivio Ziviani): Capítulo 3;
– Introdução a Estruturas de Dados (Celes,
Cerqueira e Rangel): Capítulo 10;
– Estruturas de Dados e seus Algoritmos
(Szwarefiter, et. al): Capítulo 2;
– Algorithms in C (Sedgewick): Capítulo 3;

• Slides baseados nas transparências disponíveis em: http://www.dcc.ufmg.br/algoritmos/transparenc ias.php Pilhas
• É uma lista linear em que todas as inserções, retiradas e, geralmente, todos os acessos são feitos em apenas um extremo da lista.
• Os itens são colocados um sobre o outro. O item inserido mais recentemente está no topo e o inserido menos recentemente no fundo.
• O modelo intuitivo é o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.

Propriedades e Aplicações das Pilhas
• Propriedade: o último item inserido é o primeiro item que pode ser retirado da lista. São chamadas listas lifo (“last-in, first-out”).
• Existe uma ordem linear para pilhas, do “mais recente para o menos recente”.
• É ideal para processamento de estruturas aninhadas de profundidade imprevisível.
• Uma pilha contém uma seqüência de obrigações adiadas. A ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas.

Propriedades e Aplicações das Pilhas (2)
• Aplicações em estruturas aninhadas:
– Quando é necessário caminhar em um conjunto de dados e guardar uma lista de coisas a fazer posteriormente. – O controle de seqüências de chamadas de subprogramas. – A sintaxe de expressões aritméticas.

• As pilhas ocorrem em estruturas de natureza recursiva (como árvores). Elas são utilizadas para implementar a recursividade.

TAD Pilha
• Conjunto de operações:
– FPVazia (Pilha). Faz a pilha ficar vazia.
– Vazia (Pilha). Retorna true se a pilha estiver vazia; caso contrário, retorna false.
– Empilha (x,