Baixe o app para aproveitar ainda mais
Prévia do material em texto
Listas Luciano Soler Listas - Definição Uma lista linear é um conjunto (coleção) de n>=0 nós (elementos) L1, L2, ..., LN tais que suas propriedades estruturais decorrem, unicamente, da posição relativa dos nós dentro da sequência linear (SZWARCFITER, 1994). Listas Tem-se: se n>0, L1 é o primeiro nó, para 1 < k <= n, o nó Lk é precedido por Lk-1. As operações mais frequentes em listas são: a busca, a inclusão e a remoção de um determinado elemento. essas operações podem ser efetuadas em qualquer posição da lista. Se forem consideradas apenas operações restritas aos extremos da lista temos casos especiais de estruturas de dados amplamente utilizadas na solução de problemas. Listas LISTA PILHA Inserções, remoções e acessos são realizados em um único extremo FILA Todas as inserções são feitas num único extremo e todas remoções e acessos são realizados no outro. FILA DUPLA (DEQUE) Double- Ended- Queue Fila de extremidade Dupla. Inserções, Remoções ou acessos são realizados em qualquer extremo. FDER Fila Dupla de Entrada Restrita. Inserção restrita a um único extremo. FDSR Fila Dupla de Saída Restrita. Remoção restrita a um único extremo. Pilha - Definição Pilha é uma lista linear onde os elementos podem ser inseridos e removidos apenas de uma extremidade chamada de topo. Esta disciplina de acesso determina que “o último elemento que entra é o primeiro a sair” (LIFO – Last in First out). Pilha - Exemplos Para que serve a PILHA? Pilha serve para ordenar a entrada e saída de elementos. Onde eu aplico PILHA? A Pilha é aplicada na resolução de problemas onde a ordem de entra e saída dos elementos interfere no resultado final. Exemplos Ordem de abertura de janelas (linux, windows) Inclusão de imagens do PowerPoint Ctrl + Z Voltar (navegadores) Pilha de livros ou Pilha de pratos. Pilha http://www.cheeseandburger.com/ Pilha – Operações Fundamentais Empilhar (push) – Insere um elemento no topo da pilha Se a implementação impuser limitação no espaço para a pilha é preciso verificar se a PILHA está CHEIA (erro de OVERFLOW) Desempilhar (pop) – remove um elemento do topo da pilha É preciso verificar se a PILHA está VAZIA (erro de UNDERFLOW) B<TOPO> A <TOPO> A B<TOPO> A A <TOPO> Pilha Como executar as OPERAÇÕES? topo -1 0 1 2 3 1) Indicar que a pilha esta vazia 2) Inserir um elemento 3) Retirar um elemento 4) Retirar um elemento e visualizar o elemento retirado Inserir elemento -1 0 1 2 3 topo Insira os elementos A e B Inserir elemento -1 0 1 2 3 topo topo = topo+1 vetor[topo] = A Inserir elemento -1 0 1 2 3 topo topo = topo+1 vetor[topo] = B Inserir elemento -1 0 1 2 3 topo Inserir elemento -1 0 1 2 3 topo temp =vetor[topo] vetor[topo] = null topo = topo-1 retorno Inserir elemento -1 0 1 2 3 topo Pilha Demais Operações Acessar elemento do topo (top) Checar se está vazia (isEmpty) Checar se está cheia (isFull) Tamanho (size) Pilha Os elementos da Pilha são distribuídos dentro de um vetor pré-dimensionado e o topo é coordenado por um ponteiro que indica a sua posição (índice da célula do vetor). Pilha Esta alternativa de implementação possui boa performance nas operações de inclusão e exclusão. Por outro lado, o pré-dimensionamento do vetor com o número máximo de elementos pode ser subestimado ou superestimado provocando um uso inadequado da memória (principalmente em linguagens onde a alocação do vetor é estática). Pilha Referências GOODRICH, Michael T; TAMASSIA, Robert. Estruturas de dados e algoritmos em JAVA. Porto Alegre: Bookman, 2002. SZWARCFITER, Jayme Luiz; MARKENZON, Lílian. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 1994. TENENBAUM, Aaron M.; LANGSAM, Y. AUGENSTEIN, M. J. Estruturas de Dados Usando C. São Paulo: Makron Books, 1995. DEITEL, Harvey M.; DEITEL, Paul J. Java : como programar. 8. ed. Porto Alegre: Bookman, 2010.
Compartilhar