Download - Estructuras en Memoria
-
8/19/2019 Estructuras en Memoria
1/62
Estructuras de datos en memoria principal
Franco Guidi Polanco Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chile
-
8/19/2019 Estructuras en Memoria
2/62
25-05-14Franco Guidi Polanco (PUCV-EII) 2
Estructuras de datos
! Estructuras básicas" Arreglo" Lista enlazada
• Simplemente enlazada• Doblemente enlazada
! Colecciones implementadas sobre las estructuras básicas:" Lista, Lista con iterador" Lista circular" Pila" Cola" Hashtable" Vector (Java)" (Otras)
-
8/19/2019 Estructuras en Memoria
3/62
25-05-14Franco Guidi Polanco (PUCV-EII) 3
Arreglo
! Es una colección ordenada de elementos delmismo tipo.
! Es de largo fijo, definido al momento deinstanciarlo.
! El acceso a los elementos se hace a través de unsubíndice.
! Fácil de recorrer en ambos sentidos.!
Estudiado en cursos anteriores
-
8/19/2019 Estructuras en Memoria
4/62
25-05-14Franco Guidi Polanco (PUCV-EII) 4
Listas enlazadas
! Son estructuras dinámicas: se asigna memoriapara los elementos de la lista en la medida que esnecesario.
! Cada elemento se almacena en una variable
dinámica denominada nodo.! En la lista simplemente enlazada, cada nodo
apunta al nodo que contiene el elemento siguiente
-
8/19/2019 Estructuras en Memoria
5/62
25-05-14Franco Guidi Polanco (PUCV-EII) 5
Esquema tentativo de una lista simplementeenlazada
nullhead
ListaEnlazada
Nodos
data data data data
-
8/19/2019 Estructuras en Memoria
6/62
25-05-14Franco Guidi Polanco (PUCV-EII) 6
Datos contenidos en la lista
! Los nodos de una lista contendrán datos del tipodeclarado en la estructura del nodo. Por ejemplo:" Tipos primitivos (byte, int, boolean, char, etc.)" Referencias a objetos
! En los siguientes ejemplos consideraremos el usode listas de enteros, aunque las técnicas que serándescritas son aplicables a cualquier otro “tipo” delista.
-
8/19/2019 Estructuras en Memoria
7/62
25-05-14Franco Guidi Polanco (PUCV-EII) 7
Diagrama de clases de una lista simplementeenlazada
! Diagrama de clases (lista de enteros):
Lista
agregarAlFinal(d:Data)estáContenido(d:Data):booleaneliminar(d:Data):booleanimprimirContenido()
Nodo
data:int
getData():intsetNext(n:Nodo)getNext():NodoNodo(d:Data,n:Nodo)
head
1..1
next
! Diagrama de objetos:
:Lista head:Nodo
data = 1
:Nodo
data = 20
:Nodo
data = -1
-
8/19/2019 Estructuras en Memoria
8/62
25-05-14Franco Guidi Polanco (PUCV-EII) 8
Una lista simplemente enlazada (versiónpreliminar)
! Declaración de la Lista:
public class Lista{
Nodo head = null;
public void agregarAlFinal(int data){
...
}
public void imprimirContenido(){
...
}
public boolean estaContenido(int data){
...}
public boolean eliminar(int data){
...
}
}
-
8/19/2019 Estructuras en Memoria
9/62
25-05-14Franco Guidi Polanco (PUCV-EII) 9
Nodos en una lista simplemente enlazada
public class Nodo{ private int data;
private Nodo next;
public Nodo(int d, Nodo n){
data = d;
next = n;
} public int getData(){
return data;
}
public Nodo getNext(){
return next;
}
public void setNext(Nodo n){
next = n;
}}
-
8/19/2019 Estructuras en Memoria
10/62
25-05-14Franco Guidi Polanco (PUCV-EII) 10
Inserción en la lista simplemente enlazada
! Insertar elementos:" Al final de la lista
" Manteniendo un orden
" Al inicio de la lista
Ejemplo: [ 25, 1, 14, 4 ]
nullhead
25 1 14 4
nullhead
1 4 14 25
head
4 14 1 25
null
-
8/19/2019 Estructuras en Memoria
11/62
25-05-14Franco Guidi Polanco (PUCV-EII) 11
Inserción de elementos al final de la lista
! Caso 1: la lista está vacía (variable head contienenull)
head null
public Lista{
...
public void agregarAlFinal(int dato){
...
head = new Nodo( dato, null );...
}
...
}
head
25
null
-
8/19/2019 Estructuras en Memoria
12/62
25-05-14Franco Guidi Polanco (PUCV-EII) 12
Inserción de elementos al final de la lista
! Caso 2 (general): la lista tiene al menos unelemento
head
25 1
null
14
aux
head
25 1
null
aux
1. ubicar último nodo de la lista(aquél cuya variable next
contiene null)
2. Instanciar el nuevo nodocon el contenido indicado
3. Asignar el nuevo nodo a la
variable next del último
nodo (asegurándose de quela variable next del nuevo
nodo sea igual a null)
aux.setNext(new Nodo(dato, null));
-
8/19/2019 Estructuras en Memoria
13/62
25-05-14Franco Guidi Polanco (PUCV-EII) 13
Inserción de elementos al final de la lista
! Caso general:
public class Lista{
...
public void agregarAlFinal(int dato){
Nodo nuevo = new Nodo(dato, null);
if( head == null )
head = nuevo;
else{
Nodo aux = head;
while( aux.getNext() != null)
aux = aux.getNext();
aux.setNext( nuevo );
} }
...
}
-
8/19/2019 Estructuras en Memoria
14/62
25-05-14Franco Guidi Polanco (PUCV-EII) 14
Recorrido de la lista
! Método que imprime el contenido de la lista:
public class Lista{
...
public void imprimirContenido(){
Nodo aux = head; while( aux != null ){
System.out.print( aux.getData() + "; " );
aux = aux.getNext();
}
System.out.println(); ...
}
-
8/19/2019 Estructuras en Memoria
15/62
25-05-14Franco Guidi Polanco (PUCV-EII) 15
Búsqueda en la lista
! Retorna true si el elemento está contenido en lalista
public class Lista{
...
public boolean estaContenido(int data){
Nodo aux = head;
while( aux != null ){
if( data == aux.getData() )
return true;
aux = aux.getNext();
}
return false; }
...
}
-
8/19/2019 Estructuras en Memoria
16/62
25-05-14Franco Guidi Polanco (PUCV-EII) 16
Eliminación de un elemento
! Requiere identificar el nodo a borrar.
! Caso 1: es el primer nodo de la lista
nullhead
1 14 425
nullhead
1 14 425
nullhead
1 14 4
head = head.getNext();
Sin otras referencias: candidato a eliminación(recolector de basura de Java)
-
8/19/2019 Estructuras en Memoria
17/62
25-05-14Franco Guidi Polanco (PUCV-EII) 17
Eliminación de un elemento
! Caso 2 (general): no es el primer nodo de la lista
nullhead25 1 414
null
head
25 1 414
aux
Sin otras referencias: candidato a eliminación(recolector de basura de Java)
nullhead
25 1 4
aux.setNext(aux.getNext().getNext());
-
8/19/2019 Estructuras en Memoria
18/62
25-05-14Franco Guidi Polanco (PUCV-EII) 18
Eliminación de un elementopublic class Lista{
... public boolean eliminar(int data){
if( head != null)
if( head.getData() == data ){
head = head.getNext();
return true;
}else{
Nodo aux = head;
while( aux.getNext() != null ){
if( aux.getNext().getData() == data ){
aux.setNext( aux.getNext().getNext() );
return true;
}
aux = aux.getNext();}
}
return false;
}
...
}
-
8/19/2019 Estructuras en Memoria
19/62
25-05-14Franco Guidi Polanco (PUCV-EII) 19
Simplificación del esquema propuesto: uso de unnodo “fantasma”
! En el esquema propuesto se deben hacerexcepciones al insertar y eliminar el nodo delcomienzo de la lista.
! El manejo se simplifica si se utiliza un nodo “fantasma”:" Es un nodo siempre presente en la lista" Su contenido es irrelevante (el valor u
objeto contenido no forma parte de la lista).
-
8/19/2019 Estructuras en Memoria
20/62
25-05-14Franco Guidi Polanco (PUCV-EII) 20
Lista simplemente enlazada con nodo fantasma
! Lista vacía:
! Lista con elementos:
nullhead
25 1 4
null
head
Primer elemento de la lista
public class Lista{
Nodo head;
public Lista(){
head = new Nodo(0, null);}
...
}
Valor irrelevante
-
8/19/2019 Estructuras en Memoria
21/62
25-05-14Franco Guidi Polanco (PUCV-EII) 21
Operación de inserción en la lista con nodo fantasma
! La inserción del primer elemento de la lista entraen el caso general:
1
head null
aux aux.setNext(new Nodo(dato, null));
public void agregarAlFinal(int dato){
Nodo aux = head;
while( aux.getNext() != null)
aux = aux.getNext();
aux.setNext( new Nodo(dato, null) );
} }
Clase
Lista
-
8/19/2019 Estructuras en Memoria
22/62
25-05-14Franco Guidi Polanco (PUCV-EII) 22
Eliminación del primer elemento en la lista con nodofantasma
! La eliminación del primer elemento de la lista entraen el caso general:
nullhead
1 414
aux
Sin otras referencias: candidato a eliminación
(recolector de basura de Java)
aux.setNext(aux.getNext().getNext());
-
8/19/2019 Estructuras en Memoria
23/62
25-05-14Franco Guidi Polanco (PUCV-EII) 23
Eliminación del primer elemento en la lista con nodofantasma (cont.)
public boolean eliminar(int data){
Nodo aux = head;
while( aux.getNext() != null ){if( aux.getNext().getData() == data ){
aux.setNext( aux.getNext().getNext() );
return true;
}
aux = aux.getNext();
}
return false;
}
-
8/19/2019 Estructuras en Memoria
24/62
25-05-14Franco Guidi Polanco (PUCV-EII) 24
Mejora al procedimiento de inserción de elementos al finalde la lista
! El procedimiento descrito anteriormente requiere que todaslas veces sea encontrado el último elemento de la lista.
! Más conveniente: tener una variable de instancia quesiempre referencie al último elemento de la lista.
! Esto aplica a listas con o sin nodo fantasma (con pequeñoscambios).
-
8/19/2019 Estructuras en Memoria
25/62
25-05-14Franco Guidi Polanco (PUCV-EII) 25
Mejora al procedimiento de inserción deelementos al final de la lista (cont.)
! Diagrama de clases:
Lista
agregarAlFinal(d:Data)
estáContenido(d:Data)eliminar(d:Data):booleanimprimirContenido()
Nodo
data: int
getData():DatasetNext(n:Nodo)getNext():NodoNodo(d:Data,n:Nodo)
head
1..1
tail
1..11..1
! Diagrama de objetos:
Lista ghost:Nodo1stNode:Nodo
data = 20
2ndNode:Nodo
data = -1
head
tail
-
8/19/2019 Estructuras en Memoria
26/62
25-05-14Franco Guidi Polanco (PUCV-EII) 26
Mejora al procedimiento de inserción de elementos al finalde la lista (cont.)
! La variable de instancia tail mantiene siempre lareferencia al último elemento:
nullhead
25 1 4
nullhead
tail
tail
public class Lista{
Nodo head, tail;
public Lista(){
head = new Nodo(0, null);tail = head;
}
...
}
-
8/19/2019 Estructuras en Memoria
27/62
25-05-14Franco Guidi Polanco (PUCV-EII) 27
Mejora al procedimiento de inserción de elementos al finalde la lista (cont.)
! El método agregarAlFinal ya no requiere recorrer lalista para ubicar el último nodo:
! La varaible tail es actualizada después de la inserción.
! Notar que el procedimiento de eliminación debe actualizarla referencia tail si se remueve el último nodo de la lista.
public void agregarAlFinal(int dato){
Nodo aux = new Nodo(dato, null) ;
tail.setNext( aux );
tail = aux;}
Versión con
nodo fantasma
-
8/19/2019 Estructuras en Memoria
28/62
25-05-14Franco Guidi Polanco (PUCV-EII) 28
Inserción en orden/al inicio
! Ejercicio 1: implemente el método:
agregarEnOrden(int dato)
que recibe un entero y lo agrega en ordenascendente a la lista.
!
Ejercicio 2: implemente el métodoagregarAlInicio(int dato)
que recibe un entero y lo agrega comoprimer elemento.
-
8/19/2019 Estructuras en Memoria
29/62
25-05-14Franco Guidi Polanco (PUCV-EII) 29
Resumen listas simplemente enlazadas
! Útiles para guardar un número no predefinido deelementos.
! Distintas disciplinas para mantener los datosordenados (y para removerlos).
! El acceso a los nodos es secuencial; el recorrido esen una sola dirección (Ejercicio: confrontar conarreglos)
-
8/19/2019 Estructuras en Memoria
30/62
25-05-14Franco Guidi Polanco (PUCV-EII) 30
Listas doblemente enlazadas
! Están diseñadas para un acceso fácil al nodo siguiente y alanterior.
! Cada nodo contiene dos referencias: una apuntando al nodosiguiente, y otra apuntando al nodo anterior.
!
El acceso a los nodos sigue siendo secuencial.! La técnica del nodo fantasma puede ser útil también en estetipo de lista.
nullhead
1 14 4
null
-
8/19/2019 Estructuras en Memoria
31/62
25-05-14Franco Guidi Polanco (PUCV-EII) 31
Comentarios finales sobre estructuras elementales
! Estar abierto a definir y utilizar otras estructuras.
! Ejemplo: Lista simplemente enlazada y circular
head
25 1 414
-
8/19/2019 Estructuras en Memoria
32/62
Colecciones implementadas sobre estructuras
básicas
Franco Guidi Polanco Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chile [email protected]
-
8/19/2019 Estructuras en Memoria
33/62
25-05-14Franco Guidi Polanco (PUCV-EII) 33
Interfaces versus implementación
! En la sección anterior estudiamos estructuras elementalespara implementar colecciones.
! En esta sección estudiaremos colecciones clásicas, desdedos perspectivas:" La interfaz de la colección (cómo se utiliza)"
La implementación de la colección (cómo se construye)! Una misma interfaz puede ser soportada por múltiples
implementaciones! La eficiencia en la operación de una colección va a
depender de su implementación
-
8/19/2019 Estructuras en Memoria
34/62
25-05-14Franco Guidi Polanco (PUCV-EII) 34
Listas
!
Representa una colección conformada por una secuencia finita yordenada de datos denominados elementos.! Ordenada implica que cada elemento tiene una posición. ! Los elementos corresponden a un tipo de dato.!
La lista está vacía cuando no contiene elementos.
! El número de elementos se denomina largo de la lista.
! El comienzo de la lista es llamado cabeza (head), y el final cola (tail).
!
Notación: (a1, a2, ..., an).
-
8/19/2019 Estructuras en Memoria
35/62
25-05-14Franco Guidi Polanco (PUCV-EII) 35
Lista: versión clásica
! Además de los datos, el estado de la lista contieneuna identificación (referencia) al “dato actual”.
(12, 22, 50, 30). ! La lista provee operaciones para:
" Cambiar (modificar la referencia) del dato actual" Retornar el dato actual" Eliminar el dato actual" Modificar el dato actual
" Insertar un dato en la posición del dato actual" Borrar toda la lista, buscar elementos en la lista, contar
sus elementos
-
8/19/2019 Estructuras en Memoria
36/62
25-05-14Franco Guidi Polanco (PUCV-EII) 36
Interfaces para la versión clásica de la lista
! No hay una única definición formal de interfaz.
! Estudiaremos dos extremos:" Interfaz elemental"
Interfaz extendida
-
8/19/2019 Estructuras en Memoria
37/62
25-05-14Franco Guidi Polanco (PUCV-EII) 37
Interfaz elemental para la lista clásica
public interface List {
public void clear(); // Elimina todos los elem.
public void insert(Object item); // Inserta elem. en act.
public Object remove(); // Saca/retorna elem.
public void setFirst(); // Setea act. en 1ra pos.
public void next(); // Mueve act. a sig. pos.
public int length(); // Retorna largo
public void setValue(Object val);// Setea elemento
public Object currValue(); // Retorna elemento
public boolean isEmpty(); // True: lista vacía
public boolean eol(); // True: act en end of list
public String toString(); // Retorna lista de elem.
}
Nota: pos.=posición; act.=posición actual; sig.:siguiente; prev.:previa
-
8/19/2019 Estructuras en Memoria
38/62
25-05-14Franco Guidi Polanco (PUCV-EII) 38
Ejemplo de uso de una lista (versión clásica)
! Sea la siguiente lista:
! Operaciones:"
miLista.insert(99) :
" miLista.next():
miLista=(12, 22, 50, 30)
Dato actual
miLista=(12, 99, 22, 50, 30)
Dato actual
miLista=(12, 99, 22, 50, 30)
Dato actual
-
8/19/2019 Estructuras en Memoria
39/62
25-05-14Franco Guidi Polanco (PUCV-EII) 39
Ejemplo de uso de una lista (versión clásica)
" miLista.currValue():
"
miLista.remove():
"
miLista.setFirst():
miLista=(12, 99, 22, 50, 30)
Dato actual22
miLista=(12, 99, 50, 30)
(Nuevo) dato actual22
miLista=(12, 99, 50, 30)
Dato actual
-
8/19/2019 Estructuras en Memoria
40/62
25-05-14Franco Guidi Polanco (PUCV-EII) 40
Interfaz extendida para la lista clásica
Nota: pos.=posición; act.=posición actual; sig.:siguiente; prev.:previa
public interface ExtendedList { public void clear(); // Elimina todos los elem.
public void insert(Object item); // Inserta elem. en act.
public void append(Object item); // Agrega elem. al final
public Object remove(); // Saca/retorna elem.
public void setFirst(); // Setea act. en 1ra pos.
public void next(); // Mueve act. a sig. pos.
public void prev(); // Mueve act. a pos. prev.
public int length(); // Retorna largo
public void setPos(int pos); // Setea act. a pos
public void setValue(Object val);// Setea elemento
public Object currValue(); // Retorna elemento
public boolean isEmpty(); // True: lista vacía
public boolean eol(); // True: act en end of list public String toString(); // Retorna lista de elem.
}
-
8/19/2019 Estructuras en Memoria
41/62
25-05-14Franco Guidi Polanco (PUCV-EII) 41
Implementación de la lista clásica
!
La conveniencia de una u otra implementación depende delas operaciones definidas en la interfaz.
! Interfaz elemental:" Implementación basada en lista simplemente enlazada"
Implementación basada en arreglos" Implementación basada en lista doblemente enlazada(sobredimensionada)
! Interfaz extendida:" Implementación basada en arreglos"
Implementación basada en lista doblemente enlazada" Implementación basada en lista simplemente enlazada
-
8/19/2019 Estructuras en Memoria
42/62
25-05-14Franco Guidi Polanco (PUCV-EII) 42
Implementación de la lista clásica basada enarreglos
! Usa un arreglo para almacenar los elementos de lalista.
! Los elementos son almacenados en posicionescontiguas en el arreglo.
!
El elemento “i” de la lista se almacena en la celda “i-1” del arreglo.! La cabeza de la lista siempre está en la primera
posición del arreglo (0).! El máximo número de elementos en la lista se
define al crear el arreglo.
-
8/19/2019 Estructuras en Memoria
43/62
25-05-14Franco Guidi Polanco (PUCV-EII) 43
Inserción en lista basada en arreglos
20 813 12 3
0 1 2 3 4 5
(b)
23 20 813 12 3
0 1 2 3 4 5
(c)
0 1 2 3 4 5
Insertar 23
(a)
20 813 12 3
-
8/19/2019 Estructuras en Memoria
44/62
25-05-14Franco Guidi Polanco (PUCV-EII) 44
Comparación entre implementaciones de listas
! Las listas basadas en arreglos tienen la desventajade que su número de elementos debe serpredeterminado.
! Cuando estas listas tienen pocos elementos, se
desperdicia espacio.! Las listas enlazadas no tienen límite de número
máximo de elementos (mientras la memoria lopermita).
-
8/19/2019 Estructuras en Memoria
45/62
25-05-14Franco Guidi Polanco (PUCV-EII) 45
Comparación entre implementaciones de listas
! Las listas basadas en arreglos son más rápidas queaquellas basadas en listas enlazadas para elacceso aleatorio por posición.
! Las operaciones de inserción y eliminación son
más rápidas en las listas enlazadas.! En general, si el número de elementos que
contendrá una lista es muy variable o desconocido,es mejor usar listas enlazadas.
-
8/19/2019 Estructuras en Memoria
46/62
25-05-14Franco Guidi Polanco (PUCV-EII) 46
Uso de listas
! Supongamos las siguientes implementaciones de la lista:"
LList, implementa List mediante una listasimplemente enlazada
" AList, implementa List mediante un arreglo! Referenciamos la lista por medio de su interfaz:...
List lista = new LList(); // Implementación seleccionada
lista.insert( “Hola” );
lista.insert( “chao” );
lista.setFirst();
while( !lista.eol() ){
System.out.println( (Sring)lista.currValue());lista.next();
}
lista.setFirst();
String eliminado = (String) lista.remove()
...
-
8/19/2019 Estructuras en Memoria
47/62
25-05-14Franco Guidi Polanco (PUCV-EII) 47
Uso de listas (cont.)
! Si en el programa anterior ahora se desea utilizar otraimplementación de lista, sólo debe cambiarse la clase ainstanciar.
...
List lista = new AList(); // Implementación seleccionada
lista.insert( “Hola” );
lista.insert( “chao” );
lista.setFirst();
while( !lista.eol() ){
System.out.println( (Sring)lista.currValue());lista.next();
}
lista.setFirst();
String eliminado = (String) lista.remove()
...
-
8/19/2019 Estructuras en Memoria
48/62
25-05-14Franco Guidi Polanco (PUCV-EII) 48
Pilas
! Es un tipo restringido de lista, en donde loselementos sólo pueden ser insertados o removidosdesde un extremo, llamado top.
! Se le llama también Stack o Lista LIFO (Last In,First Out).
! La operación para insertar un nuevo elemento sedenomina push.
! La operación para remover un elemento se denominapop.
-
8/19/2019 Estructuras en Memoria
49/62
25-05-14Franco Guidi Polanco (PUCV-EII) 49
Interfaz para la Pila
public interface Stack {
public void clear(); // Remueve todos los objetos
public void push(Object it); // Agrega objeto al tope
public Object pop(); // Saca objeto del tope public Object topValue();// Retorna objeto en el tope
public boolean isEmpty(); // True: pila vacía
}
-
8/19/2019 Estructuras en Memoria
50/62
25-05-14Franco Guidi Polanco (PUCV-EII) 50
Ejemplo de uso de una pila
! pila.push(4):
4
!
pila.push(14):
4
14
! pila.push(1): ! pila.pop():
414
414
11
toptop
top
top(nuevo)
-
8/19/2019 Estructuras en Memoria
51/62
25-05-14Franco Guidi Polanco (PUCV-EII) 51
Implementación de una pila mediante listasimplemente enlazada
nulltop
nulltop
4
nulltop
14 4
nulltop4
pila.push(4)
pila.push(14)
pila.pop()
Se inserta y remuevesiempre el primer
elemento:
no se requiere nodo
fantasma
-
8/19/2019 Estructuras en Memoria
52/62
25-05-14Franco Guidi Polanco (PUCV-EII) 52
! En esta clase, por conveniencia, se usa unavariable top, que siempre está 1 posición másadelante del elemento “superior” de la pila.
Implementación de una pila mediante un arreglo
3 5 8 2
top=4
0 1 2 3 4 5
-
8/19/2019 Estructuras en Memoria
53/62
25-05-14Franco Guidi Polanco (PUCV-EII) 53
Ejercicio pilas
! Proponga implementaciones de la pila:" Basada en un arreglo" Basada en una lista simplemente enlazada
-
8/19/2019 Estructuras en Memoria
54/62
25-05-14Franco Guidi Polanco (PUCV-EII) 54
Colas
! Es un tipo restringido de lista, en donde loselementos sólo pueden ser agregados al final, yremovidos por el frente.
! Se le llama también Queue o Lista FIFO (First In,
First Out).! La operación para agregar un nuevo elemento sedenomina enqueue.
! La operación para remover un elemento se denominadequeue.
-
8/19/2019 Estructuras en Memoria
55/62
25-05-14Franco Guidi Polanco (PUCV-EII) 55
Interfaz para la Cola
public interface Queue {
public void clear(); // Remueve todos los objetos
public void enqueue(Object it);// Agrega obj. al final
public Object dequeue(); // Saca objeto del frente
public Object firstValue(); // Retorna obj. del frente public boolean isEmpty(); // Retorna V si cola vacía
}
-
8/19/2019 Estructuras en Memoria
56/62
25-05-14Franco Guidi Polanco (PUCV-EII) 56
Ejemplo de uso de una cola
!
cola.enqueue( 20 )cola=(20)
! cola.enqueue( 15 )
cola=(20, 15)
!
cola.enqueue( 40 )
cola=(20, 15, 40)
! cola.dequeue()
cola=(15, 40)
20
15
! cola.dequeue()
cola=(40)
-
8/19/2019 Estructuras en Memoria
57/62
25-05-14Franco Guidi Polanco (PUCV-EII) 57
Cola basada en lista simplemente enlazada
! Es conveniente mantener una referencia al últimoelemento de la cola (facilita operación enqueue).
nullfront
25 1 41
rear
-
8/19/2019 Estructuras en Memoria
58/62
25-05-14Franco Guidi Polanco (PUCV-EII) 58
Cola basada en arreglos (cont.)
!
Aproximación simple: almacenar los “n” elementos dela cola en las “n” primeras posiciones del arreglo.
3 5 8 2
rear=3
5 8 2
rear=2Sacar del frente:
Problema: lentitud de procedimiento dequeue (sacarprimer elemento).
-
8/19/2019 Estructuras en Memoria
59/62
25-05-14Franco Guidi Polanco (PUCV-EII) 59
Cola basada en arreglos (cont.)
!
Aproximación mejorada: al hacer dequeue, nodesplazar elementos, sino asumir que el frente de lacola se desplaza.
3 5 8 2
rear=3
5 8 2
rear=3
Sacar del frente:
front=0
front=1
Problema: Al sacar y agregar elementos, rear llega a la última
posición del arreglo y la cola no puede crecer, aun cuando existan
posiciones libres al comienzo.
-
8/19/2019 Estructuras en Memoria
60/62
25-05-14Franco Guidi Polanco (PUCV-EII) 60
Cola basada en arreglos* (cont.)
!
Arreglo circular: Pretender que el arreglo es “circular”, ypermitir que la cola continúe directamente de la últimaposición del arreglo a la primera.
0
1
2
34
5
6
7
3
5
8
2
front=0
rear=3
Función de avance
Dados:
• pos: posición actual
• size: tamaño arreglo
pos=(pos+1);if (pos>=size)
pos=0;
-
8/19/2019 Estructuras en Memoria
61/62
25-05-14Franco Guidi Polanco (PUCV-EII) 61
Cola basada en arreglos* (cont.)
! Problema de arreglo circular:" Si front es igual a rear, implica que hay 1 elemento." Luego, rear está una posición detrás de front implica que la cola
está vacía." Pero si la cola está llena, rear también está una posición detrás defront.
! Problema: ¿Cómo reconocer cuando una cola está vacía o llena?! Solución: Usar un arreglo de n posiciones, para almacenar como
máximo n-1 elementos.
-
8/19/2019 Estructuras en Memoria
62/62
Cola basada en arreglos* (cont.)
! Por conveniencia, se usa una variable front paraapuntar a la posición precedente al elementofrontal.
! La cola está vacía cuando front=rear.
! La cola está llena cuando rear está justo detrásde front, o sea cuando la función de avanceindica que de aumentar rear en 1, se llegaría a front.