Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

lesiano

Queue

Mensagens Recomendadas

lesiano

Boas;

Para a seguinte definição:

typedef struct queue{
             int tam,fst;
             int qu[max];
             }

Alguém me consegue explicar porque é que a inserção de um elemento é feita em:

qu[(q->fst+q->tam)%max];

? Eu sei que assim a função fica em tempo constante em vez de linear, só não percebo muito bem é aquela conta. Também tenho ideia da divisão inteira obrigar a posição a "cair" em max, mas gostava de uma explicação melhor.

Thanks.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Isso é feito de modo a reutilizar o espaço alocado para a fila e assume que a fila nunca tem mais de "max" elementos.

A "cabeça" da fila, é o "fst" (que deve ser uma referência a first element) e a fila tem "tam" elementos. Para retirar um elemento, é usada a cabeça da fila e para inserir um elemento, este deve ser inserido no fim da fila, ou seja, 1ºelemento+tamanho.

Numa implementação trivial, só podias inserir "max" elementos na fila. Estes eram colocados nas posições 0,1,2...max-1. No entanto, se assumires que nunca existem mais do que "max" elementos activos na fila, podes reutilizar o espaço usando o array de forma circular.

Aquela formula serve para que os elementos sejam inseridos nas posições 0, 1, 2, ... max-1, 0, 1, ...max-1, 0, 1, ...


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.