• Document: ESTRUTURA DE DADOS PILHA
  • Size: 120.37 KB
  • Uploaded: 2019-06-13 00:17:43
  • Status: Successfully converted


Some snippets from your converted document:

Curso Superior de Tecnologia em Automação Industrial Disciplina: Programação e Estrutura de Dados – 2011/2 Aula – Estrutura de Dados – Pilha Profa Cristiane Koehler ESTRUTURA DE DADOS – PILHA CONCEITO DE PILHAS - Pilhas são listas lineares onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo. Pilha vazia Insere(A) Insere(B) Retira(B) Insere(C) Retira(C) 1 Curso Superior de Tecnologia em Automação Industrial Disciplina: Programação e Estrutura de Dados – 2011/2 Aula – Estrutura de Dados – Pilha Profa Cristiane Koehler Retira(A) DEFINIÇÃO: Dada uma pilha P=( a(1), a(2), ..., a(n) ), diz-se que a(1) é o elemento da base da pilha; a(n) é o elemento topo da pilha; e a(i+1) está acima de a(i). Pilhas são também conhecidas como listas lineares LIFO (last in first out). OPERAÇÕES ASSOCIADAS: 1. criar (P) - criar uma pilha P vazia 2. inserir (x, P) - insere x no topo de P (empilha): push(x,P) 3. vazia (P) - testa se a pilha P está vazia 4. topo (P) - acessa o elemento do topo da pilha P (sem eliminar) 5. elimina (P) - elimina o elemento do topo de P (desempilha): pop(P) IMPLEMENTAÇÃO DE PILHAS Uma estrutura de dados do tipo Pilha pode ser implementada de forma seqüencial ou encadeada. No caso geral de listas lineares ordenadas, a maior vantagem da alocação encadeada sobre a seqüencial - se a memória não for problema - é a eliminação de deslocamentos na inserção ou eliminação dos elementos. No caso das pilhas, essas operações de deslocamento não ocorrem. Portanto, podemos dizer que a alocação seqüencial é mais vantajosa na maioria das vezes. ALOCAÇÃO SEQUENCIAL DE PILHAS – Definição da Estrutura de Dados Type pilha = array [1..maxp] of TipoElem; indice = 0 .. maxp; Var P: pilha; topo: indice; 2 Curso Superior de Tecnologia em Automação Industrial Disciplina: Programação e Estrutura de Dados – 2011/2 Aula – Estrutura de Dados – Pilha Profa Cristiane Koehler OPERAÇÕES: 1. criar (P) - criar uma pilha P vazia procedure criar (Var topo:indice); begin topo := 0; end; 2. inserir (x, P) - insere x no topo de P(empilha): push (x, P). procedure push (x:TipoElem; var P: pilha; Var topo: indice); begin if topo = maxp then "PILHA CHEIA" else begin topo := topo + 1; P[topo] := x; end end; 3. vazia (P) - testa se P está vazia function vazia (topo: indice): boolean; begin vazia := (topo = 0); end; 4. topo (P) - acessa o elemento do topo da pilha (sem eliminar) procedure top (Var topo_p: TipoElem; P:pilha; topo:indice); begin if topo = 0 then "PILHA VAZIA" else topo_p := P[topo]; end; 5. elimina (P) - elimina o elemento do topo de P (desempilha): pop (P) procedure pop (var P:pilha; Var topo:indice); begin if topo = 0 then "PILHA VAZIA" else topo := topo-1; end; Devolve elemento eliminado procedure pop_up (var topo_p:TipoElem; var P:pilha; var topo:indice); begin if topo = 0 then "PILHA VAZIA" else begin topo_p := P[topo]; {no caso de acesso ao elemento} topo := topo-1; end; end; 3 Curso Superior de Tecnologia em Automação Industrial Disciplina: Programação e Estrutura de Dados – 2011/2 Aula – Estrutura de Dados – Pilha Profa Cristiane Koehler EXEMPLO DO USO DE PILHAS: Notação Polonesa Uma representação para expressões aritméticas que seja conveniente do ponto de vista computacional é assunto de interesse, por exemplo, na área de compiladores. A notação tradicional é ambígua e, portanto, obriga o pré-estabelecimento de regras de prioridade. Isso torna a tarefa computacional menos simples. Outras notações são apresentadas a seguir, considerando-se apenas operações binárias (com dois operandos): • Notação completamente Parentizada: acrescenta-se sempre um parênteses a cada par de operandos e seu operador. Exemplo: tradicional: A * B - C / D parentizada: ((A*B)-(C/D)) • Notação Polonesa: os operandos aparecem imediatamente antes dos operandos. Esta notação especifica quais operadores, e em que ordem, devem ser calculados. Por esse motivo dispensa o uso de parênteses, sem ambigüidades. Exemplo: tradicional: A * B - C / D polonesa: - * A B / C D • Notação Polonesa Reversa (ou posfix): é como a polonesa na qual os operandos aparecem após os operandos.

Recently converted files (publicly available):