ingeniería

FILA
S de datos cuyos elementos
Es una estructura
se
insertan por un lado y se eliminan por otro,
es decir
los elementos se eliminan en el mismo orden
en que se insertan. (PEPS= Primero en entrar,
primero en
salir).
A
B
C FILA
MAXFILA
1
frente

2

3
final

4

5

6

7

Aplicaciones de las FILAS
El concepto de FILA está ligado a computación.
Una aplicación de ellaspuede verse en las colas
de impresión, cuando hay una sola impresora
para atender a varios usuarios. En estos casos
se forma una cola con los trabajos que esperan
para ser impresos, los cuales se irán
imprimiendo en el orden en que fueron
ingresando a la cola.
Otro caso de aplicación en computación es en
los sistemas de tiempo compartido, en donde
varios usuarios comparten recursos comoel
procesador, la memoria, etc.. El sistema

Formas de implementar una FILA:
a) Utilizando arreglos (memoria estática)
b) Utilizando listas enlazadas (memoria dinámica)
Arreglos:
A
1
frente

B
2

C
3
final

MAXFILA
4

5

6

7

DESCRIPCION LOGICA DEL Tipo de Dato
Abstracto FILA:
OPERACIONES:
a) CREAR FILA: crea una fila vacía
b) FILA LLENA:
DESCRIPCION: verifica siuna fila se encuentra llena
ENTRADAS: la fila que se va a verificar
SALIDAS: valor booleano que indica si la fila esta llena o
no
PRECONDICION: la fila a verificar existe
POSTCONDICION: ninguna, la fila NO se modifica
c) FILA VACIA:
DESCRIPCION: verifica si una fila se encuentra vacía
ENTRADAS: la fila que se va a verificar
SALIDAS: valor booleano que indica si la fila esta vacía o
noPRECONDICION: la fila a verificar existe

d) INSERTAR:
DESCRIPCION: agrega un elemento en la Fila
ENTRADAS: la fila a la que se agregará el elemento y el
elemento a insertar
SALIDAS: la fila con un elemento adicional
PRECONDICION: la fila está creada y no está llena
POSTCONDICION: la fila queda con un elemento
adicional
agregado por el extremo del FINAL de la fila
e) SACAR:DESCRIPCION: elimina un elemento en la Fila
ENTRADAS: la fila a la que se va a quitar el elemento
SALIDAS: la fila con un elemento menos y el elemento
que se
eliminó
PRECONDICION: la fila esta creada y no esta vacía
POSTCONDICION: la fila queda con un elemento menos
eliminado por el extremo del FRENTE de la
fila

Diseños para FILAS

) Con FRENTE fijo: es necesario realizar corrimientos cada
vezque se elimine un elemento de la FILA. Es muy fácil de
implementar, pero no es práctico cuando existe una gran
cantidad de elementos que se van a sacar de la FILA.

) Con FRENTE y FINAL movibles: se utiliza generalmente
solo para eliminaciones ya que da FILA LLENA sin que lo est

) Fila circular: para hacer un uso más eficiente de la memo
disponible, se trata a la FILA como una estructuracircular, e
decir, el elemento anterior al primero es el último

Ejemplos de FILA CIRCULAR:
a) Frente < Final:

W X Y
Frente

Z
Final

B) Frente > Final:

P
Final

L M N O
Frente

Implementación de filas utilizando
arreglos
La definición de una Fila ha de
contener un array para almacenar los
elementos de la fila, y dos referencias o
punteros que mantienen las posicionesfrente y final de la fila.

public class filaEstatica
{
private static final int TAMFILA=10;
private int frente;
private int fin;
int [] fila;
public filaEstatica ()
{ frente=fin=-1;
fila=new int[TAMFILA];
}

PASOS PARA INSERTAR EN UNA FILA
•  checar espacio
• actualizar el apuntador final dependiendo
de:
Caso 1: si es el primer elemento en la fila: Frente

y Fin = 0
Caso2: si no es el primero pero es el elemento
que “está” en MAXFILA entonces FIN = 0
Caso 3: ninguna de las anteriores FIN = FIN + 1

• insertar el elemento

public boolean insertar (int elemento)
{
boolean x=true;
if(!filaLlena())
{
fin= (fin + 1 )% TAMFILA;
fila[fin]= elemento;
if (frente==-1){frente=0;}
}
else
x=false;
return x;
}

Pasos para eliminar un
elemento de la...