pocotó

Exercícios

1. Que conjunto de condições é necessário e suficiente para que uma seqüência de operações insert e remove sobre uma única fila vazia deixe a fila vazia sem provocar underflow? Que conjunto de condições é necessário e suficiente para que essa seqüência deixe inalterada uma fila não-vazia?

2. Se um vetor armazenando uma fila não é considerado circular, o texto sugere que cada operação remove deve deslocar para baixo todo elemento restante de uma fila. Um método alternativo é adiar o deslocamento ate que rear seja igual ao ultimo índice do vetor. Quando essa situação ocorre e faz-se uma tentativa de inserir um elemento na fila, a fila inteira é deslocada para baixo, de modo que o primeiro elemento da fila fique na posição 0 do vetor. Quais são as vantagens desse método sobre um deslocamento em cada operação remove? Quais as desvantagens? Reescreva as rotinas remove, insert e empty usando esse método.

3. Podemos evitar sacrificar um elemento de uma fila se um campo qempty for incluído na representação da fila. Demonstre como isso pode ser feito e reescreva as rotinas de manipulação da fila sob essa representação.

4. Como você implementaria uma fila de pilhas? Uma pilha de filas? Uma fila de filas? Escreva rotinas para implementar as operações corretas para cada uma destas estruturas de dados.

5. Demonstre como implementar uma fila C de inteiros, usando um vetor queue [100], onde queue [0]é usado para indicar o inicio da fila, queue[1] é usado para indicar o final da fila, e queue [2] a queue [99] são usados para conter elementos do vetor. Demonstre como inicializar esse vetor de modo a representar fila vazia e escreva rotinas remove, insert e empty para tal implementação.

6. Demonstre como implementar uma fila C, na qual cada item consista em um numero variável de inteiros.

7. Implemente uma fila de prioridade ascendente e suas operações, pqinsert, pqmindelete e empty, usando cada um dos quatro métodos apresentados no texto.