PilhaFilaArranjos

Pilhas e Filas com Arranjos

Raphael Winckler de Bettio

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.
LIFO (Last In, First Out)
Push()

Pop()

Colocar()

Retirar()

Pilhas
●

Como as inserções e as retiradas ocorrem no topo da pilha, um cursor chamado Topo é utilizado para controlar a posição do item no topo da pilha.

Pilhas
Operação Retirar

7

Operação Colocar

6

6

5

5

4

7

4

12

TOPO
3

2

3

2

2

6

2

6

1

5

1

5

12

Pilhas
Verificar se a pilha está cheia
✔Verificar se a pilha está vazia
✔

Pilhas - Push()

Pilhas - Pop()

Filas
●

●

●

É uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas e, geralmente, os acessos são realizados no outro extremo da lista.
São utilizadas quando desejamos processar itens de acordo com a ordem “primeiro-quechega, primeiro-atendido”.
FIFO (First In, First Out)
Enfileira()

Desenfileira()

Enqueue()

Dequeue()

Filas
1

2

3

4

5

6

7

8

9

5

6

7

8

9

6

7

8

9

Inserção (10,14,66,77)
1

2

3

4

10

14

66

77
Inicio

Remoção (10,14)
1

2

3

4

66

77

Fim
5

Filas
●

●

A fila tende a caminhar pela memória do computador, ocupando espaço na parte de trás e descartando espaço na parte da frente.
Com poucas inserções e retiradas, a fila vai ao encontro do limite do espaço da memória alocado para ela

Filas Circulares
●

●

●

●

Solução: imaginar o arranjo como um círculo. A primeira posição segue a última.
A fila se encontra em posições contíguas dememória, em alguma posição do círculo, delimitada pelos apontadores frente e trás.
Para enfileirar, basta mover o apontador trás uma posição no sentido horário.
Para desenfileirar, basta mover o apontador frente uma posição no sentido horário

Filas Circulares
Inserção (10,14,66,77)