Filas - Fila Circular Programação Avançada I 1 FILAS (Queues) -Estrutura linear de acesso seqüencial que mantém seus elementos em seqüência cronológica de entrada; -Estrutura FIFO (First In First Out) a ordem de saída é a mesma ordem de entrada (o 1o a entrar é o 1o a sair da fila); -Diferentemente da pilha uma fila pode ser manipulada pelas duas extremidades, conhecidas como inicio e fim (ou frente e cauda, etc); - Restrições quanto à manipulação: inserções sempre no final, remoções sempre do início da fila; 2 FILA ESTÁTICA (SOBRE UM VETOR) C/ DESCRITOR 1) Sem compactação typedef struct { int *vetFila; /* ponteiro para um vetor de inteiros */ int comprimentoDoVetor; /*numero de elementos */ int inicio; /*indexa o início da fila */ int fim; /*indexa o final da fila */ } Fila; Inserções incrementam o FIM, remoções incrementam o INICIO (INICIO e FIM variando); a) Inicialização: FIM = -1, INICIO = 0; b) Tamanho da Fila = FIM – INICIO + 1; c) Fila vazia : FIM < INICIO; d) Fila cheia (?!): FIM == ComprimentoDoVetor - 1; 3 inicio fim a) b) 0 0 -1 -1 c) d) e) f) g) h) ... ) 0 0 0 1 2 3 ... 2 0 1 2 2 2 2 ... 3 vetFila[ 4 ] 0 1 2 3 X0 X0 X1 X0 X1 X2 X1 X2 X2 ... ... ... ... Ym Yn Interpretação fila recém criada tentativa de remoção ERRO: fila vazia inseriu X0 inseriu X1 inseriu X2 removeu removeu removeu ... tentativa de inserção ERRO (?!?!): fila cheia 4 ??? 2) Compactando a Fila — Movimentação de Dados A cada remoção move-se toda a fila na direção do seu inicio de forma a preencher o espaço deixado pela remoção: for (i=0; i < tamanhoFila; i++) p->vetFila[i]=p->vetFila[i+1]; p->final -= p->inicio; p->inicio = 0; Portanto: As inserções incrementam o FIM mas o INICIO fica fixo no início do vetor (zero); a) Tamanho da fila FIM - INICIO + 1 = FIM - 0 +1 = FIM+1; b) Inicialização: FIM = -1, INICIO = 0; c) Fila vazia : FIM < INICIO; 5 d) Fila cheia : FIM = comprimentoDoVetor - 1 inicio fim 0 a) b) c) d) e) f) g) h) i) vetFila[4] 1 2 3 0 0 0 0 -1 0 1 2 2 X0 X0 X0 0 1 X1 X2 0 0 2 2 X1 X2 X2 0 1 X2 X3 0 0 2 3 X2 X2 X3 X3 X1 X1 X1 X2 X2 X3 X3 X4 X4 X5 Interpretação fila recém criada inseriu X0 inseriu X1 inseriu X2 removeu e compactou (moveu fila à esquerda) inseriu X3 removeu e compactou (moveu fila à esquerda) inseriu X4 inseriu X5 fila realmente cheia !!!!!!6 3) Solução híbrida - Compactando na hora certa INICIO variável, como feito na alternativa 1, aliado à compactação como em 2. Ao invés da compactação ocorrer a cada remoção, o critério para realiza-la seria detectar um falso sinal de “fila cheia”: inserção( ) /* fila cheia fim== comprimentoDoVetor-1 */ Se (fila cheia) /* tamanhoDaFila = FIM - INICIO + 1 */ Se(tamanhoDaFila < comprimentoDoVetor) for(i=0; i < tamanhoDaFila; i++) p->vetFila[i]=p->vetFila[i+inicio]; p->final -= p->inicio; p->inicio = 0; // inserção no final da fila; Senão FILA realmente cheia; Senão .......... 7 inicio fim 0 a) b) 0 0 -1 -1 c) d) e) f) 0 0 0 0 1 2 2 0 0 0 1 2 3 3 3 3 1 1 g) h) i) X0 X0 X0 X0 X2 X2 vetFila[4] 1 2 3 X1 X1 X1 X1 X3 X3 X2 X2 X2 X2 X2 X4 X3 X3 X3 X3 Interpretação fila recém criada remoção ERRO: fila vazia inseriu X0 inseriu X1 inseriu X2 inseriu X3 removeu removeu inserção X4: compactou e insere 8 Independentemente da opção 2 ou 3, a compactação da Fila pode ser uma operação bastante lenta. Se a estrutura possuir N posições e a fila de dados possuir N-1 elementos, serão necessárias N-2 movimentos, dos N-2 elementos desde o final da fila. 9 4) Fila Circular Considera o vetor como um arranjo circular, como se o seu final se ligasse ao seu início, não havendo interrupção. Na implementação sobre um vetor (ESTÁTICA) a fila circular torna-se bastante vantajosa, pois viabiliza a reutilização das posições desocupadas sem a necessidade de movimentação de dados. CONSEQÜÊNCIA: FIM < INICIO NÃO MAIS IMPLICA EM FILA VAZIA 10 inicio fim 2 5 2 0 vetFila[ 6 ] 0 1 2 ... 5 .... .... X0 ... X3 operação Interpretação ..... ...... J) K) J) X4 .... X0 ... X3 insere X4 fim < inicio fila Não em modo vazia Fila circular K) Aqui consideraremos que a partir do INICIO alcança-se o FIM 11 explorando a fila no sentido horário: X0,X1,X2,X3,X4 E agora... Se FIM < INICIO não mais implica em fila VAZIA ! Como testar tal condição ? Acrescentando-se um campo tamanhoDaFila à estrutura interna do TDA fila, o qual serviria como parâmetro para definir se o estado da fila é vazia ou cheio independentemente de INICIO e FIM. a) Inicialização: FIM = -1, INICIO = 0; b)Tamanho da fila dado explicito na estrutura; c) Fila vazia : tamanhoDaFila = 0; d) Fila cheia : tamanhoDaFila = comprimentoDoVetor 12 Estrutura Fila Circular Estática: typedef struct { int *vetFila; int comprimentoDoVetor; int inicio; /* indexa o início da Fila */ int fim; /*indexa o final da Fila */ int tamanhoDaFila; /* testes de vazia/cheia */ } Fila; ...... Fila fi, f*; f=&fi; 13 inicio fim tamanho 0 a) b) c) d) e) f) g) h) i) j) k) 0 0 0 0 1 1 2 3 3 3 3 -1 0 1 2 2 3 3 0 1 2 2 0 1 2 3 2 3 2 2 3 4 4 l) m) n) o) 0 1 2 3 2 2 2 2 3 2 1 0 X0 X0 X0 X4 X4 X4 X4 X4 vetFila[ 4 ] 1 2 3 X1 X1 X1 X1 X5 X5 X5 X5 X5 X2 X2 X2 X2 X6 X6 X6 X6 X6 X3 X3 X3 X3 X3 X3 Interpretação fila recém criada inseriu X0 inseriu X1 inseriu X2 removeu inseriu X3 removeu inseriu X4 inseriu X5 inseriu X6 inserção X7 ERRO: fila CHEIA removeu removeu removeu removeu: tamanho = 0 fila VAZIA !!! 14 Inserção(int novo ) SE(tamanhoDaFila < comprimentoDoVetor) /* há espaço no início do vetor */ SE (f->fim = = f->comprimentoDoVetor-1) /* utilize o aspecto circular */ f->fim = 0; f->vetFila[f->fim]=novo; SENÃO f->vetFIla[++(f->fim)]=novo; f->tamanhoDaFila ++; SENÃO /*fila realmente cheia!! */ Alternativa p/ controle da “circularidade”: SE (FIM == tamanhoDoVetor - 1) Sentido da FIM = (FIM+1) % tamanhoDoVetor; circulação vetor[FIM] = novo; tamanhoDaFila ++; 15 Remoção( ) SE(f->tamanhoDaFila = = 0) //fila vazia SENÃO SE (f->inicio = =f->comprimentoDoVetor-1) f->inicio= 0; SENÃO f->inicio++; f-> tamanhoDaFila - -; Alternativa p/ controle da “circularidade”: Sentido da circulação SENÃO INICIO = (INICIO+1)% ComprimentoDoVetor; tamanhoDaFila - -; 16 (Outra alternativa para gerenciar inicio/fim na fila circular) b) Abrir mão de um espaço na fila fazendo INICIO ser sempre uma posição antes do inicio real da Fila, então: se INICIO = = FIM => fila vazia como em (a); se (FIM+1) = = INICIO => fila cheia como em (m); 17