Estructura de Datos En C++
Dr. Romeo Sánchez Nigenda.
E-mail: [email protected]
http://yalma.fime.uanl.mx/~romeo/
Oficina: 1er. Piso del CIDET. Oficina con Dr. Oscar Chacón
Horas de Tutoría: 10am-11am Martes y Jueves,
3:30pm-4:30pm Miércoles, 2:00pm-4:00pm Viernes.
Website: http://yalma.fime.uanl.mx/~romeo/ED/2011/
Sesiones: 48
Objetivo General: Conocerá y manejará las
estructuras internas de información
Temario:
1.
2.
3.
4.
5.
6.
7.
8.
9.
Conceptos Básicos
La Pila
Colas
Recursión
Listas
Árboles
Ordenamiento
Búsqueda
Administración de Almacenamiento
Total a calificar: 110 puntos.
40% Tareas
30% Examen Parcial
30% Examen Final
10% Participación
Material de apoyo:
Estructura de Datos con C y C++.
Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Brooklyn College
Segunda Edición, Prentice-Hall.
Algorithms. Third Edition.
Parts 1-4, Fundamentals Data Structures Sorting Searching
Robert Sedgewick.
Estructura de Datos.
Román Martínez, Elda Quiroga.
Thomson Learning.
Cualquier libro de Estructura de Datos!
Software:
Compiladores GCC (GNU Compiler Collection)
IDEs (Integrated Development Environment):
http://www.eclipse.org/downloads/
http://kdevelop.org/
http://www.bloodshed.net/devcpp.html
3. La Cola (Queue)

Objetivo: El alumno conocerá la estructura denominada la
Cola o Fila, representación y aplicaciones.

Temario:
◦
◦
◦
◦
◦
Representación de Colas
Operaciones con Colas
Colas circulares
Doble cola
Aplicaciones de colas
La Cola (Queue)

Conjunto de elementos del que pueden suprimirse elementos
de un extremo (la parte delantera de la cola, front), y pueden
agregarse elementos en el otro extremo (la parte posterior de
la cola (rear)).
Agrega
Elimina
A
Front


B
C
D
E
Rear
Primer elemento insertado es el primero en suprimirse
(estructura FIFO, first in first out).
De manera genérica la cola necesita:
 Un TAD para almacenar sus elementos
 Un índice para indicar la posición del frente de la cola
 Un índice para indicar la parte posterior de la cola
Colas: Operaciones

Insertar (insert(q,i)): Agrega elemento i en la parte posterior de la cola q

Remover (remove(q)): Suprime el elemento delantero de la cola q, checando que la
cola no se encuentre vacía

Empty : (empty(q)) Retorna falso o verdadero dependiendo si la cola q está vacía o
no, el número de elementos está dado por q.rear-q.front+1
Insert(q,A)
Usando arreglos
Insert(q,B)
Insert(q,C)
Existe un problema, cuál es?
q.Elems
rear
Init
q.Front=0
q.Rear =-1
rear
front
Vacía = True
If q.rear<q.front
A
rear
B
front
A
front
C
rear
C
B
front
B
C
rear=front
A
Remove(q)
Remove(q)
Colas: Representación Básica
#define SIZEQ 100
struct ColaBasica{
int frente;
int cola;
int elementos[SIZEQ];
};
frente
cola
inicio
bool estaVacia(struct ColaBasica * C){
return (C->cola < C->frente);
}
Colas: Representación Básica
bool mueveCola(struct ColaBasica * C){
if(C->frente>0){
int j = 0;
for(int i=C->frente;i<=C->cola;i++){
C->elementos[j++] = C->elementos[i];
}
C->frente = 0;
C->cola=j-1;
return true;
Cola
}
return false;
}
Frente
Cola
Frente
Colas: Representación Básica
void insert(struct ColaBasica * C, int elem){
bool hayEspacio = true;
if(C->cola+1 > SIZEQ-1){
hayEspacio = mueveCola(C);
}
if(hayEspacio){
C->elementos[++C->cola]=elem;
}else{
cout<<"Elemento no se pudo insertar!"<<endl;
}
Cola
}
Cola
Frente
Frente
Colas: Representación Básica
int remove(struct ColaBasica * C){
if(!estaVacia(C)){
return (C->elementos[C->frente++]);
}else{
cout<<"Error cola vacia!"<<endl;
exit(1);
}
}
Cola
Cola
Frente
Frente
Colas Circulares usando Arreglos


Evitamos mover elementos is asumimos que la cola es circular, es decir,
que el primer elemento del arreglo está inmediatamente después del el
último elemento.
Se puede reservar un elemento en el arreglo para determinar si la cola
se encuentra vacía o no.
N
N=MAX +1
MAX
elementos
[1]
[0]

Frente
Se reserva un arreglo con un espacio más
bool estaVacia(struct ColaCircular q){
return q.frente % N == q.cola;
}
bool estaLlena(struct ColaCircular q){
return q.cola + 1== q.frente;
}
Cola
Utilizamos el tamaño de la cola para determinar cuando restablecer
nuestros apuntadores al índice 0, y así simular que la Cola es circular!
Colas Circulares usando Arreglos: Ejemplo
Insert(q,A)
Frente
MAX + 1
Insert(q,B)
Frente
MAX + 1
Insert(q,C)
MAX + 1
Cola
Frente
Cola
Insert(q,D)
MAX + 1
C
B
B
B
A
A
A
A
Remove(q)
Remove(q)
Remove(q)
Cola
MAX + 1
MAX + 1
B
D
C
C
B
Frente
Cola
MAX + 1
D
Frente
Cola
D
C
Cola
Frente
Remove(q)
Cola
Frente
MAX + 1
Cola
Frente
Colas Circulares usando Arreglos: Remoción
int remueveCola(ColaCircular * q) {
if (!estaVacia(q)) {
q->frente = q->frente%N;
1
return q->elementos[q->frente++];
2,3
} else {
cout << "Error, Cola vacía" << endl;
return ERROR;
}
}
Frente
MAX + 1
D
C
Cola
Remove(q)
Pasos básicos:
0) Verifica que no esté vacía
1) Determina la posición correcta de Frente
2) Guarda el elemento a retornar
3) Incrementa frente
B
3) Frente
A
2
Elemento removido: A
MAX + 1
Cola
D
C
B
1) Frente
Colas Circulares usando Arreglos: Inserción
void insertaCola(ColaCircular * q, int x) {
if (!estaLlena(q)) {
q->elementos[q->cola++] = x;
1, 2
q->cola = q->cola % N;
3
} else {
Cout << "Error, Cola llena" << endl;
return;
}
}
2) Cola
Insert(q,F)
MAX + 1
Cola
D
C
B
Frente
F
Pasos básicos:
0) Verifica que no esté llena
1) Inserta en la posición de cola
2) Incrementa el valor de cola
3) Determina la posición correcta de cola
b) Cola
1) Cola
D
C
B
Frente
3) Cola
Doble Cola: Bicola

Cola bidimensional en la que las inserciones y
eliminaciones se pueden realizar en cualquiera de los
dos extremos de la cola.
◦ Cola doble con entrada restringida: Acepta inserciones solo
al final de la cola
◦ Cola doble con salida restringida: Acepta eliminaciones solo
al inicio de la cola

A diferencia de una cola sencilla, debe haber dos
métodos para leer y dos para escribir para
considerar el frente y la parte posterior
 Podemos utilizar un contador para el número de elementos
Doble Cola: Operaciones
insertaAtras(q,A)
insertaAtras(q,B)
Cola
B
Cola
Inicio: Cola
A
Frente
insertaFrente(q,C)
Frente
insertaFrente(q,D)
A
insertaFrente(q,E)
B
Cola
B
A
B
A
C
A
C
D
Cola
C
Frente
D
Frente
Frente
E
Numelems = MAX
Cola llena!
Frente
Doble Cola: Operaciones
Numelems = MAX
B
RemueveFrente(q)
Cola
B
Cola
A
A
D
D
A
C
C
D
E
Frente
Copia
B
C
Frente
Frente
RemueveAtras(q)
Cola
B
Cola
A
A
D
D
C
Frente
C
Frente
Doble Cola: Operaciones
struct Bicola {
int nelems;
int frente;
int cola;
int elementos[MAXQUEUE];
};
int empty() { return items == 0; }
Bicola q;
q.nelems = 0;
q.frente = 0;
q.cola = 0;
Doble Cola: Operaciones
insertaAtras(q,B)
Cola
B
Cola
Frente
A
Frente
void insertaAtras(Bicola * q, int x){
if (q->nelems == MAXQUEUE){
cout<<"Error, cola llena"; exit(1);
}
q->elementos[q->cola] = x;
q->nelems ++;
q->cola ++;
}
A
Frente
Doble Cola: Operaciones
insertaFrente(q,C)
Cola
B
Cola
B
A
A
Frente
C
void insertaFrente(Bicola * q, int x){
if (q->nelems == MAXQUEUE){
cout<<"Error, cola llena"; exit(1);
}
mueveBicolaUp(q);
q->elementos[q->frente] = x;
q->nelems ++;
q->cola
}
++;
Frente
Doble Cola: Operaciones
Numelems = MAX
RemueveFrente(q)
B
Cola
B
Cola
A
A
B
D
D
A
C
C
D
E
Frente
int remueveFrente(Bicola * q){
int d;
if ( empty() ) return t_error;
q->nelems --;
q-> cola --;
d = q->elementos[q->frente];
mueveBicolaDown(q);
return d;
}
Frente
C
Frent
Doble Cola: Operaciones
RemueveAtras(q)
Cola
B
Cola
A
A
D
D
C
Frente
C
Frente
int remueveAtras(Bicola * q){
if ( empty() ) return t_error;
q->nelems --;
return q->elementos[-- q->cola];
}
Aplicaciones de Colas

En Ciencias Computacionales, Investigación de
Operaciones, y muchas otras áreas donde datos
son almacenados para ser procesados
posteriormente, ejecutando una función de
buffer (e.g., inventarios, threads, simulación,
manufactura, etc).
Descargar

Colas