Listas lineares
Listas Lineares
Pilha
Fila
Entrada restrita
Fila Dupla
Saída restrita
Fila versus Pilha
SAÍDA
FIM
SAÍDA
ENTRADA
Elemento 3
TOPO
Elemento 2
Elemento 1
Elemento 2
Elemento 1
ENTRADA
INÍCIO
BASE
Filas
Operações primitivas que manipulam as filas:
InicializaFila ou Construtor
faz a fila q ficar vazia
FilaVazia ou Empty
retorna Verdadeiro se a fila q está vazia
FilaCheia ou Full
retorna Verdadeiro se a fila q está cheia
InsereFila(x) ou Insert(x)
insere o elemento x no final da fila
RemoveFila ou Remove
remove o PRIMEIRO elemento da fila,
retornando o conteúdo do elemento
como valor da função
Filas
REPRESENTANDO FILAS EM O.O.
Pode utilizar um vetor
Apoio de duas variáveis: front e rear
Front: primeiro elemento da fila
Rear: último elementos da fila
class Queue
{
private object [] elements =
new object[1000];
private int front, rear;
...
}
Filas
Ignorando, momentaneamente, a
possibilidade de overflow e underflow:
Operação Insert (x):
elements [++ rear] = x;
Operação Remove (q):
x= elements [front ++];
• No momento que a fila é criada, rear é definido como –1 e front como 0
• A fila está vazia sempre que rear < front
• Número de elementos na fila é sempre igual ao valor de rear – front + 1
Filas
Problema clássico da fila vazia sem
possibilidade de inserir novos elementos:
itens
itens
itens
itens
4
E
3
D
2
C
1
B
0
front = 0
rear = -1
A
rear=2
front=0
C
front=
rear=2
C
rear =4
front =2
Filas
Solução 1: remanejar todos os elementos
quando remover um elemento
public int Remove ()
{
x = elements [ 0 ];
for (int i = 0; i < rear; i++)
elements[ i ] = elements[ i + 1 ];
rear - -;
• O campo front não é necessário porque o elemento na posição 0 do vetor
está sempre no início da fila. A fila vazia é representada por rear igual a –1
• Podemos verificar que pode existir um grande esforço computacional para
a movimentação de 500, 1000, 10.000, 1.000.000 elementos
• Esta solução sugerida parece ser bastante ineficiente
Filas Circulares
• Solução mais elegante para resolver problema das filas
• A idéia é armazenar os elementos na fila como um
círculo.
• Primeiro elemento do vetor vem logo depois do último.
• Se o último elemento estiver ocupado, um novo valor
pode ser inserido no primeiro elemento do vetor
• Elemento novo não será incluído numa fila circular
somente se não houver de fato espaço na mesma.
Filas Circulares
4
3
2
1
0
elements
E
rear=4
D
C
front=2
elements
E
D
C
front=2
rear=0
F
elements
E
front=4
elements
E
front=4
elements
F
G
F
G
F
rear =0
rear=1
rear= 1
front=0
No momento (d), rear < front (1 < 4), é verdadeira – fila
vazia?
Solução: utilizar um contador com o número de
elementos.
Filas Circulares
Implementação dessa solução – atributos da classe:
class Queue
{
private object [] elements;
private int front, rear, size, count;
// Métodos
...
}
Filas Circulares
Implementação dessa solução – construtor:
public Queue (int Size)
{
size = Size;
elements = new object[size];
front = 0;
rear = front;
count = 0;
}
Filas Circulares
Implementação dessa solução – retirar elementos:
public object Remove ()
{
if (Empty ()) {
throw new Exception(“Fila vazia!”); }
if (front == size – 1)
front = 0;
else
front++;
count --;
return (elements[front]);
}
Filas Circulares
Implementação dessa solução – inserir elementos:
public void Insert (object x)
{
if (Full())
{
throw new Exception (“Pilha Cheia!”);
}
if (rear == size – 1)
rear = 0;
else
rear ++;
elements[rear] = x;
count ++;
}