Estrutura de dados e algoritmos - fila

Fila é uma estrutura de dados abstrata, um tanto semelhante a Pilhas. Ao contrário das pilhas, uma fila está aberta em ambas as extremidades. Uma extremidade é sempre usada para inserir dados (enfileirar) e a outra é usada para remover dados (desenfileirar). A fila segue a metodologia First-In-First-Out, ou seja, o item de dados armazenado primeiro será acessado primeiro.

Um exemplo do mundo real de fila pode ser uma estrada de mão única de faixa única, onde o veículo entra primeiro e sai primeiro. Mais exemplos do mundo real podem ser vistos como filas nos guichês e pontos de ônibus.

Representação de fila

Como agora entendemos que na fila, acessamos ambas as extremidades por motivos diferentes. O diagrama a seguir fornecido abaixo tenta explicar a representação da fila como estrutura de dados -

Como nas pilhas, uma fila também pode ser implementada usando Arrays, Linked-lists, Pointers e Structures. Para fins de simplicidade, devemos implementar filas usando uma matriz unidimensional.

Operações básicas

As operações de fila podem envolver inicializar ou definir a fila, utilizá-la e, em seguida, apagá-la completamente da memória. Aqui, devemos tentar entender as operações básicas associadas às filas -

enqueue() - adicionar (armazenar) um item à fila.
dequeue() - remover (acessar) um item da fila.

Poucas funções a mais são necessárias para tornar eficiente a operação de fila mencionada acima. Estes são -

peek() - Obtém o elemento na frente da fila sem removê-lo.
isfull() - Verifica se a fila está cheia.
isempty() - Verifica se a fila está vazia.

Na fila, sempre retiramos da fila (ou acessamos) dados, apontados por front ponteiro e enquanto enfileiramos (ou armazenamos) dados na fila, ajudamos rear ponteiro.

Vamos primeiro aprender sobre as funções de suporte de uma fila -

olhadinha()

Esta função ajuda a ver os dados no frontda fila. O algoritmo da função peek () é o seguinte -

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implementação da função peek () na linguagem de programação C -

Example

int peek() {
   return queue[front];
}

está cheio()

Como estamos usando um array de dimensão única para implementar a fila, apenas verificamos se o ponteiro traseiro atinge MAXSIZE para determinar se a fila está cheia. No caso de mantermos a fila em uma lista ligada circular, o algoritmo será diferente. Algoritmo da função isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementação da função isfull () na linguagem de programação C -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

está vazia()

Algoritmo da função isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Se o valor de front for menor que MIN ou 0, indica que a fila ainda não foi inicializada, portanto, está vazia.

Aqui está o código de programação C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Operação de enfileiramento

As filas mantêm dois indicadores de dados, front e rear. Portanto, suas operações são comparativamente difíceis de implementar do que as de pilhas.

As etapas a seguir devem ser realizadas para enfileirar (inserir) dados em uma fila -

Step 1 - Verifique se a fila está cheia.
Step 2 - Se a fila estiver cheia, produza um erro de estouro e saia.
Step 3 - Se a fila não estiver cheia, incremente rear ponteiro para apontar o próximo espaço vazio.
Step 4 - Adicione o elemento de dados ao local da fila, para onde a parte traseira está apontando.
Step 5 - sucesso de retorno.

Às vezes, também verificamos se uma fila foi inicializada ou não, para lidar com qualquer situação imprevista.

Algoritmo para operação de enfileiramento

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Implementação de enqueue () na linguagem de programação C -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Operação de desenfileiramento

Acessar dados da fila é um processo de duas tarefas - acessar os dados onde frontestá apontando e remove os dados após o acesso. As seguintes etapas são realizadas para realizardequeue operação -

Step 1 - Verifique se a fila está vazia.
Step 2 - Se a fila estiver vazia, produz um erro de underflow e sai.
Step 3 - Se a fila não estiver vazia, acesse os dados onde front está apontando.
Step 4 - Incrementar front ponteiro para apontar para o próximo elemento de dados disponível.
Step 5 - Retorno com sucesso.

Algoritmo para operação de desenfileiramento

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Implementação de dequeue () na linguagem de programação C -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Para um programa de fila completo em linguagem de programação C, clique aqui .