Listas Lineares
Estrutura de Dados
Listas Lineares


Agrupar itens para melhor a manipulação
Exemplos práticos:





Lista de compras
Lista de aviões que devem decolar
Lista de processos no estado pronto
Lista de serviços de impressão (spooled file)
Classificadas conforme o seu tipo de acesso
Estrutura de Dados
Listas Lineares
Classificação
Listas Lineares
Pilha
Fila
Entrada restrita
Estrutura de Dados
Fila Dupla
Saída restrita
Listas Lineares


Conjunto de elementos (nós) agrupados de forma a
preservar a relação de ordem linear entre eles
Algumas operações:









Acesso a um determinado elemento
Inserção de elementos
Remoção de elementos
Cópia de Listas
Combinação de Listas
Particionamento de Listas
Ordenação de Listas
Exclusão de Listas
Outras...
Estrutura de Dados
Listas Lineares
Alocação

Alocação Estática


Durante a compilação
Alocação Dinâmica

Durante a execução
Estrutura de Dados
Listas Lineares
Formas de Agrupamento

Forma Seqüencial


Espaço contínuo na memória
Vantagem:


Fácil acesso ao endereço de memória
(pode-se utilizar uma fórmula)
Desvantagem:

Inserir ou Remover elementos do meio da
Lista
Estrutura de Dados
Listas Lineares
Formas de Agrupamento

Forma Encadeada (E, f)



Células dispersas na memória
Cada elemento armazena sua informação e o
endereço da próxima posição de memória
Vantagem:


Facilidade na inserção ou remoção de um
elemento em qualquer ponto da lista
Desvantagem:

Manipulação de um elemento específico da lista
Estrutura de Dados
Listas Lineares - Pilhas

Todos os acessos são realizados em uma só
extremidade: TOPO

LIFO – Last In, First Out (Último a entrar é o
primeiro a sair)

Porta-guardanapo

Pilha de Pratos
Estrutura de Dados
Listas Lineares - Pilhas
ENTRADA
SAÍDA
TOPO
Elemento 2
Elemento 1
BASE
Estrutura de Dados
Listas Lineares - Pilhas

Operações primitivas







Inicializar a pilha
Pilha Vazia
Pilha Cheia
Empilhar Elemento (inserir)
Desempilhar Elemento (remover)
Topo
Demonstração: Estacionamento de Trens
Estrutura de Dados