PDF de programación - Tema III. Estructuras de datos Compuestas - Unidad 2: Estructuras de Datos

Unidad 2: Estructuras de Datos

Tema III. Estructuras de datos Compuestas.

Pilas y Colas

Programación I (Plan 1999)

Algoritmos y Estructuras de Datos II (Plan 2009)

Mgter. Oscar Adolfo Vallejos
FaCENA - UNNE

Pilas y Colas

Las pilas y colas son estructuras de datos que se
utilizan generalmente para simplificar ciertas
operaciones de programación.

Estas estructuras pueden implementarse

mediante arrays o mediante listas enlazadas
(punteros).

Pilas y Colas

Pilas
Las pilas son estructuras de datos que tienes dos operaciones básicas:

push (para insertar un elemento)
pop (para extraer un elemento).

Su característica fundamental es que al extraer se obtiene siempre el
último elemento que acaba de insertarse. Por esta razón también
se conocen como estructuras de datos LIFO (del inglés Last In First
Out).

Una posible implementación mediante listas enlazadas sería

insertando y extrayendo siempre por el principio de la lista.

Pilas y Colas

Las pilas se utilizan en muchas aplicaciones que

utilizamos con frecuencia. Por ejemplo, la gestión de
ventanas en Windows (cuando cerramos una ventana
siempre recuperamos la que teníamos detrás).

Otro ejemplo es la evaluación general de cualquier

expresión matemática para evitar tener que calcular el
número de variables temporales que hacen falta.

Operaciones básicas sobre las pilas

• Creación de una pila

• Consulta del contenido del primer elemento de la

pila

• Inserción de un nuevo elemento sobre la pila

(push)

• Eliminación del elemento superior de la pila

(pop).

Pilas y Colas

Colas

Las colas también son llamadas FIFO (First In First Out), que quiere

decir “el primero que entra es el primero que sale”.

Colas simples

Se inserta por un sitio y se saca por otro, en el caso de la cola simple se
inserta por el final y se saca por el principio. Para gestionar este tipo
de cola hay que recordar siempre cual es el siguiente elemento que
se va a leer y cual es el último elemento que se ha introducido.

Colas

Operaciones básicas

• Creación de una cola vacía
• Consulta del primer elemento
• Añadir un elemento
• Suprimir el primer elemento