O conceito de pilha

Algoritmos de inserção e remoção

Exemplo: Notação Polonesa

Aula 10: Pilhas

10.1

Pilhas

10.2

Listas, pilhas e deques: inserções e remoções ocorrem

somente nas extremidades.

Uso eficiente de listas:

inserções e remoções não devem acarretar

movimentação de nós.

remover

A B C D E A B D E

Remover Voltar

Listas, pilhas e deques: inserções e remoções ocorrem

somente nas extremidades.

Uso eficiente de listas:

inserções e remoções não devem acarretar

movimentação de nós.

C

A B D E

Pilhas

10.3

Pilhas: inserções e remoções ocorrem em uma mesma

extremidade

topo da pilha

A base da pilha

B

C

D

E

Pilhas

10.4

Topo da pilha: extremidade na qual

ocorrem as inserções e remoções.

Pilhas

10.5

Operações básicas:

Formas de armazenamento:

Em alocação sequencial:

usa vetores;

um ponteiro indica a posição do topo da pilha.

inserção;

remoção.

Pilhas

10.6

Situações extremas:

Forma de operação:

Operações inválidas:

pilha vazia;

pilha cheia.

inserção em pilha cheia (overflow)

remoção em pilha vazia (underflow)

último a entrar, primeiro a sair (LIFO)

Exemplo

10.7

Exemplo de operação de uma pilha:

situação 8:

remover (underflow)

topo

5

4

3

2

1

C

A

situação 5:

inserir C

5

4

3

2

1

topo

5

4

3

2

A 1

situação 6:

remover

topo

situação 7:

remover

5

4

3

2

1

topo

5

4

3

2

1

B

A

situação 3:

inserir B

topo

A

5

4

3

2

1

situação 2:

inserir A

topo

situação 1: inicial

(pilha vazia)

5

4

3

2

1 topo

5

4

3

2

A 1

situação 4:

remover

topo

10.8

Exemplo de operação de uma pilha

Voltar

topo = 0 topo = 1 topo = 2

A B C

Animar

topo = -1 -> underflow

Exemplo

Algoritmo de Inserção

10.9

A pilha se encontra armazenada no vetor

P

A variável topo indica o topo da pilha

Algoritmo: inserção na pilha P

se topo

≠ M então

topo := topo + 1

P[ topo ] := novo_valor

senão overflow

Pilha vazia: topo = 0

Overflow: inserção com topo =

M

A informação a ser inserida é novo_valor.

O vetor

P possui

M posições

Algoritmo de Remoção

10.10

A pilha se encontra armazenada no vetor P

A variável topo indica o topo da pilha

Algoritmo: remoção na pilha P

se topo ≠ 0 então

valor_recuperado := P[ topo ]

topo := topo - 1

senão underflow

Pilha vazia: topo = 0

Overflow: remoção com topo = 0

A informação a ser removida é transferida

para valor_recuperado.

Explicação: