Pilhas, filas, listas - Resumo

Prévia do material em texto

Pilhas e filas:​ O elemento a ser removido deve ser especificado previamente. 
 
Pilhas: ​O último elemento que entra é o primeiro que sai (LIFO). Uma pilha com N 
elementos possui o atributo ​topo​[N], que indexa o primeiro elemento. Se 
TOPO[N]=0, a pilha está vazia. Extração de pilha vazia figura erro, que é o estouro 
negativo. O estouro positivo se dá quando se ultrapassa o limite da pilha. 
 
Operações: 
INSERT na pilha é chamado de PUSH (EMPILHAR) 
DELETE é chamado de POP (DESEMPILHAR) 
STACK-EMPTY verifica se a pilha é vazia 
 
Filas: O primeiro elemento a entrar é o primeiro a sair (FIFO). Uma fila com N 
elementos possui os atributos ​inicio ​[N], que indexa o primeiro elemento, e ​fim​[N], 
que indexa o último. Se ​inicio ​[N]=​fim​[N] a fila está vazia. Os estouros positivo e 
negativo também ocorrem na fila. 
 
Operações: 
INSERT na fila é chamado de ENQUEUE (ENFILEIRAR) 
DELETE na fila é chamado de DEQUEUE (DESINFILEIRAR 
 
Listas ligadas: Os objetos são organizados linearmente. A ordem é determinada 
por um ponteiros. A lista possui o atributo ​inicio​[N], que aponta para o primeiro 
elemento. Cada elemento de uma lista duplamente encadeada possui campos para 
os ponteiros ​proximo e ​anterior​, que apontam para o próximo ou para o elemento 
anterior a ele. Se ​proximo​[N]=NULL ele é o último da lista. Se ​anterior​[N]=NULL, ele 
é o primeiro da lista. Se ​inicio​[N]=NULL, a lista está vazia. 
 
Um lista simplesmente encadeada não tem o ponteiro ​anterior ​. Uma lista circular o 
ponteiro ANTERIOR do primeiro elemento aponta para o fim da lista, e o ponteiro 
proximo ​do último elemento aponta para o início da lista. 
 
Operações: 
LIST-SEARCH realiza pesquisa 
LIST-INSERT realiza inserção 
LIST-DELETE realiza exclusão 
 
Para excluir um elemento da lista primeiro faz a busca, e após a exclusão deve-se 
atualizar os ponteiros. 
 
Sentinelas: ​objeto que simplifica as limitações. É adicionado ao elemento dois 
campos que serão iguais a fila (​proximo e ​anterior​) mas não armazenam dados. 
Isso transforma uma lista encadeada normal em uma lista circular duplamente 
encadeada. É feito para melhorar a buscar e simplificar o processo, mas ocupa uma 
maior quantidade de memória. 
 
Ponteiros e objetos 
 
Objetos com vários arranjos: ​Quando o objeto possui os atributos ​proximo e 
anterior, ​o ponteiro é armazenado nesses espaços. O ponteiro funciona como um 
índice para o elemento. 
 
Objetos com um único arranjo: O ponteiro é o endereço da posição de memória 
de um objeto., conforme o objeto se desloca, o ponteiro aponta para o novo 
endereço. 
 
Alocação e liberação de objetos: ​Para inserir um novo item na lista é preciso 
apontar o ponteiro para um espaço não utilizado, para o novo objeto ocupar um 
espaço vago. Uma variável global aponta para o início da lista, e ela deve estar livre 
(NULL). Sempre que ela estiver livre um novo espaço na memória é alocado para a 
inserção de um objeto na lista. Se a variável estiver apontando para algum 
elemento, a lista está completa e não é mais possível inserir mais elementos.