Analise De Sistemas

3.1 FILA

As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila. A operação DEQUEUE só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.

a. Pilha

As pilhas são estruturas baseadas no princípio LIFO (last in, first out), na qual os dados que foram inseridos primeiros na pilha serão os últimos a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.

b. Em uma lista simplesmente encadeada, cada elemento possui apenas informação de quem é seu sucessor. É necessário também armazenar a informação do primeiro elemento da lista.

Principais problemas:

Impossibilidade de voltar ao elemento anterior

Necessidade de guardar informação do elemento anterior a fim de realizar algumas operações.

c. A estrutura de lista simplesmente encadeada vista na seção anterior caracteriza-se por formar um encadeamento simples entre os seus nós. Dessa forma, cada nó desta lista contém um referência para o nó seguinte, o que nos permite percorrer toda alista encadeada a partir do primeiro nó (do início para o fim). Porém,neste tipo de lista, não temos uma eficiência para percorrer a lista do fim para o início. Ainda mais, a remoção de um elemento de uma lista simplesmente encadeada também é uma tarefa difícil. Mesmo conhecendo a posição do elemento a ser removido, teremos que percorrer toda a lista, nó por nó, a fim de encontrarmos o elemento anterior, pois, dado um determinado nó, não temos como acessar diretamente o nó anterior.A fim de solucionar esses problemas, podemos utilizar uma estrutura de dados conhecida como lista duplamente encadeadas. Uma lista duplamente encadeada é aquela em que cada nó possui duas Referências, ao invés de uma só. A primeira é usada para indicar o nó sucessor (da mesma forma que lista simplesmente encadeada), enquanto que a segunda é usada para apontar para o nó predecessor (nó anterior). Desta forma, dado um nó qualquer da lista, podemos acessar ambos os nós adjacentes: o próximo e o anterior.

d.

e. Depende do tamanho e do volume de inserções e exclusões de sua lista.

Numa lista duplamente encadeada, por possuir ponteiros para o nó anterior e para o nó posterior, estas operações são menos dispendiosas, pois não há necessidade de se percorrer novamente a lista a partir do início como é o caso das listas simplesmente encadeadas.

Na época em que a memória disponível, RAM ou HD, era cara e limitada fazia mais sentido economizar o espaço de alocação de um ponteiro, atualmente normalmente se opta por otimizar as operações e não pela economia de memória (é óbvio que existem

...