O impasse fila vazia/cheia, na implementação circular, foi solucionado com o uso de uma variável contadora. Uma outra forma de resolver o problema seria impedir que o índice final alcançasse o índice começo, deixando sempre pelo menos uma posição livre entre o primeiro e o último elemento da fila. Apresente uma nova implementação circular para o tipo fila que se baseie neste princípio para detectar fila vazia ou cheia. Dê exemplos.
Passo 1
Vamos resumir o que está sendo pedido. O exercício fala sobre filas circulares e como resolver o problema de determinar quando a fila está vazia ou cheia. A solução proposta é deixar sempre uma posição livre na fila para facilitar essa detecção. Para resolver isso, vamos utilizar conceitos de estruturas de dados, especialmente filas circulares, e implementar uma lógica que impede o índice de final (rear) alcançar o índice de início (front), garantindo assim que sempre haja pelo menos uma posição vazia.
Passo 2
Primeiro, precisamos entender como funciona uma fila circular. Em uma fila linear, ao inserir elementos até o fim, pode haver desperdício de espaço quando elementos são removidos do início. A fila circular resolve esse problema permitindo que, ao chegar ao final do array, o índice volte para o início, aproveitando o espaço vazio. Mas, como mencionamos, isso cria a ambiguidade entre fila cheia e vazia.
Passo 3
Para evitar essa ambiguidade sem usar uma variável contadora, implementamos a regra de deixar sempre uma posição livre. Isso significa que, em vez de usar todos os espaços do array, usamos apenas (tamanho da fila - 1). Assim, podemos dizer que a fila está cheia quando o próximo índice de rear for igual a front.
Passo 4
Vamos definir as variáveis necessárias:
front
: índice que aponta para o início da fila.rear
: índice que aponta para o final da fila.size
: tamanho total do array que representa a fila.
Inicialmente, ambos
front
e rear
são iguais a 0, indicando que a fila está vazia.Passo 5
Para inserir um elemento (enqueue):
- Verifique se a fila está cheia: se
(rear + 1) % size == front
, a fila está cheia. - Se não estiver cheia, insira o elemento na posição
rear
. - Atualize
rear
para(rear + 1) % size
.
Para remover um elemento (dequeue):
- Verifique se a fila está vazia: se
front == rear
, a fila está vazia. - Se não estiver vazia, remova o elemento da posição
front
. - Atualize
front
para(front + 1) % size
.
Passo 6
Vamos ver um exemplo prático. Suponha que temos uma fila de tamanho 5.
- Inicialmente:
front = 0
,rear = 0
. - Inserimos 1: fila = [1, -, -, -, -],
rear = 1
. - Inserimos 2: fila = [1, 2, -, -, -],
rear = 2
. - Inserimos 3: fila = [1, 2, 3, -, -],
rear = 3
. - Inserimos 4: fila = [1, 2, 3, 4, -],
rear = 4
. - Tentativa de inserir outro elemento:
(4 + 1) % 5 == 0
, que é igual afront = 0
, então a fila está cheia. Não é possível inserir mais elementos. - Removemos um elemento: remove 1, fila = [-, 2, 3, 4, -],
front = 1
. - Agora é possível inserir novamente: inserimos 5, fila = [5, 2, 3, 4, -],
rear = 0
(pois(4 + 1) % 5 = 0
).
Resposta
Implementamos uma fila circular que sempre mantém uma posição livre para distinguir entre fila cheia e vazia. Utilizamos os índices
front
e rear
com a condição de que a fila está cheia quando (rear + 1) % size == front
e está vazia quando front == rear
. Com essa lógica, garantimos uma implementação eficiente e sem ambiguidade para a fila circular.