C Implementação de fila estática

[Lee Zen]

Olá amigos sou novo aqui preciso de uma ajudinha, preciso implementar um código, envolvendo fila estática, gostaria de saber como  implementar uma fila estática somente com duas funções a "enfileirar" e "desenfileirar"  alguém tem alguma ideia de como fazer isso?

[devair1010]

@Lee Zen   olá  ,  desculpe  ,   postar um link do youtube ,   mas nesse aqui tem uma aula de fila estatica :

https://www.bing.com/videos/search?q=fila+estática+no+c&docid=608045984900983751&mid=DC09FB1F4523726063F5DC09FB1F4523726063F5&view=detail&FORM=VIRE 

[arfneto]

Essa é uma nomenclatura infeliz, mas é real. Claro que não existem filas estáticas ou pilhas estáticas ou algo assim.

 

Uma fila não pode ser estática, e não ajuda em nada popularizar um nome tão besta, mas autores escrevem assim. Não autores famosos, imagino, porque por exemplo não me lembro de ter visto referências a filas estáticas em livros clássicos, como a biblia dos algoritmos, ou o livro de Weiss. Mas não é difícil achar referências a essas coisas, como @devair1010 mostrou essa aula em português

  

 

Então como implementar isso?

 

Não muda nada. Claro que os métodos são os mesmos e a estrutura é a mesma. Apenas os ponteiros não apontam para endereços de memória e sim para deslocamentos (índices) em um vetor pré-existente.

 

Citação

a estrutura é implementada usando vetores alocados estaticamente

 

Só isso.

 

17 horas atrás, Lee Zen disse:

como  implementar uma fila estática somente com duas funções a "enfileirar" e "desenfileirar"  alguém tem alguma ideia de como fazer isso?

 

Como o vetor vai estar presente desde o início na hora de implementar aparece o problema do que fazer com o vetor ao retirar alguém da fila: vai deslocar todo mundo ou vai ter um ponteiro para um início móvel?

 

Um modelo real

 

O móvel ao lado serve para entender o que acontece: tem uma fila de 3 lugares. "Estática"  . Podiam ser 3000. É só comprar mais bancos e alugar um galpão Quando chegar alguém e não tiver assento livre o alguém vai embora. O tamanho do galpão no caso do programa é a memória alocada. Só isso. 

 

E tem duas possibilidades: (a) o cara a ser atendido é sempre o primeiro ou o atendente tem uma senha, um papel marcando quem será o próximo. Ao sair o cara os que estiverem na fila se deslocam para a esquerda e a fila "estática" anda. Ou (b) o cara que está atendendo sabe qual o próximo a ser atendido e quem chega se senta na primeira posição livre.

 

Apenas decida o algoritmo e implemente. Os prós e contras são os mesmos do mundo real.

 

Escreva em torno dos dados

 

Uma fila é uma fila de alguma coisa. Pode ser uma fila de letrinhas ou uma fila de números, como os clássicos primeiros exercícios de lista que eu já vi nesse forum. Pode ser a fila de livros, a fila de alunos, a fila de carros, a tal playlist, são os exercícios mais elaborados que sempre vejo aqui. Tanto faz. 

 

Filas são abstrações. Todas essas estruturas de dados são claro abstrações. E são coleções de coisas. Tem esse nome em java. Em C++ são chamadas de containers.

 

Implementando uma fila

 

É claro que não faz faz diferença se a fila é estática (não existe isso) ou dinâmica ou azul. É uma fila.

 

Fila de que? Uma fila de Node.

 

typedef struct
{
    Dado*    d;
    unsigned prox;

} Node;

 

Uma fila é um container. Na fila tem uma série de algo. Cada elemento na fila é em geral chamado de Node. E dentro dele tem um Dado e mais umas coisas que são chamadas em geral de metadados, que permitem navegar na coisa. Uma fila é uma lista ligada. Não é sempre preciso ter um ponteiro para cada lado, já que no geral de fila o que importa para o cara que entra na fila é "atrás de quem ele está". E para quem atende o que importa é "quem é o próximo".

 

O que é Dado? Tanto faz: a fila é sempre a fila: a fila do banco é igual a fila do médico, que é igual a fila da padaria, que é igual à fila de produtos esperando para serem embalados na linha de produção da fábrica.

 

Note que a fila aqui é "estática":  os ponteiros são números. É a única diferença. 

 

Um Dado que é um Aluno

 

typedef struct
{
    char* nome;
    char  matricula[15];
    int   id;
    int*  materias;

} Aluno;

typedef Aluno Dado;

 

Pronto: é uma fila de Aluno agora.  Mas e a fila em si?

 

#define CAP_FILA (42)
typedef struct
{
    Node     el[CAP_FILA];  // a fila toda
    unsigned capacidade;
    unsigned tamanho;
    unsigned prox;  // o cara a ser atendido

}   Fila;

 

Pronto: uma fila "estática" de 42 lugares: de el[0] a el[41].

 

E o que fazer com a fila?

 

Uns métodos, na nomenclatura C++: funções em C
 

int   entra(Dado*, Fila*);  // o cara entra na fila
Dado* atende(Fila*);
int   empty(Fila*);
int   size(Fila*);

int teste(Fila*);  // teste: mostra a fila toda

 

O clássico: empty() retorna 1 se a fila está vazia, size() retorna o tamanho da fila, entra() coloca alguém na fila e sai() atende alguém. O de sempre.

 

O teste() é importante porque esse é um programa de estudo. Uma fila nunca tem isso, mas aqui precisa de uma função para mostrar tudo que tem na fila, os índices e os caras um por um. Nunca estaria numa implementação real.

 

Um exemplo de fila 

 

#define CAP_FILA (42)
#include "iso646.h"
#include <stdio.h>

typedef struct
{
    char* nome;
    char  matricula[15];
    int   id;
    int*  materias;

} Aluno;

typedef Aluno Dado;

typedef struct
{
    Dado*    d;
    unsigned ant;
    unsigned prox;

} Node;

typedef struct
{
    Node     el[CAP_FILA];  // um elemento na fila
    unsigned capacidade;
    unsigned tamanho;
    unsigned prox;  // o cara a ser atendido

}   Fila;

int   entra(Dado*, Fila*);  // o cara entra na fila
Dado* atende(Fila*);
int   empty(Fila*);
int   size(Fila*);

int teste(Fila*);  // teste: mostra a fila toda

int main(void)
{
    Fila uma;
    Fila outra;
    Fila andar[12];  // 12 andares com fila
    Fila* F = &uma;  // um ponteiro para a fila

    uma.capacidade = CAP_FILA;
    uma.tamanho    = 0;
    printf("Tamanho da Fila: %u\n", size(&uma));
    return 0;
}

int   entra(Dado* d, Fila* f) { return 0; };
Dado* sai(Fila* f) { return NULL; };
int   empty(Fila* f) { return 0; };
int   size(Fila* f) { return 0; };

int teste(Fila* f) { return 0; };

 

E até compila. Uma fila "estática" com capacidade para 42 elementos. No caso uma fila de Aluno. Escrevendo a partir dos dados e juntando o que estava no exemplo acima.