Pilas fil

AS“ESTRUCTURA DE DATOS . Referencia práctica con orientación a objetos”. R. Martinez y E.Quiroga - 2002

Cátedra: Estructuras de Datos Libro: “ESTRUCTURA DE D ATOS. Referencia práctica con orientación a objetos”. Román Martínez, Elda Quiroga Inst. Tecnológico y de Estudios Superiores de Monterrey. Campus Monterrey. Ed. Thomsan Learning. - 2002 - ISBN 970-686-044-4 Bibliografía de la clases 7 y8 – Unidad 2: Estructuras de Datos Lineales

Capitulo 6 – Pilas y Filas (Colas)
OBJETIVOS
• • • • • Explicar en qué consisten las estructuras de datos pila y fila (Cola), y cuáles son sus aplicaciones principales. Diseñar los TDA pila y fila. Describir las diferentes opciones para representar los TDA pila y fila, analizando ventajas y desventajas. Conocer la forma en que se maneja un arreglocircular y cómo se aplica en la representación de una fila. Integrar los conceptos de abstracción de datos, programación orientada a objetos y listas encadenadas en memoria dinámica, en el contexto de los TDA pila y fila.

¿Qué es una pila?
Una pila es un conjunto ordenado de objetos los cuajes pueden obtenerse (uno a la vez) siguiendo un orden especial; el último que entró en la pila es elprimero en salir (figura 6.1). Así, en una cafetería de autoservicio se tienen apiladas las charolas que emplearán los clientes y cada uno toma la que se encuentra hasta arriba (en el tope) y la última charola que se toma es precisamente la primera que se colocó en la pila. De la misma manera, se puede tener una pila de libros, una pila de ladrillos, una bolsa de pan de caja, etcétera.

Figura 6.1¿Qué es la estructura de datos pila?
Esta última idea de obtener el elemento del fondo de la pila, a través del acceso de los elementos que están por encima de él, sirve para hacer la definición abstracta de la estructura de datos pila. Esto es una estructura de datos lineal de objetos ordenados de forma tal que éstos se obtienen por un sólo lado de la estructura siguiendo un sistema UEPS(Último en Entrar, Primero en Salir) o en inglés LIFO (Last lnput, First
Output).

La pila es una estructura finita. Los elementos pueden identificarse por la posición en que están; el último elemento de la pila se encuentra en el tope, enseguida está el otro, y así sucesivamente. Para llegar al objeto del fondo, es necesario obtener primero los que le anteceden. Por consiguiente, siempre se deberátener en cuenta donde se encuentra el último elemento añadido, es decir, el tope de la pila.

Capítulo 6 – Pilas y Filas (Colas)

1

“ESTRUCTURA DE DATOS . Referencia práctica con orientación a objetos”. R. Martinez y E.Quiroga - 2002

¿Qué es una fila (cola)?
Diariamente vivimos las filas. En los supermercados, en los teatros, en los bancos, hacemos filas con otras personas que esperanser atendidas (figura 6.2). Existen modelos de líneas de espera que estudian el comportamiento de las filas tomando en cuenta factores como llegadas de clientes, cantidad de servidores, tiempo de llegada entre clientes, tiempo necesario para servicio, etc. Sin embargo, aquí se hará una breve explicación del concepto de fila o cola (queue en inglés) desde el punto de vista de las estructuras dedatos.

Figura 6.2

¿Qué es la estructura de datos fila?
Aunque el estudio de la fila se hará desde el punto de vista de las estructuras de datos, sigue manteniéndose el concepto de atender al primero en la fila. Con base en esto, se puede definir una fila como una estructura de datos cuyos elementos se manejan bajo la filosofía (PEPS) primero en entrar, primero en salir o en inglés FIFO (Firstlnput, Fi rst Ouput ). La fila es una estructura finita y lineal donde los elementos pueden ser de cualquier tipo que se requiera. Su dominio lo forman aquellos elementos que puedan llegar a almacenarse en la estructura, y se obtienen por dos partes de la estructura; una llamada frente que señala dónde se encuentra el siguiente elemento por atender en la fila, y otra llamada final, que significa...