911147 Aula 09 Pilha

Programa¸c˜ao de Computadores II
Prof. Kleber Jacques F. de Souza
PUC Minas

Aula 09 - Pilha

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Agenda

1

Pilha

2

Propriedade e Aplica¸c˜ oes das Pilhas

3

TAD Pilha

4

Implementa¸c˜ao de Pilhas por meio de Apontadores

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Pilha
´ uma lista linear em que todas as inser¸c˜
E
oes, retiradas e, geralmente, todos os acessos s˜ao feitos em apenas um extremo da lista.
Os itens s˜ao colocados um sobre o outro. O item inserido mais recentemente est´a no topo e o inserido menos recentemente no fundo.
O modelo intuitivo ´e o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.
Esta imagem est´a frequentemente associada com a teoria de autˆomato, na qual o topo de uma pilha ´e considerado como o recept´aculo de uma cabe¸ca de leitura/grava¸c˜ao que pode empilhar e desempilhar itens da pilha

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Propriedade e Aplica¸c˜oes das Pilhas
Propriedade: o u
´ltimo item inserido ´e o primeiro item que pode ser retirado da lista. S˜ao chamadas listas LIFO
(“Last-In, First-Out”).
Existe uma ordem linear para pilhas, do “mais recente para o menos recente”.
´ ideal para estruturas aninhadas de profundidade imprevis´ıvel.
E
Aplica¸c˜oes em estruturas aninhadas:
Quando ´e necess´ario caminhar em um conjunto de dados e guardar uma lista de coisas a fazer posteriormente.
O controle de sequˆencias de chamadas de subprogramas.
A sintaxe de express˜ oes aritm´eticas.

As pilhas ocorrem em estruturas de natureza recursiva (como
´arvores). Elas s˜ao utilizadas para implementar a recursividade. Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

TAD Pilha

Conjunto de opera¸c˜ oes: 1
2

3
4

5

FPVazia(Pilha). Faz a pilha ficar vazia.
Vazia(Pilha). Retorna true se a pilha est´a vazia; caso contr´ario, retorna false.
Empilha(x,