Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Estruturas de Dados I Pilhas e filas Estudo de listas lineares especiais, com disciplina restrita de organização e de acesso a seus nodos Estruturas de Dados I Pilhas e filas Disciplina restrita acesso permitido somente em alguns nodos Com disciplina restrita de organização e acesso a seus nodos Listas lineares especiais Estruturas de Dados I Pilha Listas lineares especiais mais usuais Pilhas e filas Fila LIFO Last In First Out o último componente inserido é o primeiro a ser retirado FIFO First In First Out o primeiro componente inserido é também o primeiro a ser retirado Estruturas de Dados I Consultas Exclusões Inserções Topo Base Pilhas e Filas Início Final Inserções Exclusões e Consultas PILHA FILA Estruturas de Dados I Filas Duplas exclusões inserções exclusões inserções Inserções e exclusões podem ocorrer em qualquer extremidade da lista Especialização de fila Estruturas de Dados I Pilhas e filas Pilhas Estruturas de Dados I Criar uma pilha vazia Inserir um nodo no topo da pilha Remover o nodo do topo de pilha Consultar / modificar nodo do topo da pilha Destruir a pilha Operações sobre Pilhas Pilhas Estruturas de Dados I Pilhas Pilhas implementadas por contiguidade física Estruturas de Dados I Pilha - contiguidade física Índices do arranjo Pilha – contiguidade física Implementada sobre um arranjo Índices de controle da pilha: BASE da pilha TOPO atual da pilha LIMITE máximo que pode ser ocupado pela pilha Estruturas de Dados I Exemplo de manipulação de uma pilha LIM TOPO BASE PILHA 10 9 8 7 6 5 4 3 2 1 3 LIM TOPO BASE 10 9 8 7 6 5 4 3 2 1 3 7 LIM TOPO BASE 10 9 8 7 6 5 4 3 2 1 3 7 5 LIM TOPO BASE 10 9 8 7 6 5 4 3 2 1 3 7 LIM TOPO BASE 10 9 8 7 6 5 4 3 2 1 Retorna “7” 1. Inicializar pilha de valores inteiros,a partir do índice 1, máximo 10 nós 2. Inserir nodo com valor 3 3. Inserir nodo com valor 7 4. Inserir nodo com valor 5 5. Remover nodo do topo 6. Consultar pilha Pilha – contiguidade física PILHA PILHA PILHA PILHA Estruturas de Dados I Pilha – contiguidade física TipoPilha = arranjo [1..N] de TipoNodo Operações Tipo de dados utilizado nos algoritmos para pilha implementada por contiguidade física: Criar uma pilha vazia Inserir um nodo no topo da pilha Remover o nodo do topo de pilha Consultar / modificar nodo do topo da pilha Estruturas de Dados I Lim Topo Base Pilha 1. Definir valor do índice de BASE da pilha 2. Definir valor máximo de nodos que a pilha pode ter LIM 3. Indicar que a pilha está vazia através do valor de TOPO 10 9 8 7 6 5 4 3 2 1 Exemplo: Base 1 Topo Base – 1 Lim 6 Criação da pilha Pilha – contiguidade física Estruturas de Dados I Algoritmo InicializarPilhaArr Entrada: Base (inteiro) Saída: Topo (inteiro) início Topo Base – 1 fim Algoritmo: Inicializar Pilhas implementada sobre Arranjo Pilha – contiguidade física Estruturas de Dados I Lim Topo Base Pilha 10 9 8 7 6 5 4 3 2 1 Lim Topo Base Pilha 10 9 8 7 6 5 4 3 2 1 Operação PUSH Inserção de um nodo na pilha Pilha – contiguidade física Estruturas de Dados I Pilha – contiguidade física Algoritmo: Inicializar Pilhas implementada sobre Arranjo Algoritmo InserirPilhaArr Entradas: Pilha (TipoPilha) Lim (inteiro) Topo (inteiro) Valor (TipoNodo) Saídas: Pilha (TipoPilha) Topo (inteiro) Sucesso (lógico) início se Topo < Lim então início Topo Topo + 1 Pilha[Topo] Valor Sucesso verdadeiro fim senão Sucesso falso fim Estruturas de Dados I Lim Topo Base Pilha 10 9 8 7 6 5 4 3 2 1 Operação POP Pilha – contiguidade física Remoção de um nodo da pilha Estruturas de Dados I Algoritmo RemoverPilhaArr Entradas: Pilha (TipoPilha) Topo (inteiro) Base (inteiro) Saídas: Pilha (TipoPilha) Topo (inteiro) Sucesso (lógico) ValorRemovido (TipoNodo) início se Topo Base então início ValorRemovido Pilha[Topo] Topo Topo - 1 Sucesso verdadeiro fim senão Sucesso falso fim Algoritmo: Remover nodo do topo de Pilha implementada sobre Arranjo Estruturas de Dados I ? Lim Topo Base Pilha 10 9 8 7 6 5 4 3 2 1 Pilha – contiguidade física Acesso à pilha Somente ao nodo do topo da pilha Para consulta e/ou modificação Estruturas de Dados I Algoritmo ConsultarPilhaArr Entradas: Pilha (TipoPilha) Base (inteiro) Topo (inteiro) Saídas: Valor (TipoNodo) Sucesso(lógico) início se Topo Base então início Valor Pilha[Topo] Sucesso verdadeiro fim senão Sucesso falso fim Algoritmo: Consultar nodo do topo de Pilha implementada sobre Arranjo Estruturas de Dados I Pilhas Pilhas implementadas por encadeamento Estruturas de Dados I PtPilha Info Elo Topo da pilha Base da pilha Endereço do topo da pilha Pilha implementada por encadeamento TipoNodo = registro Info: TipoInfo Elo: TipoPtNodo fim registro Tipo de dados utilizado nos algoritmos: Estruturas de Dados I Pilha por encadeamento Criação de pilha encadeada Pilha criada vazia Atribuir endereço nulo para apontador que contém o endereço do topo da pilha Estruturas de Dados I Algoritmo: Criar Pilha Encadeada Pilha por encadeamento Algoritmo CriarPilhaEnc Entradas: - Saída: PtPilha (TipoPtNodo) início PtPilha nulo fim Estruturas de Dados I Topo Inserção de um nodo em pilha encadeada Topo Pilha por encadeamento Novo nodo inserido sempre no topo da pilha PtPilha PtPilha Topo Novo nodo Base Base Estruturas de Dados I Algoritmo InserirPilhaEnc Entradas: PtPilha (TipoPtNodo) Valor (TipoInfo) Saída: PtPilha (TipoPtNodo) Variável local: PtNovo (TipoPtNodo) início alocar(PtNovo) PtNovo.Info Valor PtNovo.Elo PtPilha PtPilha PtNovo fim Algoritmo: Inserir nodo em Pilha Encadeada Pilha por encadeamento Estruturas de Dados I PtPilha Topo Remoção de um nodo de uma pilha encadeada Pilha por encadeamento Topo PtPilha Base Base Só pode ser removido o nodo do topo da pilha Nodo a ser removido Estruturas de Dados I Pilha por encadeamento Algoritmo: Remover nodo de Pilha Encadeada Algoritmo RemoverPilhaEnc Entrada: PtPilha (TipoPtNodo) Saídas: PtPilha (TipoPtNodo) Sucesso (lógico) Variável local: PtAux (TipoPtNodo) início se PtPilha nulo então início PtAux PtPilha PtPilha PtPilha.Elo liberar(PtAux) Sucesso verdadeiro fim senão Sucesso falso fim Estruturas de Dados I Acesso à pilha encadeada Pilha por encadeamento Só pode ser acessado o nodo do topo da pilha Topo PtPilha Base Nodo que pode ser acessado Estruturas de Dados I Pilha por encadeamento Algoritmo: Consultar nodo do topo de Pilha Encadeada Algoritmo ConsultarPilhaEnc Entrada: PtPilha (TipoPtNodo) Saídas: Valor (TipoInfo) Sucesso (lógico) início se PtPilha = nulo então Sucesso falso senão início Sucesso verdadeiro Valor PtPilha.Info fim fim Estruturas de Dados I Pilha por encadeamento Algoritmo: Desempilhar Consulta nodo do topo da pilha, e o remove da pilha Algoritmo Desempilhar Entrada: PtPilha (TipoPtNodo) Saídas: PtPilha (TipoPtNodo) Valor (TipoInfo) Sucesso (lógico) Variável local: PtAux (TipoPtNodo) início se PtPilha = nulo então Sucesso falso senão início Sucesso verdadeiro Valor PtPilha.Info PtAux PtPilha PtPilha PtPilha.Elo liberar(PtAux) fim fim Estruturas de Dados I PtPilha = nil Base Topo Base Topo Base Topo Base Topo PtPilha PtPilha PtPilha Destruição de uma pilha encadeada Pilha por encadeamento Liberar espaço ocupado pelos nodos, sempre a partir do topo da pilha No final: apontador para o topo = endereço nulo Estruturas de Dados I Pilha por encadeamento Algoritmo: Destruir Pilha Encadeada Algoritmo DestruirPilhaEnc Entrada: PtPilha (TipoPtNodo) Saída: PtPilha (TipoPtNodo) Variável local: PtAux (TipoPtNodo) início enquanto PtPilha ≠ nulo faça início PtAux PtPilha PtPilha PtPilha.Elo liberar(PtAux) fim fim * * *
Compartilhar