isco

Estructuras y apuntadores
Representaciones estáticas y dinámicas: Listas, pilas y colas, árboles,
aplicaciones
Dr. Jesús Carrillo Ahumada
Estructura de datos

Introducción
Los arreglos son estructuras lineales es decir cada componente tiene un único sucesor y
un único predecesor con excepción del primero y del último respectivamente. Por otra
parte, al analizar las operaciones deinserción y eliminación se observa que los elementos
se podrían insertar o eliminar en cualquier posición del arreglo. Cabe señalar que existen
problemas que por su naturaleza requieren que los elementos se agreguen o se quiten
solo por un extremo. Para lo cual se utilizan las pilas y colas que son estructuras de datos
lineales con restricciones en cuanto a la posición en la cual se pueden llevar acabo las
operaciones de inserción y eliminación de componentes.

1 Pilas
Una pila representa una estructura lineal de datos en la que se puede agregar o quitar
elementos únicamente por uno de los dos extremos. En consecuencia, lo elementos de
una pila se eliminan en orden inverso al que se insertaron; es decir el último elementos
que se mete en la pila es el primero que se saca. Debido a estacaracterísticas, se le
conoce como estructura LIFO (last-input, first-output; el último en entrar es el primero en
salir).

Ejemplos que utilizan en concepto de pilas son: pila de platos o pila de libros.

Figura 1. Ejemplos prácticos de pilas

En la Fig. 1. se muestra una pila de platos. Es de suponer que si el cocinero necesita un
plato limpio, tomará el que está encima de todos, quees el último que se coloco en la pila.

Las pilas son estructuras de datos lineales como los arreglos ya que los componentes
ocupan lugares sucesivos en la estructura y cada uno de ellos tiene un único sucesor y un
único predecesor con excepción del último y del primero respectivamente.

Una pila se define formalmente como:
Una colección de datos a los cuales se puede acceder mediante unextremo que se conoce
generalmente como tope.

1.1 Representación de pilas
Las pilas no son estructuras fundamentales de datos; es decir no están definidas como
tales en los lenguajes de programación. Para su representación requieren el uso de otras
estructuras como:




Arreglos
Listas

Es importante definir el tamaño máximo de la pila, así como una variable auxiliar a la que
sedenomina TOPE. Esta variable se utiliza para indicar el último elemento que se inserto
en la pila. En la Figura 2 se presentan dos alternativas de representación de una pila,
utilizando arreglos.

Figura 2. a) pila llena, b) pila con algunos elementos, c) pila vacía.

Al utilizar arreglos para implementar pilas se tiene la limitación de que se debe reservar
espacio de memoria conanticipación, característica propia de los arreglos. Una vez dado
un máximo de capacidad a la pila no es posible insertar un número de elementos mayor al
máximo establecido. Si la pila estuviera llena y se intentara insertar un elemento nuevo, se
producirá un error conocido como desboradamiento "overflow".

Por ejemplo, si en la pila que se presenta en la Fig 2a donde TOPE=MAX, se quisiera
insertar unnuevo elemento, se producirá un error de este tipo. La pila está llena y el
espacio de memoria reservado es fijo, no se puede expandir ni contraer.
Una posible solución a este tipo de inconveniente consiste en definir pilas de gran
tamaño, pero esto último resultaría ineficiente. No siempre es viable saber con exactitud
cual es el número de elemento a tratar; por lo tanto, siempre existe laposibilidad de
cometer un error de desbordamiento.
Existe otra alternativa de solución a este problema. Consiste en usar espacios compartidos
de memoria para la implementación de pilas. Supongamos que se necesitan dos pilas,
cada una de ellas con un tamaño máximo de N elementos. Se definirá entonces un solo
arreglo unidimensional de 2*N elementos, en lugar de dos arreglos de N elementos...