Implementando a Estrutura de Dados Fila em C

Introdução

Neste projeto, você aprenderá como implementar uma estrutura de dados de fila (queue) em C. Filas são amplamente utilizadas em ciência da computação, por exemplo, em filas de mensagens que são usadas para transmitir dados em um computador.

👀 Visualização

$ gcc queue.c -o queue
$ ./queue
11250

🎯 Tarefas

Neste projeto, você aprenderá:

• Como implementar o método front() para retornar o valor do elemento da frente na fila
• Como implementar o método pop() para remover e retornar o elemento da frente da fila
• Como implementar o método count() para retornar o número de elementos atualmente na fila
• Como implementar o método is_empty() para verificar se a fila está vazia

🏆 Conquistas

Após concluir este projeto, você será capaz de:

• Compreender as operações básicas de uma estrutura de dados de fila
• Implementar os métodos principais de uma fila em C
• Aplicar seu conhecimento de filas para resolver problemas do mundo real

Implementar o Método front()

Nesta etapa, você aprenderá como implementar o método front() da fila.

O método front() deve retornar o valor do elemento da frente na fila. Se a fila estiver vazia, o método deve sair do programa com exit(-1).

Siga os passos abaixo para completar esta etapa:

1. Abra o arquivo queue.c localizado em /home/labex/project/queue.c.
2. Localize o método front() no código.
3. Implemente o método front() da seguinte forma:

static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

O método front() primeiro verifica se o ponteiro phead é NULL, o que indica uma fila vazia. Se a fila estiver vazia, o método sai do programa com exit(-1).

Se a fila não estiver vazia, o método retorna o valor armazenado no nó phead, que representa o elemento da frente da fila.

Implementar o Método pop()

Nesta etapa, você aprenderá como implementar o método pop() da fila.

O método pop() deve remover e retornar o elemento da frente da fila. Se a fila estiver vazia, o método deve sair do programa com exit(-1).

Siga os passos abaixo para completar esta etapa:

1. Abra o arquivo queue.c localizado em /home/labex/project/queue.c.
2. Localize o método pop() no código.
3. Implemente o método pop() da seguinte forma:

static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

O método pop() primeiro verifica se o ponteiro phead é NULL, o que indica uma fila vazia. Se a fila estiver vazia, o método sai do programa com exit(-1).

Se a fila não estiver vazia, o método armazena o valor do nó phead, que representa o elemento da frente da fila. Em seguida, ele atualiza o ponteiro phead para o próximo nó, removendo efetivamente o elemento da frente da fila. Finalmente, o método retorna o valor armazenado.

Implementar o Método count()

Nesta etapa, você aprenderá como implementar o método count() da fila.

O método count() deve retornar o número de elementos atualmente na fila.

Siga os passos abaixo para completar esta etapa:

1. Abra o arquivo queue.c localizado em /home/labex/project/queue.c.
2. Localize o método count() no código.
3. Implemente o método count() da seguinte forma:

static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

O método count() inicializa uma variável cnt com 0. Em seguida, ele percorre a fila seguindo os ponteiros next do nó phead e seus sucessores. Para cada nó encontrado, ele incrementa a variável cnt. Finalmente, o método retorna o valor de cnt, que representa o número de elementos na fila.

Implementar o Método is_empty()

Nesta etapa, você aprenderá como implementar o método is_empty() da fila.

O método is_empty() deve retornar 1 se a fila estiver vazia e 0 caso contrário.

Siga os passos abaixo para completar esta etapa:

1. Abra o arquivo queue.c localizado em /home/labex/project/queue.c.
2. Localize o método is_empty() no código.
3. Implemente o método is_empty() da seguinte forma:

static int is_empty() {
    return phead == NULL;
}

O método is_empty() simplesmente verifica se o ponteiro phead é NULL, o que indica uma fila vazia. Se phead for NULL, o método retorna 1, indicando que a fila está vazia. Caso contrário, ele retorna 0, indicando que a fila não está vazia.

Parabéns! Você agora implementou todos os métodos necessários para a estrutura de dados da fila. Agora você pode compilar e executar o programa para testar a funcionalidade da fila.

4. Compilar e executar:

$ gcc queue.c -o queue
$ ./queue
00000

A saída esperada é a seguinte:

$ gcc queue.c -o queue
$ ./queue
11250

Resumo

Parabéns! Você concluiu este projeto. Você pode praticar mais laboratórios no LabEx para aprimorar suas habilidades.