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):
  1. Verifique se a fila está cheia: se (rear + 1) % size == front, a fila está cheia.
  2. Se não estiver cheia, insira o elemento na posição rear.
  3. Atualize rear para (rear + 1) % size.
Para remover um elemento (dequeue):
  1. Verifique se a fila está vazia: se front == rear, a fila está vazia.
  2. Se não estiver vazia, remova o elemento da posição front.
  3. Atualize front para (front + 1) % size.

Passo 6

Vamos ver um exemplo prático. Suponha que temos uma fila de tamanho 5.
  1. Inicialmente: front = 0, rear = 0.
  2. Inserimos 1: fila = [1, -, -, -, -], rear = 1.
  3. Inserimos 2: fila = [1, 2, -, -, -], rear = 2.
  4. Inserimos 3: fila = [1, 2, 3, -, -], rear = 3.
  5. Inserimos 4: fila = [1, 2, 3, 4, -], rear = 4.
  6. Tentativa de inserir outro elemento: (4 + 1) % 5 == 0, que é igual a front = 0, então a fila está cheia. Não é possível inserir mais elementos.
  7. Removemos um elemento: remove 1, fila = [-, 2, 3, 4, -], front = 1.
  8. 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.

Exercícios relacionados