Estrutura de dados

São Paulo, 2011

Algoritmos e estrutura de dados

Estrutura de Dados

28/11/2012

1

Sumário
Algoritmos e estrutura de dados

 Introdução  Conceitos gerais  Operações com pilhas  Notações infixa, pré-fixa, pós-fixa  Implementação de uma pilha

28/11/2012

2

Introdução
 Estruturas de dados: utilizam restrições de acesso aos dados.
Algoritmos e estrutura de dados

 Benefícios:

 menos detalhes nas estruturas;
 implementações mais simples e flexíveis:

 menos operações suportadas.
 Estas restrições também conhecidas como políticas de acesso são:  Last In First Out (LIFO): utilizadas por estruturas do tipo Pilha.  First In First Out (FIFO): utilizadas por estruturas do tipo Fila.
28/11/2012 3

Conceitos gerais
 Estrutura do tipo Pilha:
Algoritmos e estrutura de dados

 É uma lista linear;

 Inserções, retiradas e todos os acessos são feitos em apenas uma das extremidades da lista;  Sua principal característica é:  O último item inserido é o primeiro item a ser retirado da lista.

28/11/2012

4

Conceitos gerais
Algoritmos e estrutura de dados

Primeiro elemento a sair

Último elemento a entrar

Último elemento a sair

Primeiro elemento a entrar

28/11/2012

5

Operações realizadas com pilhas
 Apenas duas operácões básicas estão envolvidas:
Algoritmos e estrutura de dados

 PUSH ou Empilha: Acrescentar no topo da pilha

 POP ou Desempilha: Retirar do topo da pilha push (a) push (b) push (c) pop ( ) retorna c topo b a topo push (d)

a

topo

b a

topo

c b a

d b a

topo

28/11/2012

6

Operações realizadas com pilhas
 PILHA: é uma lista do tipo seqüencial no qual:
Algoritmos e estrutura de dados

 O elemento 0 (ZERO) será definido como o fundo da pilha;

 Topo da pilha: TOPO índice que indica a 1ª posição livre da pilha.
 pilha vazia: TOPO = -1

 restrição: tamanho máximo definido (MAX - 1).

28/11/2012

7

Operações realizadas com