Pila

Ricardo Ferrís / Jesús Albert

Algoritmos y Estructuras de Datos I

11. PILAS
11.0 INTRODUCCIÓN .......................................................................................................................................................... 25 11.1 FUNDAMENTOS.......................................................................................................................................................... 25 11.2. REPRESENTACIÓN DE LAS PILAS EN C++ .................................................................................................................. 26 Implementación mediante estructuras estáticas........................................................................................................... 31 Implementación mediantecursores.............................................................................................................................. 35 Implementación mediante estructuras dinámicas ........................................................................................................ 35

11.0 Introducción
En este tema y en el siguiente veremos las estructuras de datos lineales pilas y colas. Las pilas y las colasson dos de las estructuras de datos más utilizadas. Se trata de dos casos particulares de las estructuras lineales generales (secuencias o listas) que, debido a su amplio ámbito de aplicación, conviene ser estudiadas de manera independiente. En este tema veremos concretamente las pilas, su utilización y su implementación más habitual en C++.

11.1 Fundamentos
La pila es una lista de elementoscaracterizada porque las operaciones de inserción y eliminación de elementos se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente cima (top en la nomenclatura inglesa). Dada una pila P, formada por los elementos a, b, c, ..., k (P=(a,b,c,...,k)), se dice que a, que es el elemento más inaccesible de la pila, está en el fondo dela pila (bottom) y que k, por el contrario, el más accesible, está en la cima (top). Las restricciones definidas para la pila implican que si una serie de elementos A, B, C, D, E, F se añaden, en este orden, a una pila entonces el primer elemento que se elimine (borre) de la estructura deberá ser E. Por tanto, resulta que el último elemento que se inserta en una pila es el primero que se borra.Por esa razón, se dice que una pila es una lista o estructura lineal de tipo LIFO (Last In First Out, el último que entra es el primero que sale). Estructura Pila A B C D E F ... ← → Borrado Inserción

Un ejemplo típico de pila lo constituye un montón de platos: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se coge unplato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. O, si somos más estrictos, otro ejemplo sería una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o cojemos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos elnúmero de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja. Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información Tema 11. Pilas 25

RicardoFerrís / Jesús Albert

Algoritmos y Estructuras de Datos I

asociada con ese procedimiento (parámetros, variables, constantes, direción de retorno, etc...) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en...