ESTRUCTURA DE DATOS

U nidad 9: D atos Com plejos: Pilas, Colas, Listas, G rafos y Á rboles

UNIDAD 9. DATOS COMPLEJOS
PILAS
Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por
uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en
orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el
primero ensalir de ella.

En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena,
una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc.

Debido al orden en que se insertan y eliminan los elementos en una pila, también se le
conoce como estructura LIFO (Last In, First Out: último en entrar, primero en salir).

Su utilización principal espara el software del sistema, compiladores e intérpretes.

Representación en Memoria
Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales
en los lenguajes de programación. Las pilas pueden representarse mediante el uso de:
•

Arreglos.

•

Listas enlazadas.

Nosotros ahora usaremos los arreglos. Por lo tanto debemos definir el tamaño máximo dela
pila, además de un apuntador al último elemento insertado en la pila el cual denominaremos
SP. La representación gráfica de una pila es la siguiente:

Ing. N ahiby Castillo

1

U nidad 9: D atos Com plejos: Pilas, Colas, Listas, G rafos y Á rboles

COLAS
Son listas lineales de información a las cuales de accede de un modo determinado siendo el
de tipo FIFO (First In, First Out)(Primero en Entrar, Primero en Salir), lo que quiere decir que
el primer dato en entrar es también el primer dato en salir, en las colas no se permite el
acceso aleatorio a ningún elemento concreto. Las recuperaciones de operaciones son
destructivas (elimina el elemento) de la cola, si no es almacenado en otro lugar se destruye.

Su utilización principal en las simulaciones, planificación desucesos, y los procesos de
entrada y salida con buffer.

Existen muchísimos ejemplos de colas en la vida real, como por ejemplo: personas
esperando en un teléfono público, niños esperando para subir a un juego mecánico,
estudiantes esperando para subir a un camión escolar, etc.

2.2 Representación en Memoria
Podemos representar a las colas de dos formas:
•

Como arreglos

•

Como listasordenadas

En lo sucesivo, al apuntador del primer elemento lo llamaremos F, al último elemento A y
MAXIMO para definir el número máximo de elementos en la cola.

2.3 Cola Lineal
La cola lineal es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica
FIFO (primero en entrar primero en salir). Las colas lineales se representan gráficamente de
la siguiente manera:Las condiciones a considerar en el tratamiento de colas lineales son las siguientes:
•

Overflow (cola llena), cuando se realice una inserción.

•

Underflow(cola vacía), cuando se requiera de una extracción en la cola.

•

Vacío

Ing. N ahiby Castillo

2

U nidad 9: D atos Com plejos: Pilas, Colas, Listas, G rafos y Á rboles

LISTAS
Son colecciones de elementos, donde cada unode ellos, además de almacenar información,
almacena la dirección del siguiente elemento. Una lista es una estructura lineal de datos. Es
decir, cada uno de sus componentes y un predecesor únicos, con excepción del último y del
primero.

Las listas pueden implementarse mediante arreglos, resultando así una estructura estática.
También puede ser una memoria dinámica (La cantidad de memoriaocupada puede
modificarse durante la ejecución del programa).

Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada
uno contiene datos y un enlace o liga.

Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo).
Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este
existe.

Un apuntador...