La Pila (stack). 5x47v

Estructuras de Datos

21

Capítulo 2. LA PILA (STACK). 2.1 Definición y ejemplos. Una pila es un conjunto ordenado de elementos en el cual se pueden agregar y eliminar elementos de un extremo, el cual es llamado el tope de la pila. La pila es un objeto dinámico en constante cambio. La definición de pila especifica que un solo extremo de la pila se designa como tope.

Ricardo Ruiz Rodríguez

Estructuras de Datos

22

Pueden colocarse nuevos elementos en el tope de la pila o se pueden quitar elementos de él. La característica más importante de la pila es que el último elemento insertado en ella es el primero en suprimirse. Por esta razón, una pila se denomina como una estructura LIFO (Last In First Out) en la cual, el último elemento insertado, será el primero en ser eliminado.

Ricardo Ruiz Rodríguez

23

Estructuras de Datos

Tabla 1. Crecimiento y decrecimiento de una Pila.

→ →

→

F

F

E

E

E

E

D

D

D

D

C

C

C

B

B

A

A

→ →

→

G →

F

I

H

H

E

E

E

D

D

D

D

C

C

C

C

C

B

B

B

B

B

B

A

A

A

A

A

A

Ricardo Ruiz Rodríguez

→

Estructuras de Datos

24

2.2 Funciones primitivas. Las funciones básicas definidas sobre una pila son push y pop. La función push inserta un nuevo elemento en el tope de la pila. La función pop elimina el elemento indicado por el tope de la pila. Existen otras funciones útiles al usar pilas, por ejemplo, antes de aplicar la operación pop a una pila, se debe verificar que la pila no esté vacía. Así, la función isEmpty determina si una pila está o no vacía.

Ricardo Ruiz Rodríguez

Estructuras de Datos

25

Otra operación que puede ejecutarse sobre una pila es determinar cuál es el elemento que se encuentra en el tope de la pila pero sin eliminarlo. Esta función puede llamarse stacktop. 2.3 Representación de pilas en C. Hay varias formas de representar una pila en C y cada una de ellas es sólo una implementación del concepto introducido en la sección anterior. Aunque un arreglo no es una pila, bien puede ser usado para representar una. (Ejemplo del arreglo implementando una pila).

Ricardo Ruiz Rodríguez

Estructuras de Datos

26

Una pila es fundamentalmente un objeto dinámico cuyo tamaño se modifica en forma continua conforme se agregan y remueven elementos. (Ejemplo de una pila dinámica). Un programador siempre debe preocuparse por la legibilidad del código que produce. 2.4 Ejemplos clásicos del uso de pilas. Esta sección revisa dos ejemplos clásicos del uso de pilas, no son las únicas aplicaciones que se tienen de este tipo de estructura de datos, pero sí son de los más representativos.

Ricardo Ruiz Rodríguez

27

Estructuras de Datos

2.4.1 Análisis básico de expresiones. Considérese la siguiente expresión matemática:   x + y  x ∗  j − 3   7 −  4 − 5   

   + y     2   

Cuya representación “lineal” es: • 7 – ((x * ((x + y) / (j - 3)) + y) / (4 – 5/2)). ¿Cómo saber si la expresión está correctamente balanceada en cuanto a paréntesis se refiere?

Ricardo Ruiz Rodríguez

Estructuras de Datos

28

Considérese ahora la siguiente expresión matemática:

{x + ( y − [a + b]) ∗ c − [(d + e)]} (h − ( j − (k − [l − n]))) Cuya representación “lineal” es: • {x + (y – [a + b]) * c – [(d + e)]} / (h – (j – (k – [l - n]))). ¿Cómo saber si la expresión está correctamente balanceada en cuanto a símbolos de agrupación se refiere? ¿Cómo saber que un símbolo de agrupación está cerrando a su correspondiente símbolo de apertura? Considere el siguiente algoritmo: Ricardo Ruiz Rodríguez

Estructuras de Datos

valid = true; s = the empty stack; while(not end of string){ read the next symbol of the string; if(symbol == ‘(’ || symbol == ‘[’ || symbol == ‘{’) push(s, symbol); else if(symbol == ‘)’ || symbol == ‘]’ || symbol == ‘}’){ if(isEmpty(s)) valid = false; else{ i = pop(s); if(i is not equivalent to symbol) valid = false; } }

Ricardo Ruiz Rodríguez

29

Estructuras de Datos

30

} /* while’s */ if(!isEmtpy(s)) valid = false; if(valid) printf(“The string is valid\n”); else printf(“The string is invalid\n”); 2.4.2 Notación interfija, postfija y prefija. Considere la suma de dos números A y B. Aplicar el operador “+” a los operandos A y B, y escribir la suma como A + B tiene el nombre de representación interfija.

Ricardo Ruiz Rodríguez

Estructuras de Datos

31

Hay otras dos notaciones alternas para expresar la suma de A y B usando los mismos símbolos A, B y +: • + A B representación prefija. • A B + representación postfija. Los prefijos “pre”, “pos” e “inter” hacen referencia a la posición relativa del operador en relación a los operandos. Una función en C para retornar la suma de dos argumentos invocada mediante add(s, b) utiliza notación prefija, ya que el operador add precede a los operandos. Considere la siguiente expresión: Ricardo Ruiz Rodríguez

Estructuras de Datos

32

• A + B * C indica implícitamente A + (B * C). Suponga que se desea convertir la expresión anterior a su representación en postfija. Entonces, aplicando las reglas de precedencia, primero se convierte la parte de la expresión que se evalúa primero: • A + (B * C) forma interfija. • A + (BC *) se convierte la multiplicación. • A (BC *) + convierte la suma. • A B C * + representación postfija.

Ricardo Ruiz Rodríguez

Estructuras de Datos

33

Las únicas reglas que deben recordarse durante el proceso de conversión son las siguientes: 1.Las operaciones con mayor precedencia se convierten primero. 2.Después de que una parte de la expresión se ha convertido a postfija, se considerará como un operando único. Ejemplo: 1.(A + B) * C forma interfija. 2.(A B +) * C se convierte la adición. 3.(A B +) C * convierte la multiplicación. Ricardo Ruiz Rodríguez

Estructuras de Datos

34

4.A B + C * representación postfija. Ejercicio: Convertir las siguientes expresiones en su representación postfija: 1.

A+B

2.

A+B-C

3.

(A+B) * (C-D)

4.

A$B*C–D+E/F/(G+H)

5.

((A+B)*C–(D-E))$(F+G)

6.

A–B/(C*D$E)

Ricardo Ruiz Rodríguez

35

Estructuras de Datos

El signo de $ en las expresiones anteriores, representa el símbolo de exponenciación y es el de más alta precedencia. Las reglas para convertir una expresión de interfija a prefija son idénticas. El único cambio es que el operador se coloca antes de los operandos en lugar de después de ellos. Ejercicio:

Convierta

las

expresiones

anteriores

a

su

representación prefija. En base a los ejercicios anteriores, debe observarse que la representación prefija no siempre es una imagen reflejo de la representación postfija. Ricardo Ruiz Rodríguez

Estructuras de Datos

36

El orden de los operadores en las expresiones postfijas determina el orden real de las operaciones al evaluar la expresión, haciendo innecesario el uso de paréntesis. Ejercicio: Crear un algoritmo, así como su implementación, para convertir una expresión interfija en: 1.Postfija. 2.Prefija. Con valores concretos en las expresiones postfijas. ¿Cómo evaluar una expresión postfija? Considere el siguiente algoritmo: Ricardo Ruiz Rodríguez

Estructuras de Datos

Algoritmo para evaluar una expresión postfija: opndstack = the empty satck; while(not end of input){ symbol = next input character; if(symbol is an operand) push(opndstack, symbol); else{ opnd2 = pop(opndstack); opnd1 = pop(opndstack); value = opnd1 symbol opnd2; push(opndstack, value); } } return pop(opndstack);

Ricardo Ruiz Rodríguez

37

38

Estructuras de Datos

Solución a los ejercicios de conversión: Prefija:

Postfija:

1. + A B

AB+

2. - + A B C

AB+C-

3. * + A B - C D

AB+CD-*

4. + - * $ A B C D / / E F + G H

AB$C*D-EF/GH+/+

5. $ - * + A B C - D E + F G

AB+C*DE--FG+$

6. - A / B * C $ D E

ABCDE$*/-

Ricardo Ruiz Rodríguez