PILAS Y COLAS

Estructuras de Datos
Avanzadas
Contenido del Tema

T
E
M
A

5.1. Introducción
5.2. Pilas
5.3. Colas
5.4. Listas
5.5. Arboles Binarios
Arboles Binarios de Búsqueda

5
Programación Modular

Introducción
Objetivos
• Especificación e Implementación de nuevas
estructuras de datos
Técnica: Abstracción de
Datos
• Tipos de Estructuras de Datos:
1) Datos organizados por PosiciónPilas , Colas
y Listas
2) Datos organizados por Valor
Arboles Binarios
Programación Modular

2

1

Introducción
• Estudio de las Estructuras de Datos:
Definición de la Estructura de Datos e
identificación de su Conjunto de
Operaciones
Presentación de Aplicaciones
Desarrollo de diversas Implementaciones

Programación Modular

3

Pilas
Definición
• Pila: Grupo Ordenado, (deacuerdo al tiempo que llevan
en la pila) de Elementos
Homogéneos (todos del
mismo tipo).
• Acceso a la Pila: añadir y
eliminar elementos, SÓLO a
través de la CABEZA de la
Pila
• Estructura LIFO (Last Input
First Output)

Añadir

Eliminar

Cabeza

Pila

Programación Modular

4

2

Pilas. Operaciones

INTERFAZ CLASE CPila
TIPOS
TipoElemento ... // cualquier tipo dedatos
METODOS
// Añade un elemento por la cabeza de la pila
Apilar( E TipoElemento elem)
// Saca un elemento por la cabeza de la Pila
Desapilar()
// Devuelve el elemento de la cabeza de la Pila
TipoElemento Cima()
...

Programación Modular

5

Pilas. Operaciones 2
...
// Crea una pila vacía
Crear()
//Operación lógica que nos dice si una pila está vacía o no
B EstáVacía ()//Operación lógica que nos dice si una pila está llena o no.
//Necesaria en determinadas implementaciones
B EstáLlena()
// Destruye una pila previamente creada
Destruir()
FIN CPila

Programación Modular

6

3

Pilas. Aplicaciones
Aplicaciones
• Ejemplo1: Leer una secuencia de caracteres desde teclado
e imprimirla al revés
• Ejemplo2: Verificar si una cadena de caracteres estábalanceada en paréntesis o no
abc(defg(ijk))(l(mn)op)qr
SI
abc(def))ghij(kl)m
NO
• Ejemplo3: Reconocimiento del Lenguaje,
L={W$W´ / W es una cadena de caracteres y W´es su
inversa} (Suponemos que $ no está ni en W ni en W´)
Programación Modular

7

Pilas. Ejemplo1
Algoritmo Inverso
Tipos
TipoElemento = C
Variables
TipoElemento c
CPila pila // Se llama automáticamente al constructorInicio
Leer(c)
MIENTRAS c != CHR(13)HACER
pila.Apilar(c)
Leer(c)
FINMIENTRAS
MIENTRAS NO (pila.EstáVacía()) HACER
c = pila.Cima()
pila.Desapilar()
Escribir(c)
FINMIENTRAS
pila.Destruir()
Fin

Programación Modular

8

4

Pilas. Ejemplo2
Algoritmo Balanceo
Tipos

SI c = = ‘)’ ENTONCES
SI (!pila.EstáVacía()) ENTONCES

TipoElemento = C
Variables

pila.Desapilar ()
SINOTipoElemento c
CPila pila
B bien

bien = FALSO
FINSI
FINSI

Inicio
bien = VERDADERO
Leer(c)
MIENTRAS
HACER

(bien

FINSI
Leer(c)
Y

(c!=CHR(13)))

SI c== ‘(’ ENTONCES
pila.Apilar(c)
SINO

FINMIENTRAS
SI bien Y pila .EstáVacía() ENTONCES
Escribir(“cadena balanceada “)
SINO
Escribir(“cadena no balanceada”)
FINSI
pila.Destruir()
Fin

Programación Modular

9Pilas. Ejemplo3
Algoritmo Lenguaje_L
Tipos
TipoElemento = $
Variables
TipoElemento c1, c2
CPila pila
B bien
Inicio
Leer(c1)
MIENTRAS (c1 != ‘$’) HACER
pila.Apilar(c1)
Leer(c1)
FINMIENTRAS
Leer(c1)
bien = VERDADERO
MIENTRAS (bien AND
(c1 CHR(13))) HACER

SI pila .EstáVacía()ENTONCES
bien= FALSO
SINO
c2 = pila .Cima()
pila.Desapilar ()
SI (c1 != c2) ENTONCES
bien = FALSE
SINOLeer(c1)
FINSI
FINSI
FINMIENTRAS
SI (bien AND pila.EstáVacía())ENTONCES
Escribir (“ Si pertenece”)
SINO
Escribir (“No pertenece”)
FINSI
pila Destruir()
Fin

Programación Modular

10

5

Pilas. Aplicaciones
• Aplicaciones complejas que se pueden solucionar con
pilas:
Expresiones Algebraicas
Operadores: +, -, *, /
Operandos: Letras mayúsculas
• Notación Infija:
• El...