Estruturas de Dados lineares

Estruturas de dados são construções de dados que podem ser implementadas por uma linguagem de programação. Aprender a projetar EDs genéricas e eficientes é importante para saber escolher a certa para usar no programa: a escolha da ED afeta os algoritmos que podem ser utilizados, sendo mais ou menos eficientes, e para os mesmos dados, a ED pode ocupar mais ou menos espaço.
Nesse período serão estudadas EDs lineares: pilhas, filas e listas.
Definição formal de lista:
seqüência linear de 0 ou mais itens ou elementos cuja principal propriedade estrutural é a posição relativa dos elementos na seqüência:
 xi precede xi+1 para 1 <= i <= n - 1;
 xi sucede xi-1 para 2 <= i <= n;
 xi é o i-ésimo elemento da lista, x1 é o primeiro e xn é o último, sendo n o número de elementos (tamanho da lista).

Alguns tipos de listas:
 FIFO: First In First Out - o primeiro a entrar é o primeiro a sair
 LIFO: Last In First Out - o último a entrar é o primeiro a sair
 LRU: Least Recently Used - ordem dos menos utilizados recentemente
 MRU: Most Recently Used - ordem dos mais utilizados recentemente
 LFU: Least Frequently Used - ordem dos menos frequentemente utilizados
 MFU: Most Frequently Used -  ordem dos mais frequentemente utilizados

Pilhas e filas são variações de listas. Por exemplo, uma lista FIFO funciona como uma fila e uma LIFO, como uma pilha.

Alocação estática e dinâmica de memória:
Alocação estática de memória é gerenciada pelo compilador e alocada na stack memory. Quando você declara um vetor, por exemplo, ele tem o tamanho definido (no programa ou em tempo de execução, mas é sempre AQUELE tamanho) e já é alocado num espacinho contínuo quando seu programa compila. O acesso a cada elemento do vetor é aleatório e tem mesmo custo: basta ir ao vetor[indice] e pronto.
Alocação dinâmica de memória é gerenciada pelo programador e alocada na parte da memória denominada dynamic heap. Por exemplo: numa lista encadeada, não há um número fixo de elementos. O tamanho da lista é limitado apenas pela memória (heap e virtual), sendo, assim, uma estrutura muito versátil. Portanto, a criação E EXCLUSÃO deles deve ser pensada por você. Lembrando que é muito importante excluir elementos "inúteis" senão eles ficam ocupando memória e não são apagados quando seu programa é fechado. O acesso aos elementos da lista encadeada tem custo diferente para cada um, pois é sequencial. Então, se o elemento buscado for o último, a lista vai ter que ser percorrida inteira, cada elemento apontando para o próximo, até chegar no desejado.
Listas estáticas são implementadas com vetores (coleção fixa de elementos do mesmo tipo armazenados de forma contígua e acessíveis por um índice que têm correspondência direta e sequencial com a memória)
Listas dinâmicas, ligadas ou encadeadas são implementadas com ponteiros. Para entender isso basta ir ao resuminho de PC 1!