ING° PEDRO BELTRÁN CANESSA Estructuras de Datos 1
Las FILAS
Estructuras de Datos 2
LA FILA (Conceptos ....)
Es un contenedor que utiliza el protocolo
FIFO (First In, First Out) o bien, PEPS (Primeras Entradas, Primeras Salidas)
Entrada Salida
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 3
Tiene dos puntos de acceso, la cabeza (inicio) y el final (fin).
Entre sus operaciones se encuentran las de agregar un elemento a la fila (enqueue) y la de quitar (eliminar) un elemento de la fila (dequeue).
Cuando se agrega un elemento, se coloca al final de la cola, cuando se quita, se elimina del inicio de la misma.
Es un error tratar de quitar un elemento de una cola vacía.
LA FILA (Conceptos)
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 4
Fila con estructura estática Es una fila implementada como un arreglo
11 22 33 44
inicio final
max 0 1 2 3 4
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 5
Filas: Casos posibles:
11 22 33 44 55 66 77 88 99 00
11 22 33 44 55
inicio final
inicio final
llena
con algunos elementos
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 6
Filas: Casos posibles:
final inicio
Fila vacía
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 7
Filas: Operaciones: CREAR
Agrega un elemento a la fila
Entrada: número de elementos del arreglo
Salida: una fila vacía (de tamaño 0).
Int [] Crearfila (max){
Int [] f;
f = new int [max];
Return f;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 8
Filas: Operaciones: VACÍA
Sirve para determinar si una fila está vacía o no.
Entrada: fila
Salida: un boolean = a true si es vacía.
Boolean vacia (fin){
vacia = fin << 0;
Return vacia;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 9
Filas: Operaciones: LLENA
Determina si la fila está llena.
Entrada: fila, fin
Salida: true si está llena.
Boolean llena (fila, fin){
llena = fin == fila.length -1;
Return llena;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 10
Filas: Operaciones: AGREGAR
Agrega un elemento al final de la fila
Precondición: fila no llena
Entrada: fila, fin, dato
Salida: fila modificada
Void Agregafila (fila, fin, dato){
si no llena
{ fin fin + 1;
Fila [fin] dato}
si no escribir “ lista llena ”
} ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 11
Filas: Operaciones: QUITAR Quitar y devolver el primer elemento de la fila
Precondición: fila no vacía
Entrada: fila, fin
Salida: fila modificada, dato
Int quitafila (fila, fin){
Si no vacía
{ dato = fila [inicio];
rotarfila (fila, fin);
fin --;
return dato;}
si no escribir ( „Fila Vacía‟ )
} ING° PEDRO
BELTRÁN CANESSA
Estructuras de Datos 12
Filas: Operaciones: Rotarfila
Desplaza todos los elementos de un fila hacia la izquierda.
Entrada: fila, fin
Salida: fila modificada
Int rotarfila (fila, fin){
for(int i=0; i<fin ; i++)
fila [i] = fila [i+1];
return fin;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 13
Las Pilas
Estructuras de Datos 2005
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 14
LA pila (Conceptos ....)
Es un contenedor que utiliza el protocolo
LIFO (Last In, First Out) o bien, UEPS (Ultima Entrada, Primera Salida)
Entrada
Salida
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 15
Tiene un punto de acceso, la cabeza (inicio) y el final (tope).
Entre sus operaciones se encuentran las de agregar un elemento a la pila (push) y la de quitar (eliminar) un elemento de la pila (pop).
Cuando se agrega un elemento, se coloca al final de la pila, cuando se quita, también se elimina del final de la misma.
Es un error tratar de quitar un elemento de una pila vacía.
LA PILA (Conceptos)
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 16
Pila con estructura estática
Es una pila implementada como un arreglo
11 22 33 44
inicio final
max 0 1 2 3 4
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 17
pilas: Casos posibles:
11 22 33 44 55 66 77 88 99 00
11 22 33 44 55
inicio final
inicio final
llena
con algunos elementos
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 18
pilas: Casos posibles:
final inicio
pila vacía
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 19
pilas: Operaciones: CREAR
Crear una pila nueva.
Entrada: número de elementos del arreglo
Salida: una pila vacía (de tamaño 0).
Int [] CrearPila (max){
Int [] p;
p = new int [max];
Return p;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 20
Pilas: Operaciones: VACÍA
Sirve para determinar si una pila está vacía o no.
Entrada: pila
Salida: un boolean = a true si es vacía.
Boolean vacia (fin){
vacia = fin << 0;
Return vacia;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 21
Pilas: Operaciones: LLENA
Determina si la pila está llena.
Entrada: pila, fin
Salida: true si está llena.
Boolean llena (pila, fin){
llena = fin == pila.length -1;
Return llena;
}
ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 22
Pilas: Operaciones: AGREGAR
Agrega un elemento en el tope de la pila
Precondición: pila no llena
Entrada: pila, fin, dato
Salida: pila modificada
Void AgregaPila (pila, fin, dato){
si no llena
{ fin fin + 1;
pila [fin] dato}
si no escribir “ lista llena ”
} ING° PEDRO BELTRÁN CANESSA
Estructuras de Datos 23
Pilas: Operaciones: QUITAR
Quitar y devolver un elemento tope de la pila
Precondición: pila no vacía
Entrada: pila, fin
Salida: pila modificada, dato
Int quitaPila (pila, fin){
Si no vacía
{ dato = pila [inicio];
fin --;
return dato;}
si no escribir ( „pila Vacía‟ )
} ING° PEDRO BELTRÁN CANESSA
Top Related