Material didático para conceituar e implementar pilhas usando alocação estática sequencial

Material didático usado para ensinar o conceito de pilhas como listas restritas e apresentar possível implementação de pilhas usando memória estática sequencial em Linguagem Pascal. O material começa conceituando listas lineares, apresenta o modelo conceitual de pilhas e uma representação gráfica, discute a implementação usando alocação estática sequencial e apresenta ainda algumas aplicações. A implementação é feita com comandos básicos da linguagem Pascal com o objetivo de facilitar a aprendizagem.

1. Estruturas de Dados ► Pilhas (Linguagem Pascal ) Prof. Dr. Marcelo Duduchi Aux. Docente Lucio Nunes

2. Estruturas de Dados Ao implementarmos programas de computador estamos de certa forma tentando representar o mundo real pela computação; Os dados a serem processados no computador representam uma abstração de parte da realidade na medida em que representam características selecionadas das entidades do mundo real; 2

3. Estruturas de Dados A forma segundo a qual os bits são agrupados, interpretados e manipulados pelo computador normalmente não nos interessa quando a nossa preocupação maior é resolver um problema específico; Felizmente, as linguagens atuais oferecem um conjunto básico de tipos de dados primitivos (inteiros, reais, caractere, booleano etc.) que podemos usar nas soluções de problemas; Da mesma forma, temos mecanismos que permitem criar agrupamentos complexos de dados a partir desses tipos primitivos; 3

4. Estruturas de Dados Para representar o mundo computacionalmente é necessário modelar; É neste particular que o conceito de tipos abstratos de dados passa a ser muito importante para a computação; Um tipo abstrato de dados é formado por: Um conjunto de valores; Uma série de funções que podem ser aplicadas a estes valores. O modelo usado para representar a solução de uma classe de problemas podemos chamar de estrutura de dados ; 4

5. Estruturas de Dados O estudo das estruturas de dados envolve dois objetivos básicos: Teórico: Identificar e desenvolver modelos, determinando que classes de problemas podem resolver; Prático: Criar representações concretas dos objetivos e desenvolver sub-rotinas capazes de atuar como representações. 5

6. Listas Lineares Uma lista é uma coleção de elementos do mesmo tipo dispostos linearmente que podem ou não seguir uma determinada organização; Exemplo: [E 1 , E 2 , E 3 , ..., E n ], onde n ≥ 0 ; Uma lista de pagamentos pode ser constituída por: prestação do carro, cartão de crédito, conta de luz, condomínio, televisão a cabo e prestação do crediário; 6

7. Listas Lineares Para a representação de alguns modelos do mundo real é necessário limitar o funcionamento das listas lineares; É neste contexto que surgem as listas lineares restritas. As mais utilizadas são: Pilhas e Filas. 7

8. Pilhas Uma lista linear onde tanto a entrada quanto a saída precisa ser feita pela mesma extremidade é conhecida como pilha; Neste caso o último elemento que entrar é o primeiro a sair ( Last In First Out ); Existem duas funções que se aplicam a todas as pilhas: PUSH : insere o item no topo da pilha; POP : remove o item d o topo da pilha. 8

9. Pilhas (modelo conceitual) 9 Novos elementos são armazenados no topo da pilha. PILHA A

10. Pilhas (modelo conceitual) Push 10 Novos elementos são armazenados no topo da pilha. PILHA A

11. Pilhas (modelo conceitual) 11 Novos elementos são armazenados no topo da pilha. PILHA B A

12. Pilhas (modelo conceitual) Push 12 Novos elementos são armazenados no topo da pilha. PILHA A B

13. Pilhas (modelo conceitual) 13 Novos elementos são armazenados no topo da pilha. PILHA C A B

14. Pilhas (modelo conceitual) Push 14 Novos elementos são armazenados no topo da pilha. PILHA A B C

15. Pilhas (modelo conceitual) 15 Novos elementos são armazenados no topo da pilha. PILHA D A B C

16. Pilhas (modelo conceitual) Push 16 Novos elementos são armazenados no topo da pilha. PILHA A B C D

17. Pilhas (modelo conceitual) 17 A B C D Sequência armazenada em pilha. PILHA

18. Pilhas (modelo conceitual) Pop 18 A B C D O último elemento que entrou será o primeiro a sair ( LIFO ). PILHA

19. Pilhas (modelo conceitual) Pop 19 A B C O último elemento que entrou será o primeiro a sair ( LIFO ). PILHA

20. Pilhas (modelo conceitual) Pop 20 A B O último elemento que entrou será o primeiro a sair ( LIFO ). PILHA

21. Pilhas (modelo conceitual) Pop 21 A O último elemento que entrou será o primeiro a sair ( LIFO ). PILHA

22. Pilhas (representação gráfica) 22 D push (pilha, ‘D’); Topo → D p op(pilha); Topo → A p ush (pilha, ‘A’); Topo → V A p ush (pilha, ‘V’); Topo → V A pop(pilha); Topo → B A push (pilha, ‘B’); Topo → D A B V D V

23. Pilhas (representação gráfica) 23 G B A p ush (pilha, ‘G’); Topo → H G B A p ush (pilha, ‘H’); Topo → H G B A p op(pilha); Topo → G B A p op(pilha); Topo → B A p op(pilha); Topo → A p op(pilha); Topo → H G H G B A

24. Pilhas (implementação) Consideremos para a nossa implementação um grupo de operações: c reate → inicializa a pilha d estroy → esvazia a pilha isfull → verifica se está cheia isempty → verifica se está vazia p ush → insere um elemento p op → retira um elemento t op → mostra o elemento do topo 24

25. Pilhas (definição da estrutura) 25 type TPilha = record vet : array [ 1 .. 6 ] of char ; topo : integer ; end ; TPilha vet topo 1 2 3 4 5 6

26. Pilhas ( c reate , d estroy , isfull e isempty ) 26 procedure create ( var p : TPilha ); begin p . topo := ; end ; procedure destroy ( var p : TPilha ); begin p . topo := ; end ; function isfull ( var p : TPilha ): boolean ; begin if p . topo = 6 then isfull := true else isfull := false ; end ; function isempty ( var p : TPilha ): boolean ; begin if p . topo = then isempty := true else isempty := false ; end ;

27. Pilhas ( isfull e isempty ) 27 function isfull ( var p : TPilha ): boolean ; begin isfull := p . topo = 6 ; end ; function isempty ( var p : TPilha ): boolean ; begin isempty := p . topo = ; end ; SEGUNDA VERSÃO

28. function pop ( var p : TPilha ): char ; var aux : char ; begin if isempty ( p ) t hen begin writeln ( ' underflow ' ); halt ; end ; aux := p . vet [ p . topo ]; p . topo := p . topo - 1 ; pop := aux ; end ; Pilhas ( p ush e p op ) 28 procedure p ush ( var p : TPilha ; x : char ); begin if isfull ( p ) t hen begin writeln ( 'overflow' ); halt ; end ; p . topo := p . topo + 1 ; p . vet [ p . topo ] := x ; end ;

29. Pilhas ( top ) 29 f unction top ( var p : TPilha ): char ; begin if isempty ( p ) t hen begin w riteln ( ' underflow ' ); h alt ; end ; top := p . vet [ p . topo ]; end ;

30. Pilhas (exemplo de utilização) 30 procedure inverte ( var s : string ); var i, tam : integer ; p : TPilha ; begin create ( p ); i := 1 ; tam := length ( s ); while not isfull ( p ) and ( i <= tam ) do begin push ( p , s [ i ]); i := i + 1 ; end ; s := '' ; while not isempty ( p ) do s := s + pop ( p ); end ; Roma amoR a m o R

31. Pilhas (aplicações) Pilha de chamada de rotinas: Caso seja uma chamada, colocar o endereço da próxima instrução na pilha, executando a rotina chamada; Caso seja um “retorne”, retirar um endereço da pilha, passando a executá-lo. 31

32. Pilhas (aplicações) INSTRUÇÃO ESTADO DA PILHA e0 e1: A( ); e0, e2 e5: B( ); e0, e2, e6 e7: Retorne; e0, e2 e6: Retorne; e0 e2: C( ); e0, e3 e8: Retorne; e0 e3: B( ); e0, e4 e7: Retorne; e0 e4: Retorne; Rotina P e1: A( ); e2: C( ); e3: B( ); e4: Retorne ; Rotina A e5: B( ); e6: Retorne ; Rotina B e7 : Retorne ; Rotina C e8 : Retorne ; 32

33. Pilhas (infixa -> posfixa ) 33 Infixa   Posfixa  

34. Pilhas (infixa -> posfixa ) 34 Infixa:   Posfixa : ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

35. Pilhas (infixa -> posfixa ) 35 Infixa:   Posfixa : ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

36. Pilhas (infixa -> posfixa ) 36 Infixa:   Posfixa : ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

37. Pilhas (infixa -> posfixa ) 37 Infixa:   Posfixa : ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

38. Pilhas (infixa -> posfixa ) 38 Infixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string Posfixa:  

39. Pilhas (infixa -> posfixa ) 39   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

40. Pilhas (infixa -> posfixa ) 40   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

41. Pilhas (infixa -> posfixa ) 41 Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

42. Pilhas (infixa -> posfixa ) 42   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

43. Pilhas (infixa -> posfixa ) 43   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

44. Pilhas (infixa -> posfixa ) 44   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

45. Pilhas (infixa -> posfixa ) 45   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

46. Pilhas (infixa -> posfixa ) 46   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

47. Pilhas (infixa -> posfixa ) 47   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

48. Pilhas (infixa -> posfixa ) 48 Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

49. Pilhas (infixa -> posfixa ) 49   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

50. Pilhas (infixa -> posfixa ) 50   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

51. Pilhas (infixa -> posfixa ) 51   Infixa:   Posfixa:   ( : ignore 0…9 : anexe à string +, -, *, / : empilhe ) : desempilhe e anexe à string

52. Pilhas (infixa -> prefixa) 52 Infixa   Prefixa  

53. Pilhas (infixa -> prefixa) 53 Infixa:   Prefixa: ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

54. Pilhas (infixa -> prefixa) 54 Infixa:   Prefixa: ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

55. Pilhas (infixa -> prefixa) 55 Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

56. Pilhas (infixa -> prefixa) 56   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

57. Pilhas (infixa -> prefixa) 57   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

58. Pilhas (infixa -> prefixa) 58   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

59. Pilhas (infixa -> prefixa) 59   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

60. Pilhas (infixa -> prefixa) 60   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

61. Pilhas (infixa -> prefixa) 61   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

62. Pilhas (infixa -> prefixa) 62   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

63. Pilhas (infixa -> prefixa) 63   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

64. Pilhas (infixa -> prefixa) 64   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

65. Pilhas (infixa -> prefixa) 65   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

66. Pilhas (infixa -> prefixa) 66   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

67. Pilhas (infixa -> prefixa) 67 Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string  

68. Pilhas (infixa -> prefixa) 68   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

69. Pilhas (infixa -> prefixa) 69   Infixa :   Prefixa: +   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

70. Pilhas (infixa -> prefixa) 70   Infixa :   Prefixa: + /   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

71. Pilhas (infixa -> prefixa) 71   Infixa :   Prefixa:   ) : ignore 0…9 : anexe à string +, -, *, / : empilhe ( : desempilhe e anexe à string

72. Pilhas ( posfixa -> infixa) 72 Posfixa   Infixa  

73. Pilhas ( posfixa -> infixa) 73 Posfixa:   0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'   Infixa:

74. Pilhas ( posfixa -> infixa) 74   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

75. Pilhas ( posfixa -> infixa) 75   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

76. Pilhas ( posfixa -> infixa) 76   Posfixa:   0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

77. Pilhas ( posfixa -> infixa) 77   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

78. Pilhas ( posfixa -> infixa) 78   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

79. Pilhas ( posfixa -> infixa) 79   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

80. Pilhas ( posfixa -> infixa) 80   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

81. Pilhas ( posfixa -> infixa) 81   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

82. Pilhas ( posfixa -> infixa) 82   Posfixa:   Infixa: 0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

83. Pilhas ( posfixa -> infixa) 83 Posfixa:   Infixa:   0…9 : empilhe +, -, *, / : recebe desempilha; e mpilhe '(' + desempilha + + + ')'  

84. Pilhas (prefixa -> infixa) 84 Prefixa   Infixa  

85. Pilhas (prefixa -> infixa) 85 Prefixa:   0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'   Infixa:

86. Pilhas (prefixa -> infixa) 86   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

87. Pilhas (prefixa -> infixa) 87   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

88. Pilhas (prefixa -> infixa) 88   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

89. Pilhas (prefixa -> infixa) 89   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

90. Pilhas (prefixa -> infixa) 90   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

91. Pilhas (prefixa -> infixa) 91   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

92. Pilhas (prefixa -> infixa) 92   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

93. Pilhas (prefixa -> infixa) 93   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

94. Pilhas (prefixa -> infixa) 94   Prefixa:   Infixa: 0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

95. Pilhas (prefixa -> infixa) 95 Prefixa:   Infixa:   0…9 : empilhe +, -, *, / : empilhe '(' + desempilha + + desempilha + ')'  

96. 96 Avaliação de expressão POSFIXA  

97. Pilhas (avaliação posfixa ) 97 posfixa :   Resultado:   0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

98. Pilhas (avaliação posfixa ) 98 posfixa :   Resultado:   3 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

99. Pilhas (avaliação posfixa ) 99 posfixa :   Resultado:   1 3 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

100. Pilhas (avaliação posfixa ) 100 posfixa :   Resultado:   2 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

101. Pilhas (avaliação posfixa ) 101 posfixa :   Resultado:   2 2 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

102. Pilhas (avaliação posfixa ) 102 posfixa :   Resultado:   4 2 2 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

103. Pilhas (avaliação posfixa ) 103 posfixa :   Resultado:   8 2 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

104. Pilhas (avaliação posfixa ) 104 posfixa :   Resultado:   10 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

105. Pilhas (avaliação posfixa ) 105 posfixa :   Resultado:   5 10 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

106. Pilhas (avaliação posfixa ) 106 posfixa :   Resultado:   2 0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

107. Pilhas (avaliação posfixa ) 107 posfixa :   Resultado:   0…9 : empilhe +, -, *, / : recebe desempilha; empilhe( desempilha )  

108. 108 Avaliação de expressão PREFIXA  

109. Pilhas (avaliação prefixa) 109 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)  

110. Pilhas (avaliação prefixa) 110 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   5

111. Pilhas (avaliação prefixa) 111 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   4 5

112. Pilhas (avaliação prefixa) 112 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   2 4 5

113. Pilhas (avaliação prefixa) 113 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   8 5

114. Pilhas (avaliação prefixa) 114 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   1 8 5

115. Pilhas (avaliação prefixa) 115 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   3 1 8 5

116. Pilhas (avaliação prefixa) 116 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   2 8 5

117. Pilhas (avaliação prefixa) 117 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   10 5

118. Pilhas (avaliação prefixa) 118 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)   2

119. Pilhas (avaliação prefixa) 119 prefixa :   Resultado:   0…9 : empilhe +, -, *, / : empilhe(desempilha desempilha)