Download Colas - WordPress.com

ESTRUCTURA DE DATOS
Adaptadores de contenedores:
pilas, colas, colas de prioridad
PILA
• Es una estructura de datos en la cual la inserción y
borrado de nuevos elementos se realiza sólo por un
extremo llamado cima o tope.
• Son estructuras utilizadas muy a menudo como
herramientas de programación de tipo LIFO (Last inFirst out)
• Permiten el acceso solo a un elemento a la vez: el
último elemento insertado
• La mayoría de los procesadores utilizan una
arquitectura basada en pilas
EJEMPLOS DE PILAS
• Pila de platos
• Pila de bandejas
• Pila de monedas
CARACTERISTICAS DE
UNA PILA
• Es una estructura de datos dinámica.
• Es una estructura tipo LIFO (Last In,
First Out)
• El tipo de datos PILA, no existe como
tal en ningún lenguaje, por lo cual se
hace necesario implementarlo mediante
las herramientas del lenguaje de
programación.
OPERACIONES DE UNA PILA
• CREAR: Se usa para inicializar o preparar la pila.
• ENTRAR (PUSH): Introduce un elemento a la
pila.
• SACAR (POP): Eliminar un elemento de la pila.
• PILAVACIA: Se usa para comprobar si la pila está
vacía.
• PILALLENA: Se usa en el caso de que la pila sea
implementada en un arreglo y tiene el fin de
comprobar si la pila no está desbordando los límites
del arreglo.
OPERACIONES DE UNA PILA
ENTRAR (PUSH)
OPERACIONES DE UNA PILA
SACAR (POP)
IMPLEMENTACION
DE UNA PILA
• Pilas alojadas en arreglos.
• Pilas con punteros.
USOS DE LAS PILAS
• Compiladores.
• Sistemas operativos.
• Programas de aplicación.
Pilas - Eficiencia
• El tiempo de ejecución de las operaciones
primarias de una pila no depende del tamaño de
la pila
• Push y Pop se realizan en tiempo constante O(1)
- no es necesario hacer ninguna comparación
Pilas: código en JAVA
• En JAVA para trabajar con pilas se usa la clase
Stack (java.util.Stack). A continuacion el
comando para crear una pila:
Stack pila = new Stack();
Los métodos mas usados en las
pilas son:
– push() “empuja” un objeto al tope del stack.
– peek() regresa el objeto en el tope del stack pero sin
sacarlo.
– pop() regresa el objeto en el tope del stack,
removiéndolo.
– search() Se puede buscar un objeto dentro del stack
para obtener su índice utilizando dicho método.
Ejemplos de pilas
Stack pila = new Stack();
pila.push("1");
pila.push("2");
pila.push("3");
//observar el elemento en el tope del stack sin sacarlo.
Object objTop = pila.peek();
Object obj3 = pila.pop(); //la cadena "3" está en el tope del stack.
Object obj2 = pila.pop(); //la cadena "2" está en el tope del stack.
Object obj1 = pila.pop(); //la cadena "1" está en el tope del stack.
int index = pila.search("3"); //index = 3
COLA
Es una estructura de datos en la cual
la inserción de elementos se hacen
por un extremo (llamado FINAL) y
las eliminaciones se hacen por otro
extremo (llamado FRENTE).
EJEMPLOS DE COLAS
• Fila de personas
• Una caravana de carros
• Lista de archivos a ser impresos
CARACTERISTICAS DE
UNA COLA
• Es una estructura de datos dinámica.
• Es una estructura tipo FIFO (FIRST
IN, FIRST OUT)
• El tipo de datos COLA, no existe como
tal en ningún lenguaje, por lo cual se
hace necesario implementarlo mediante
las herramientas del lenguaje de
programación.
TIPOS DE COLAS
• Cola simple: Estructura lineal donde los elementos
salen en el mismo orden en que llegan.‡
• Cola circular: Representación lógica de una cola
simple en un arreglo.‡
• Cola de Prioridades: Estructura lineal en la cual los
elementos se insertan en cualquier posición de la cola
y se remueven solamente por el frente.‡
• Cola Doble (Bicola): Estructura lineal en la que los
elementos se pueden añadir o quitar por cualquier
extremo de la cola (cola bidireccional)
OPERACIONES DE UNA COLA
• CREAR: Se usa para inicializar o preparar la cola.
• ENTRAR (PUSH): Introduce un elemento a la
cola. Este se agrega al FINAL.
• SACAR (POP): Elimina un elemento de la cola.
Se elimina por el FRENTE.
• COLAVACIA: Se usa para comprobar si la cola
está vacía.
• COLALLENA: Se usa en el caso de que la cola
sea implementada en un arreglo y tiene el fin de
comprobar si la cola no está desbordando los
límites del arreglo.
OPERACIONES DE UNA COLA
• ENTRAR (PUSH)
OPERACIONES DE UNA COLA
• SACAR(POP)
IMPLEMENTACION
DE UNA COLA
• Colas alojadas en arreglos.
• Colas con punteros.
USOS DE LAS COLAS
• Impresoras.
• Administración de tareas.
Colas - Eficiencia
• El tiempo de ejecución de las operaciones
primarias de una colas no depende del tamaño de
la cola
• Encolar y Desencolar se realizan en tiempo
constante O(1) - no es necesario hacer ninguna
comparación
Colas: código en Java
• La interfaz Queue (java.util.Queue) es un subtipo de
la interfaz Collection, representa una lista ordenada
de objetos justo como List pero su uso es ligéramente
distinto.
• Una cola está diseñada para tener sus elementos
insertados al final de la cola y removidos del inicio.
Justo como una fila de banco o de supermercado.
• Al ser un subtipo de Collection, todos los métodos de
Collection también se encuentran disponibles en la
interfaz Queue.
• Como Queue es una interfaz, es necesario
instanciar una implementación concreta para
poder utilizarla.
• Existen 2 clases en el API de Java que
implementan la interfaz Queue:
– java.util.LinkedList
– java.util.PriorityQueue
• LinkedList es una implementación es una
implementación estándar de una cola.
• PriorityQueue guarda sus elementos internamente
de acuerdo a su orden natural (si implementan la
interfaz Comparable), o de acuerdo a un Comparador
(Comparator) pasado a PriorityQueue.
Aquí hay algunos ejemplos de cómo crear una instancia
de Queue:
Queue colaA = new LinkedList();
Queue colaB = new PriorityQueue();
• Para agregar elementos a una cola, se llama
su método add(). Este método se hereda
de la interfaz Collection:
Queue colaA = new LinkedList();
colaA.add("elemento 1");
colaA.add("elemento 2");
colaA.add("elemento 3");
• El orden en el cual los elementos se agregan a Queue
es almacenado internamente y depende de la
implementación. Esto mismo es cierto para el orden
en el cual los elementos son obtenidos (removidos)
de la cola.
• Se puede observar cuál es el elemento que se
encuentra a la “cabeza” de la cola sin quitarlo
utilizando el método element():
Object firstElement = queueA.element();
• Para quitar el primer elemento de la cola, se
utiliza el método remove().
• Para remover (quitar) elementos de la cola, se
llama el método remove(). Éste método quita el
elemento que se encuentra a la “cabeza” de la
cola:
Object primerElemento = colaA.remove();
• También es posible iterar todos los elementos de la cola, en
lugar de procesarlos uno a la vez:
Queue colaA = new LinkedList();
colaA.add("elemento 0");
colaA.add("elemento 1");
colaA.add("elemento 2");
//acceso con iterador
Iterator iterador = colaA.iterator();
while(iterador.hasNext(){
String elemento = (String) iterador.next();
}
//acceso con ciclo for
for(Object objecto : colaA) {
String elemento = (String) objecto;
}
Cola de prioridad
• Una cola de prioridades es una estructura de
datos en la que los elementos se atienden en el
orden indicado por una prioridad asociada a cada
uno.
• Si varios elementos tienen la misma prioridad, se
atenderán de modo convencional según la
posición que ocupen.
Características generales
• Este tipo especial de colas tienen las mismas
operaciones que las colas , pero con la condición de
que los elementos se atienden en orden de prioridad.
• Ejemplos de la vida diaria serían la sala de urgencias
de un hospital, ya que los enfermos se van atendiendo
en función de la gravedad de su enfermedad.
• Entendiendo la prioridad como un valor numérico y
asignando a altas prioridades valores pequeños, las
colas de prioridad nos permiten añadir elementos en
cualquier orden y recuperarlos de menor a mayor.
Implementación
• Hay 2 formas de implementación:
1. Añadir un campo a cada nodo con su prioridad.
Resulta conveniente mantener la cola ordenada por
orden de prioridad.
2. Crear tantas colas como prioridades haya, y
almacenar cada elemento en su cola.
Tipos de cola de prioridad
• Colas de prioridades con ordenamiento
ascendente: en ellas los elementos se insertan de
forma arbitraria, pero a la hora de extraerlos, se
extrae el elemento de menor prioridad.
• Colas de prioridades con ordenamiento
descendente: son iguales que la colas de
prioridad con ordenamiento ascendente, pero al
extraer el elemento se extrae el de mayor
prioridad.
Operaciones
Las operaciones de las colas de prioridad son las
mismas que las de las colas genéricas:
– Crear: se crea la cola vacía.
– Añadir: se añade un elemento a la cola, con su
correspondiente prioridad.
– Eliminar: se elimina el elemento frontal de la cola.
– Frente: se devuelve el elemento frontal de la cola.
– Destruye: elimina la cola de memoria.
Ejemplo de cola de prioridad
import java.util.*;
public class PriorityQueueDemo {
public static void main(String args[]) {
// create priority queue
PriorityQueue < Integer > prq = new PriorityQueue < Integer > ();
// insert values in the queue
for ( int i = 0; i < 10; i++ ){
prq.add (new Integer (i)) ;
}
Ejemplo de cola de prioridad
(cont.)
// create iterator from the queue
Iterator it = prq.iterator();
System.out.println ( "Priority queue values are: ");
while (it.hasNext()){
System.out.println ( "Value: "+ it.next());
}
}
}