Licenciatura

Instituto Tecnológico de Querétaro

Guillermo Álvarez Jiménez
Felipe Gómez Rangel
Gustavo Juárez vega
Jorge de Jesús Flores Muñoz
Jesús Zubieta Segundo
Unidad 3
Pilas

Estructura de Datos

Grupo: 6 M

Ingeniería en Sistemas Computacionales


Contenido
Introducción 3
Objetivo 4
Operaciones básicas de las pilas 5
Insertar 5
Borrar 6
Representacion enmemoria 7
Notación Prefija, Infija y Postfija 9
• Notación Prefija o Polaca 9
• Notación Postfija o Polaca Inversa 9
USO DE LAS PILAS PARA SIMULAR RECURSIVIDAD 9
Conclusión 11
Referencias 12

Introducción

En este documento hablaremos acerca de la estructura de dato llamada pila veremos las operaciones básicas que se pueden realizar en esta estructura de dato asi como también larepresentación de las pilas

Objetivo

Operaciones básicas de las pilas
Vamos a estudiar las principales operaciones a realizar sobre una pila, insertar y borrar.
Insertar
En primer lugar hay que decir que esta operación es muy comúnmente denominada push.
La inserción en una pila se realiza en su cima, considerando la cima como el último elemento insertado. Esta es una de las particularidadesde las pilas, mientras el resto de estructuras de datos lineales se representan gráficamente en horizontal, las pilas se representan verticalmente. Por esta razón es por lo que se habla de cima de la pila y no de cola de la cima. Aunque en el fondo sea lo mismo, el último elemento de la estructura de datos.
Las operaciones a realizar para realizar la inserción en la pila son muy simples, hacer queel nuevo nodo apunte a la cima anterior, y definir el nuevo nodo como cima de la pila.
Vamos a ver un ejemplo de una inserción:

Al insertar sobre esta pila el elemento 0, la pila resultante sería:

Borrar
Esta operación es normalmente conocida como pop.
Cuando se elimina un elemento de la pila, el elemento que se borra es el elemento situado en la cima de la pila, el que menos tiempolleva en la estructura.
Las operaciones a realizar son muy simples, avanzar el puntero que apunta a la cima y extraer la cima anterior.
Si aplicamos la operación pop a la pila de 4 elementos representada arriba el resultado sería:

Representacion en memoria

Los lenguajes de programación de alto nivel no suelen disponer de un tipo de datos pila. Aunque por el contrario, en lenguajes de bajonivel (ensamblador) es posible manipular directamente alguna estructura pila propia del sistema. Por lo tanto, en general, es necesario representar la estructura pila a partir de otros tipos de datos existentes en el lenguaje.
La forma más simple, y habitual, de representar una pila es mediante un vector unidimensional. Este tipo de datos permite definir una secuencia de elementos (de cualquiertipo) y posee un eficiente mecanismo de acceso a la información contenida en él.
Al definir un array hay que determinar el número de índices válidos y, por lo tanto, el número de componentes definidos. Entonces, la estructura pila representada por un array tendrá limitado el número de posibles elementos.
Se puede definir una pila como una variable:
Pila: array [1..n] de T

donde T es el tipoque representa la información contenida en la pila (enteros, registros,etc.)
El primer elemento de la pila se almacenará en Pila[1], será el fondo de la pila, el segundo elemento en Pila[2] y así sucesivamente. En general, el elemento i-úsimo estará almacenado en Pila.
Como todas las operaciones se realizan sobre la cima de la pila, es necesario tener correctamente localizada en todo instanteesta posición. Es necesaria una variable, cima, que apunte al último elemento (ocupado) de la pila.
Con estas consideraciones prácticas, se puede pasar a definir las operaciones que definen la pila.

Crear pila:
Es necesario definir el array que permitirá almacenar la información y la variable que indica la posición de la cima. Además tendremos que inicializar cima al valor 0, indicando...