Igor Santos Grueiro
A diario hacemos
colas
para comer
para ir al cine
En nuestro ordenador
también hay colas
Una cola es una estructura formada por
una secuencia de 0 a N elementos, en
la que la extracción de elementos se
hace en orden de inserción
Encolar
Desencolar
Cola
Objeto
En un cola se recoge el extremo inicial
de la cola
Un elemento nuevo se inserta por el
extremo final de la cola
Es un tipo de estructura FIFO
(First Input First Output)
Podemos hacer varias operaciones:
Crear una cola
Vaciar una cola
Objeto
Objeto
Comprobar si una cola está Vacía
NO
Sí
Objeto
Objeto
Obtener una copia del primer elemento
Objeto
Objeto
Se
Insertar
conoce
uncomo
elemento
encolar
en ola“put”
cola
Objeto
Objeto
Objeto
SeRecoger
conoce como
el primer
desencolar
elemento
o “get”
y
eliminarlo de la cola
Objeto
Objeto
Construyamos una cola
Nos hace falta una estructura que
enlace un elemento al siguiente
Nodo
Nodo siguiente
Object elemento
}
public class NodoCola{
private Object elemento;
private NodoCola siguiente;
public NodoCola(Object elemento,
NodoCola siguiente){
this.elemento = elemento;
this.siguiente = siguiente;
}
public NodoCola(Object elemento){
this.elemento = elemento;
this.siguiente = null;
}
public Object getElemento(){
return elemento;
}
public NodoCola getSiguiente(){
return siguiente;
}
public void insertarSig(Object x) {
NodoCola nuevoNodo = new NodoCola(x, this.siguiente);
this.siguiente = nuevoNodo;
}
}
Ahora la clase
Cola
}
public class Cola{
private NodoCola primero;
private NodoCola ultimo;
private int cont;
public Cola(){
this.primero = null;
this.ultimo = null;
this.cont = 0;
}
// …
}
}
Para vaciar se ponen a null el
primero y el último
// …
public vaciar(){
this.primero = null;
this.ultimo = null;
this.cont = 0;
}
// …
Para comprobar si está vacía
miramos si el primero es
null
//…
public boolean estaVacia(){
return (this.primero == null);
}
//…
Para insertar un elemento
se añade un elemento como siguiente del
último nodo de la cola
//…
public void put(Object x){
if (primero == null){
this.primero = new NodoCola(x);
this.ultimo = primero;
}else{
this.ultimo.insertarSiguiente(x);
this.ultimo = this.ultimo.getSiguiente();
}
this.cont++;
}
//…
Cim
Primero
a
Último
Cim
a
public Object cima(){
return v[cont-1];
}
Para devolver el elemento al
frente se devuelvo el
primero
//…
public Object frente(){
if (this.primero !=null)
return this.primero.getElemento();
else
return null;
}
//…
public Object cima(){
return v[cont-1];
}
Para borrar el elemento al
frente se pone el primero al
valor siguiente del primero
previo
//…
public void borrar(){
if (this.primero !=null){
this.primero = this.primero.getSiguiente();
this.cont--;
}
}
//…
Cim
Primero
a
Último
Cim
a
public Object cima(){
return v[cont-1];
}
Para desencolar el elemento al
frente se recupera y se borra el
elemento primero
//…
public Object get(){
if (this.primero == null)
return null;
else {
this.cont--;
NodoCola nodoTmp = this.primero;
this.primero = this.primero.getSiguiente();
return nodoTmp.getElemento();
}
}
//…
Cim
Primero
a
Devolvemos el objeto
dentro del nodo
eliminado
Último
Cim
a
public Object cima(){
return v[cont-1];
}
También, podemos recuperar
el número de elementos
insertados en la cola
//…
public int tamanyo(){
return this.cont;
}
//…
Ya comprendemos las colas
Ejercicio palíndromos
Diseñar un programa que determine si una frase
introducida por teclado es o no palíndroma.
Una frase es palíndroma si la secuencia de caracteres de
izquierda a derecha en la frase es la misma que de
derecha a izquierda. En esta comprobación no se tendrá
en cuenta los caracteres blancos que separan las palabras
de la frase, ni se diferenciaran las mayúsculas de las
minúsculas.
El programa deberá hacer uso en este programa de una
Pila y de una Cola para verificar que la frase es o no
palíndroma.
Descargar

05b-Colas