Estructura de Datos

Pilas – Colas

Prof.: Mauricio Solar Prof.: Lorna Figueroa

Primer Semestre,
2010

Universidad Técnica Federico Santa María - Departamento de Informática

Indice

• TDA: Pilas
• TDA: Colas
• Colas de Prioridad
• Anillos
• BiColas
• BiColas Circulares

Universidad Técnica Federico Santa María - Departamento de Informática

Pilas - Stack

• Una de las estructuras de datos más primitivas y más antiguas en

la ciencia de los computadores.
• A pesar de ser tan simple, es esencial en los compiladores,
SS.OO., etc.
• Se pueden representar como una lista lineal que crece y decrece
por el mismo extremo.
• El último elemento que se incorpora a la estructura, es el
único que se puede consultar y eliminar.

LIFO
Entrada
Salida

trabajos
 Universidad Técnica Federico Santa María - Departamento de Informática

Pilas - Stack

• Es un tipo lineal de datos, secuencia de elementos de un tipo,

una estructura tipo LIFO (Last In First Out) último en entrar
primero en salir.
• Son un subconjunto de las listas, en donde las eliminaciones e
inserciones se realizan en un solo extremo.

LIFO
Entrada
Salida

trabajos

Universidad Técnica Federico Santa María - Departamento de Informática

Aplicaciones de las Pilas

Aplicaciones Directas:
• Histórico de páginas visitadas en un browser de web.
• Secuencia de “undo” en un editor de textos.
• Cadena de llamadas a métodos en JVM o medioambiente
runtime en C++
• Parsers en Compiladores (reconocedores sintácticos).
• SSOO.
• Convertir notación infija a posfija o prefija.
• Implementación de recursividad.

Aplicaciones Indirectas:
• Estructuras de datos auxiliares para algoritmos
• Componentes de otras estructuras de datos.

Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplo – Aplicación de las pilas

• Suponga que se quiere evaluar una expresión aritmética,

mediante un proceso que se basa en guardar dicha expresión en
dos pilas:
• una de operadores (+, -, * y /) y
• otra de operandos (números naturales).
 Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplo – Aplicación de las pilas

• El método consiste en seguir el siguiente proceso de forma

reiterada:
1. Si la pila de operadores está vacía, la cima de la de operandos
contiene el resultado final.
2. En caso contrario, tomar los dos operandos de la cima de la
pila y operarlos según el operador de la cima de la otra pila.
El resultado colocarlo en la cima de la pila de operandos.

* 4
- 2 - 8
3 3 5
+ 1 + 1 + 1 9
Iteración 1 Iteración 2 Iteración 3

Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Pilas

• Se definirá la semántica de las operaciones del TDA Pila en

términos de las operaciones del TDA Lista.

• Operaciones:
• CrearPilaVacía( P ) apilar desapilar
• PilaVacía( P ) → B tope
• Apilar( x, P )
• Desapilar( P )
• Tope( P ) → E

Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Pilas

•• CrearPilaVacía: Pila→→Pila
CrearPilaVacía:Pila Pila
•• CrearPilaVacía(P)
CrearPilaVacía(P)==CrearListaVacía(P)
CrearListaVacía(P)
•• Invocación:
Invocación:CrearPilaVacía(P)
CrearPilaVacía(P)

•• PilaVacía: Pila→→Lógico
PilaVacía:Pila Lógico
•• PilaVacía(P)
PilaVacía(P)==ListaVacía(P)
ListaVacía(P)
•• Invocación:
Invocación:PilaVacía(P)
PilaVacía(P)

•• Apilar:
Apilar:Elemento Pila→→Pila
ElementoxxPila Pila
•• Apilar(
Apilar(x,x,PP))==Insertar(
Insertar(x,x,Primera(P),
Primera(P),PP))
•• Invocación:
Invocación:Apilar(x,P)
Apilar(x,P)
 Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Pilas

•• Desapilar: Pila→→Pila
Desapilar:Pila Pila

Desapilar(
Desapilar(PP)){{
Si
Si(no
(noListaVacía(P))
ListaVacía(P))
Eliminar(
Eliminar(Primera(P),
Primera(P),PP))
sino
sinoError
Error
}}

•• Invocación:
Invocación:Despilar(P)
Despilar(P)

Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Pilas

•• Tope: Pila→→Elemento
Tope:Pila Elemento

Tope(
Tope(PP)) {{
Si
Si(no
(noListaVacía(P))
ListaVacía(P))
Retornar(
Retornar(Recuperar(Primera(P),
Recuperar(Primera(P),P)
P)))
Sino
Sino Error
Error
}}

•• Invocación:
Invocación:Tope(P)
Tope(P)

Universidad Técnica Federico Santa María - Departamento de Informática

Aplicaciones con TAD Pila

void
voidMostrarPila(Pila
MostrarPila(Pila P) P){{
Pila p1;
Pila p1;
CrearPilaVacia(
CrearPilaVacia(p1 p1))
PasarPila(
PasarPila(P,
P,p1
p1)) ////definirla
definirla
mientras
mientrasno
noPilaVacia(
PilaVacia(p1p1)){{
Imprimir(
Imprimir(Tope(p1)
Tope(p1)))
Apilar(
Apilar( Tope(p1),PP))
Tope(p1),
Desapilar(
Desapilar(p1p1))
}}
}}
 Universidad Técnica Federico Santa María - Departamento de Informática

Aplicaciones con TAD Pila

Pila
PilaPasarPila(
PasarPila(Pila
PilaOrigen
Origen)) {{
Pila
PilaDest;
Dest;
mientras
mientras(no
(noPilaVacia(
PilaVacia(Origen
Origen))))
Apilar(
Apilar(Tope(Origen),
Tope(Origen),Dest
Dest))
Desapilar(
Desapilar(Origen
Origen))
}}
return
returnDest;
Dest;
}}

Universidad Técnica Federico Santa María - Departamento de Informática

PILAS

• La representación gráfica de una pila es como la de cualquier

estructura dinámica:

tope

...

NULL

Universidad Técnica Federico Santa María - Departamento de Informática

PILAS – Implementaciones

typedef struct nodoP {

tElemento info;
struct nodoP* sig;
}

• Las pilas se implementan como una lista enlazada simple.

• El puntero de la lista (el tope) apunta al primer nodo de la
pila.

tope a1 a2 …. an

pila
 Universidad Técnica Federico Santa María - Departamento de Informática

PILAS – Implementaciones

boolean
booleanEstaVacia
EstaVacia(struct
(structnodoP*
nodoP*tope)
tope) {{
return (tope→
return(tope →sigsig====NULL);
NULL);
////Verdadero
Verdaderosisiestá
estávacía
vacía
}}

Universidad Técnica Federico Santa María - Departamento de Informática

PILAS – Implementaciones

void
voidPush
Push(tElemento
(tElementox,
x,struct
structnodoP*
nodoP*tope)
tope) {{
struct
structnodoP*
nodoP*q; q;
qq==(struct
(structnodoP*)
nodoP*)malloc
malloc(sizeof
(sizeof(struct
(structnodoP));
nodoP));
qq→→info
info==x;x; ////almacena
almacenaelelelemento
elemento
qq→→sigsig==tope;
tope; ////enlaza
enlazaalalnodo
nodoconconelelresto
resto
tope
tope==q;q; ////yylo
lopone
poneen enlalacabeza
cabeza
}}

Universidad Técnica Federico Santa María - Departamento de Informática

PILAS – Implementaciones

tElemento
tElementoPop Pop(struct
(structnodoP*
nodoP*tope)
tope) {{
struct
structnodoP*
nodoP*temp;
temp;
tElemento
tElementox; x;
ifif(EstaVacía(tope))
(EstaVacía(tope))
printf
printf(“Error:
(“Error:pila
pilavacía”);
vacía”);
else
else {{
tope→
xx==tope →info;
info;
temp
temp==tope;
tope; ////Se
Seeliminará
eliminaráeleltope
tope
tope tope→
tope==tope →sig;
sig;
free(temp);
free(temp);
return(x);
return(x);
}}
}}
 Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplo

1000 1

100 100 100 100 100

10 10 10 10 10 10

push(10) push(100) push(1000) pop() push(1) pop()

Universidad Técnica Federico Santa María - Departamento de Informática

Expresiones infijas, prefijas, postfijas

• Ejemplo de suma de dos operandos:

• Infija → A + B (operador va entre operandos )
• Prefija o polaca → + A B (operador va antes que
operandos)
• Postfija o polaca inversa → A B + (operador va después de
operandos)
• Solo existe una expresión prefija y una postfija para cada
expresión algebraica.
• Para evaluar estas expresiones se usan las pilas.

Universidad Técnica Federico Santa María - Departamento de Informática

Notación polaca inversa (postfija)

• Para evaluar la expresión aritmética: −b ± b − 4 ∗ a ∗ c

2

2∗a

• Se sigue el orden indicado por las flechas, (según prioridad

de operadores y uso de paréntesis).

(b + (b^2 – 4 * a * c) ^ 0.5) / (2 * a)

6 1 4 2 3 5 8 7
 Universidad Técnica Federico Santa María - Departamento de Informática

Notación polaca inversa (postfija)

• Para eliminar esta dificultad, se hace una traducción de las

expresiones aritméticas a notación postfija.

• Esta notación tiene la ventaja de que las operaciones

aparecen en el orden en que se efectúa realmente la
evaluación.

Universidad Técnica Federico Santa María - Departamento de Informática

Notación postfija

• La idea básica detrás de la notación de cadenas polacas es que

los operadores se escriben al final y no en medio de las
expresiones.
• A + B se escribe como A B +.
• En esta forma, el operador + se considera como una
instrucción para sumar los valores de las dos variables que
lo preceden inmediatamente. Ejemplo:

• La clave de la traducción de notación infija a posfija es la

prioridad de los operadores: ( ), + -, * /, ^

Universidad Técnica Federico Santa María - Departamento de Informática

Notación postfija

Reglas básicas para convertir expresiones infijas a posfijas:

1. Si el elemento es un ‘(‘ se coloca directamente en la pila de
operadores.
2. Si el elemento es un ‘)’, los operadores de la pila se transfieren
uno a uno, al extremo derecho de la expresión posfija hasta
llegar a un ‘(‘. Este se saca pero no va a la salida.
3. Si el elemento localizado es una variable, se coloca
inmediatamente en el extremo derecho de la expresión posfija
que se está creando.
4. Si el elemento es un operador y es de menor precedencia que
el operador en la pila, el operador de la pila se saca y va a la
salida, continuando de esta manera hasta encontrar un ‘(‘ o
hasta que el operador de la pila sea de menor precedencia.
Cuando esto ocurre, el operador en turno se apila.
 Universidad Técnica Federico Santa María - Departamento de Informática

Conversión infija a postfija

• Ecuación cuadrática −b ± b 2 − 4 ∗ a ∗ c
2∗a
• En notación infija:

( -b + ( b ^ 2 – 4 * a * c ) ^ ( 1 / 2 ) ) / ( 2 * a )

• En notación postfija:

-b b 2 ^ 4 a c * * – 1 2 / ^ + 2 a * /

Universidad Técnica Federico Santa María - Departamento de Informática

Algoritmo

1. Implementar la pila
2. Repetir hasta encontrar el fin de la expresión postfija
• Tomar un carácter.
• Si el carácter es un operando colocarlo en la pila.
• Si el carácter es un operador entonces sacar los dos
valores del tope de la pila (operando2 operando1), aplicar
el operador (operando1 operador operando2) y colocar el
resultado en el nuevo tope de la pila.

• Estructura de datos y organización de archivos. Mary

E. Loomis. Prentice Hall. 2a Ed.
www.itlp.edu.mx/publica/tutoriales/estru1/33.htm
thales.cica.es/rd/Recursos/rd99/ed99-0636-03/notacion_polaca.html

Universidad Técnica Federico Santa María - Departamento de Informática

Algoritmo para evaluar una expresión postfija

Para evaluar una expresión postfija con pilas:

i=1
Mientras i < Longitud(expresion)
si expresión[i] es operando
Insertar expresion[i] en la pila
sino {es operador}
Extraer dos elementos de la pila
operarlos según el operador,
insertar el resultado de nuevo en la pila
FinMientras
valor = cimaPila
 Universidad Técnica Federico Santa María - Departamento de Informática

Aplicación: Invertir una Pila

nodoP
nodoPInvPila(nodoP
InvPila(nodoP*tope)
*tope) {{

//// Función
Funciónque
queinvierte
invierteuna
unapila
pila
tElemento
tElementox;x;
nodoP
nodoP*tope1;
*tope1;
while(
while(!EstaVacia(tope)
!EstaVacia(tope))) {{
xx==Pop(tope);
Pop(tope);
Push(x,
Push(x,tope1);
tope1);
}}
return(tope1);
return(tope1);
}}

Universidad Técnica Federico Santa María - Departamento de Informática

Implementación en C

#include
#include<stdlib.h>
<stdlib.h>
#include
#include<stdio.h>
<stdio.h>

typedef
typedefstruct
structnodoP
nodoP{{
int
intvalor;
valor;
struct
structnodoP
nodoP*sig;
*sig;
}}tipoNodo;
tipoNodo;

typedef
typedeftipoNodo
tipoNodo*pNodo;
*pNodo;
typedef
typedeftipoNodo
tipoNodo*Pila;
*Pila;

////Prototipo
Prototipode
delas
lasfunciones
funciones
void
voidPush(Pila
Push(Pila*p,
*p,int
intx);
x);
int
intPop(Pila
Pop(Pila*p);
*p);

Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplo

• Algoritmo para encontrar el factorial de un número mediante

pilas

leer n;
mientras n > 1 {
push(n);
n = n-1;
}
factorial = 1;
mientras pila no está vacía
factorial = factorial * pop();
 Universidad Técnica Federico Santa María - Departamento de Informática

Ejercicios

1. Evaluar, indicando en cada paso el estado de la pila:

Pila p = (Pila *)malloc(sizeof(Pila));

a) Pop ( Pop ( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) )

b) EstaVacia(Pop(Pop(Push( 8,p))))

c) InvPila( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) ) )

2. Escribir una función que permita contar todos los elementos pares que
están en una pila dada.

Universidad Técnica Federico Santa María - Departamento de Informática

COLAS
COLAS

Universidad Técnica Federico Santa María - Departamento de Informática

Colas - queue
• Es una abstracción útil con muchos paralelismos en la vida
real: colas de espera en bancos, supermercados, etc
• Ello hace que su importancia sea crucial en simulaciones.
• Computacionalmente hay muchos casos en los que aparecen
colas de espera, por ejemplo:
• Procesos que esperan a ser ejecutados en sistemas
multitarea
• Procesos batch de cálculo intensivo
• Acceso a recursos compartidos (impresora)
 Universidad Técnica Federico Santa María - Departamento de Informática

Colas - queue

Aplicaciones Indirectas:

• Estructuras de datos auxiliares para algoritmos.

• Componentes de otras estructuras de datos.

Universidad Técnica Federico Santa María - Departamento de Informática

Colas

• Tipo de dato lineal con estructura FIFO (First In, First Out),
indica que el primer elemento que se incorporó a la estructura,
será el primero que salga, y el único que se puede consultar en
un momento dado.

entrada FIFO

trabajos

salida

Universidad Técnica Federico Santa María - Departamento de Informática

Colas

• Las colas son un subconjunto de las listas, en donde las

eliminaciones se dan al comienzo de la lista y las inserciones
al final.
• Los elementos se procesan en el orden como se reciben
(similar a la cola de impresión en redes).
• Cuando se desea accesar un elemento que no está en un
extremo, obligadamente se debe realizar una operación
desplazamiento de los nodos anteriores (o posteriores) a él.
entrada FIFO

trabajos

salida
 Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Cola

encolar
• CrearColaVacía( C )
final
• ColaVacía( C ) → B
• PonerEnCola( x, C )
• SacarDeCola( C )
frente
• Frente( C ) → E
desencolar

Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Cola

•• CrearColaVacía: Cola→→Cola
CrearColaVacía:Cola Cola
CrearColaVacía(C)
CrearColaVacía(C)==CrearListaVacía(C)
CrearListaVacía(C)
•• Invocación:
Invocación:CrearColaVacía(C)
CrearColaVacía(C)

•• ColaVacía: Cola→→Lógico
ColaVacía:Cola Lógico
ColaVacía(C)
ColaVacía(C)==ListaVacía(C)
ListaVacía(C)
•• Invocación:
Invocación:ColaVacía(C)
ColaVacía(C)

•• PonerEnCola:
PonerEnCola:Elemento Cola→→Cola
ElementoxxCola Cola
PonerEnCola(
PonerEnCola(x,x,CC))==Insertar(
Insertar(x,x,Fin(C),
Fin(C),CC))
•• Invocación:
Invocación:PonerEnCola(x,
PonerEnCola(x,C)
C)

Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Cola

•• SacarDeCola: Cola→→Cola
SacarDeCola:Cola Cola

SacarDeCola(
SacarDeCola(CC)){{
Si
Si(no
(noListaVacía(C))
ListaVacía(C))
Eliminar(
Eliminar(Primera(C),
Primera(C),CC))
sino
sinoError
Error
}}

•• Invocación:
Invocación:SacarDeCola
SacarDeCola(C)
(C)
 Universidad Técnica Federico Santa María - Departamento de Informática

Definición del TAD Cola

•• Frente: Cola→→Elemento
Frente:Cola Elemento

Frente(
Frente(CC)){{
Si
Si(no
(noListaVacía(C))
ListaVacía(C))
retornar(
retornar(Recuperar(Primera(C),
Recuperar(Primera(C),C)
C)))
Sino
Sino Error
Error
}}

•• Invocación:
Invocación:Frente(C)
Frente(C)

Universidad Técnica Federico Santa María - Departamento de Informática

Colas - Implementación

Estructura para los nodos: info sig

typedef struct TColas {

tElemento info;
struct tColas* sig;
}
Entrada de Dato
TColas *tCola;

Salida de Dato

Universidad Técnica Federico Santa María - Departamento de Informática

Colas

• Representación gráfica:

frente final

...

NULL

Por aquí se sale Por aquí entran

 Universidad Técnica Federico Santa María - Departamento de Informática

Colas

• Otra representación:

Universidad Técnica Federico Santa María - Departamento de Informática

Colas

• Se dispone de un puntero más.

• Cuando la cola está vacía se tiene la siguiente situación:

frente
final

NULL

Universidad Técnica Federico Santa María - Departamento de Informática

Colas
INSERTAR(dato;frente;final)
INSERTAR(dato;frente;final){{
p
Nuevo(p);
Nuevo(p);
p->info dato
p->info==dato;
dato;
ififfinal
final====NULL
NULL{{ final
frente
frente==p;p; ////1a
1a p 2a
final
final==p;p; ////2a
2a frente dato
3
}} 1a null

else
else{{ final
final->sig
final->sig==p;p; ////1b
1b p 2b
final
final==p;p; ////2b
2b dato
frente final 1b 3
}}
... null
p->sig
p->sig==null;
null; //// 33
}}
 Universidad Técnica Federico Santa María - Departamento de Informática

Colas

Algoritmo
AlgoritmoEliminar(frente)
Eliminar(frente)
{{
ififfrente
frente====NULL
NULL frente null
“cola
“colavacía”
vacía”

else
else {{
frente frente final
pp==frente;
frente; //// 11
3 2
frente
frente==frente->sig;
frente->sig; //// 22 ...
free(p);
free(p); //// 33 1
p null
}}
}}

Universidad Técnica Federico Santa María - Departamento de Informática

Colas - Implementación

boolean
booleanEstaVacía
EstaVacía(tCola
(tCola**frente,
**frente,tCola
tCola**final)
**final){{
//// Verificación de cola vacía
Verificación de cola vacía
ifif((*final
((*final==
==NULL)
NULL)&& &&((*frente
*frente==
==NULL))
NULL))
return(
return(true);
true); ////Verdadero
Verdaderosisiestá
estávacía
vacía
else
else
return
return(false);
(false);
}}

Universidad Técnica Federico Santa María - Departamento de Informática

Colas - Implementación

void
voidEnqueue
Enqueue(tCola
(tCola**frente
**frente,tCola
,tCola**final)
**final){{
tElemento
tElementodato;
dato;
printf("Ingrese
printf("Ingreseelemento
elemento");
"); scanf("%d",&dato);
scanf("%d",&dato);
if(
if(*frente
*frente==
==NULL)
NULL){{
*frente=(tCola *) malloc(sizeof(tCola));
*frente=(tCola *) malloc(sizeof(tCola));
(*frente)->info
(*frente)->info==dato;
dato; ////loslosparéntesis
paréntesisson
sonrequeridos
requeridospor
por
(*frente)->sig
(*frente)->sig==NULL;
NULL; ////precedencia
precedenciadedeoperandos
operandos
*final = *frente;
*final = *frente;
}}
else
else{{
tCola
tCola*q
*q==(tCola
(tCola*)
*)malloc
malloc(sizeof
(sizeof(tCola)
(tCola)););
q->info=
q->info=dato;
dato;
q->sig
q->sig==NULL;
NULL;
*final
*final==(*final)->sig
(*final)->sig==q;
q;
}}
}}
 Universidad Técnica Federico Santa María - Departamento de Informática

Colas - Implementación

tElemento
tElementoDequeue
Dequeue(TCola
(TCola**top,
**top,TCola
TCola**final)
**final){{
tCola
tCola*temp;
*temp;
ifif(EstaVacia(frente,final))
(EstaVacia(frente,final))
printf("Error
printf("Error(cola
(colavacia)");
vacia)");
else
else {{
tElemento
tElementox=(*frente)->info;
x=(*frente)->info;
temp
temp==*frente;
*frente;
*frente
*frente==(*frente)->
(*frente)->sig;
sig;
temp->sig=NULL;
temp->sig=NULL;
free(temp);
free(temp);
return(x);
return(x);
}}
}}

Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplo

a a

a b a b

a b c a b c

b c b c

No es necesario mover Apuntadores al frente

todos los elementos y al final

Universidad Técnica Federico Santa María - Departamento de Informática

Colas - Ejercicios

Escribir
Escribir unauna función
función que,
que, dada
dada una
una cola
cola que
que almacena
almacena números
números
enteros,
enteros,cuente
cuentelalacantidad
cantidadde
demúltiplos
múltiplosdede55que
quecontiene.
contiene.
Solución:
Solución:
int
intMul5EnCola(tCola**frente,
Mul5EnCola(tCola**frente,tCola**final)
tCola**final){{
////Contar
Contarlos losnúmeros
númerosmúltiplos
múltiplosde
de55almacenados
almacenadosen enlalacola
cola
int
intcont=0;
cont=0;
tCola
tCola*aux
*aux=*frente;
=*frente;
while
while(*aux!=
(*aux!=NULL)
NULL){{
int
inttemp
temp==Dequeue(aux,
Dequeue(aux,final);
final);
if(temp
if(temp% %55== ==0)
0)
cont++;
cont++;
}}
return(cont);
return(cont);
}}
 Universidad Técnica Federico Santa María - Departamento de Informática

Colas – Ejercicios

#include
#include<stdlib.h>
<stdlib.h>
#include
#include<stdio.h>
<stdio.h>
#include
#include<malloc.h>
<malloc.h>
struct
structtColas
tColas{{
int
intinfo;
info;
struct
structTColas*
TColas*sig;
sig;
};
};

typedef
typedefTColas
TColastCola;
tCola;

void
voidEnqueue(tCola
Enqueue(tCola**frente,
**frente,tCola
tCola**final);
**final);
int
intDequeue
Dequeue(tCola
(tCola**frente,
**frente,tCola
tCola**final);
**final);
int
intMultiplos5EnCola(tCola
Multiplos5EnCola(tCola**frente,
**frente,tCola
tCola**final);
**final);
int
intEstaVacia(tCola
EstaVacia(tCola**final,
**final,tCola
tCola**frente);
**frente);

Universidad Técnica Federico Santa María - Departamento de Informática

Colas – Ejercicios

void
voidmain()
main(){{
int
intm5,
m5,i,i,max;
max;
tCola
tCola*final
*final==NULL;
NULL;
tCola
tCola*frente
*frente==NULL;
NULL;

//// Ingresar
Ingresardatos
datosaalalacola
cola
printf("Cuantos
printf("Cuantosdatos
datosaaingresar?
ingresar?");
"); scanf("%d",&max);
scanf("%d",&max);
for(i=0;i < max; i++)
for(i=0;i < max; i++)
Enqueue(&frente,&final);
Enqueue(&frente,&final);
//// Buscar
Buscarlos
losmúltiplos
múltiplosde de55
m5=
m5=Multiplos5EnCola(&frente,
Multiplos5EnCola(&frente,&final);
&final);
printf("\n\nNumeros
printf("\n\nNumerosmultiplos
multiplosde
de5:
5:%d",m5);
%d",m5);
getch();
getch();
}}

Operaciones: Estado de la cola:

Inicio: Cola Vacía

1.-
1.- Insertar A A

2.-
2.- Insertar B A B

3.-
3.- Insertar C A B C

4.-
4.- Remover Elemento B C

5.-
5.- Insertar D
B C D

6.- Remover Elemento

C D
 Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas

• Colas de prioridad
• Anillos
• BiColas
• BiColas circulares

Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas: Colas de Prioridad

• Una cola de prioridad es una generalización de los conceptos de

pila y cola en la que, tras entrar en la cola, la salida de los
elementos no se basa necesariamente en el orden de llegada sino
que se basa en un orden definido entre ellos.

• 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.

Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas: Colas de Prioridad

• Los objetos se introducen de igual forma que en los casos

anteriores;
• La diferencia aparece en el caso de la extracción y en la consulta
del siguiente objeto a extraer.
• El elemento que se saca es el menor de los que se han
introducido según la relación de orden total.
• Si hay varios elementos menores, con el mismo valor, el que
se saca es aquél que se introdujo primero.
 Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas: Colas de Prioridad

• Existen dos 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.
cp

dato1 pr1 dato2 pr2 ... daton prn

typedef struct {
// Informacion
// Prioridad
Cola *sgte;
} Cola_Prioridad;

Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas: Colas de Prioridad

2. Crear tantas colas como prioridades haya, y almacenar cada

elemento en su cola.
Frente Final
prim
P1 I11 I12 I13

P2 I21

P3

ult
P4 I41 I42

Universidad Técnica Federico Santa María - Departamento de Informática

Algunas aplicaciones de las colas de prioridad

• Gestión de procesos en un SO. Los procesos no se ejecutan

uno tras otro en base a su orden de llegada. Algunos procesos
deben tener prioridad (por su mayor importancia, por su
menor duración, etc.) sobre otros.
• Implementación de algoritmos voraces, proporcionan
soluciones globales a problemas basándose en decisiones
tomadas sólo con información local. La determinación de la
mejor opción local suele basarse en una cola de prioridad.
• Algunos algoritmos sobre grafos, como la obtención de
caminos o árboles de expansión de costo mínimo, son
ejemplos representativos.
 Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplos del uso TDA Cola Prioridad

Convertir una expresión aritmética infija en postfija:

Dada una expresión aritmética E formada por números y los
operadores: +, -, *, / expresada en formato infijo, transformarla a
formato postfijo.

Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplos del uso TDA Cola Prioridad

Cola
ColaConvertir(
Convertir(Cola
ColaInfija
Infija)) {{
Cola
ColaPost;
Post; Pila
PilaP;
P; Elem
Elemtoken;
token;
CrearPilaVacia(
CrearPilaVacia(PP););
CrearColaVacia(
CrearColaVacia(PostPost););
CrearElem(
CrearElem(token
token););
REPETIR
REPETIR
Asignar(token,
Asignar(token,Frente(Infija)),
Frente(Infija)),
SacarDeCola(
SacarDeCola(Infija
Infija););
Si
SiOperando(
Operando(token
token))
PonerEnCola(
PonerEnCola(token,
token,Post
Post););
Sino
Sino
Si
Si(no
(noPilaVacia(P))
PilaVacia(P))&& && (Prioridad(token)
(Prioridad(token)<=
<=Prioridad(Tope(P)))
Prioridad(Tope(P))){{
PonerEnCola(
PonerEnCola(Tope(P),
Tope(P),Post
Post))
Desapilar(
Desapilar(PP))
}}

Universidad Técnica Federico Santa María - Departamento de Informática

Ejemplos del uso TDA Cola Prioridad

Apilar(
Apilar(token,
token,PP););
}}
HASTA
HASTAColaVacia(
ColaVacia(Infija
Infija))
mientras
mientras(no
(noPilaVacia(P))
PilaVacia(P))
PonerEnCola(
PonerEnCola(Tope(P),
Tope(P),Post
Post););
Desapilar(
Desapilar(PP););
}}
return
returnPost;
Post;
}}

Estructuras de datos y algoritmos - 2007 - Clase 3

Mg. Sergio Alejandro Gómez
 Universidad Técnica Federico Santa María - Departamento de Informática

Anillos – Cola circular

• Las colas lineales tienen un grave problema:

• como las extracciones sólo pueden realizarse por un
extremo, puede llegar un momento en que el apuntador A
sea igual al máximo número de elementos en la cola, siendo
que al frente de la misma existan lugares vacíos, y al insertar
un nuevo elemento nos mandará un error de overflow (cola
llena).

• Para solucionar el problema de desperdicio de memoria se

implementaron las colas circulares, en las cuales existe un
apuntador desde el último elemento al primero de la cola.

Universidad Técnica Federico Santa María - Departamento de Informática

Anillos – Cola circular

• Es una secuencia de elementos dispuestos de forma circular.

• Los elementos pueden añadirse y eliminarse desde un único
punto llamado cabeza del anillo.
• El círculo de elementos se puede rotar en ambos sentidos, de
manera que los diferentes elementos van pasando por la cabeza
del anillo.
• Un anillo es, pues, una estructura en la que todo elemento tiene
un sucesor y un predecesor, y hay una posición distinguida
llamada cabeza del anillo.

Universidad Técnica Federico Santa María - Departamento de Informática

Anillos – Cola circular

• Estructuras con características parecidas se presentan a distintos

niveles:
• redes de computadores con configuraciones de anillo y
comunicación mediante paso de mensajes
• las interfaces de usuario, en los intérpretes de comandos,
que suelen utilizar un buffer de entrada estructurado como
un anillo de líneas que se puede recorrer para recuperar
líneas introducidas con anterioridad.
 Universidad Técnica Federico Santa María - Departamento de Informática

Implementación en C – Anillos

• Declaración:
struct tcola {
int clave;
struct tcola *sig;
};
• Creación:
void crear(struct tcola **cola) {
*cola = NULL;
}

• Función que devuelve verdadero si la cola está vacía:

int vacia(struct tcola *cola) {
return (cola == NULL);
}

Universidad Técnica Federico Santa María - Departamento de Informática

Implementación en C – Anillos

• Poner_En_Cola:
void encolar(struct tcola **cola, int elem) {
struct tcola *nuevo;
nuevo = (struct tcola *) malloc(sizeof(struct tcola));
nuevo->clave = elem;
if (*cola == NULL)
nuevo->sig = nuevo;
else {
nuevo->sig = (*cola)->sig;
(*cola)->sig = nuevo;
}
(*cola) = nuevo;
}

Universidad Técnica Federico Santa María - Departamento de Informática

Implementación en C – Anillos

• Sacar_De_Cola:
void desencolar(struct tcola **c1, int *elem) {
struct tcola *aux;
*elem = (*c1)->sig->clave;
if ((*c1) == (*c1)->sig) {
free(*c1);
*c1 = NULL;
}
else {
aux = (*c1)->sig;
(*c1)->sig = aux->sig;
free(aux);
}
}
 Universidad Técnica Federico Santa María - Departamento de Informática

Implementación en C – Anillos

• Programa de prueba:
#include <stdio.h>
#include <stdlib.h>
int main(void) {
struct tcola *cola;
int elem;
crear(&cola);
if (vacia(cola))
printf("\nCola vacia!");
encolar(&cola, 100);
desencolar(&cola, &elem);
return 0;
}

Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas – BiColas

• Colas en donde los nodos se pueden insertar y eliminar por

ambos extremos;
• Se les llama DEQUE (Double Ended QUEue).

Universidad Técnica Federico Santa María - Departamento de Informática

TAD BiCola

• Las operaciones son las mismas que la del TAD Cola, salvo que
Primero, Insertar y Eliminar son sustituidas por 2 operaciones
respectivamente:
• PrimeroIzquierda: TipoDeque Æ TipoElemento
• PrimeroDerecha: TipoDeque Æ TipoElemento
• InsertarIzquierda: TipoElementox TipoDeque Æ TipoDeque
• InsertarDerecha: TipoElemento x TipoDeque Æ TipoDeque
• EliminarIzquierda: TipoDeque Æ TipoDeque
• EliminarIzquierda: TipoDeque Æ TipoDeque
 Universidad Técnica Federico Santa María - Departamento de Informática

Tipos de colas – BiColas

• Existen dos variantes:

• Bicolas de entrada restringida: Son aquellas donde la

inserción sólo se hace por el final, aunque se puede
eliminar al principio o al final.
• Bicolas de salida restringida: Son aquellas donde sólo se
elimina por el final, aunque se puede insertar al principio y
al final.

Universidad Técnica Federico Santa María - Departamento de Informática

BiColas circulares
• Permite la implementación eficiente de todas las operaciones
del anillo normal, y de la cola doble.
• p puede apuntar ahora sin problemas a la cabeza del anillo, ya
que se puede acceder sin problemas y de forma directa al
último elemento.

Universidad Técnica Federico Santa María - Departamento de Informática

BiColas circulares

• Las rotaciones tanto a derecha como a izquierda no suponen

tampoco complicación alguna, ya que se tienen punteros en
ambas direcciones.
 Universidad Técnica Federico Santa María - Departamento de Informática

Bibliografía - Webgrafía

• Abstracción de datos
1. http://www14.uniovi.es/tutorED/abstraccion/abstraccionfr.html
• Estructura de Datos
2. http://www14.uniovi.es/tutorED/estlineales/estlineafr.html
3. http://www14.uniovi.es/tutorED/java-c++/java-c++fr.html
4. Como programar en Java. Deitel y Deitel.
• Listas
5. http://www14.uniovi.es/tutorED/estlineales/interlistafr.htm
• 6. http://oviedo3.ccu.uniovi.es/martin/EDI/ListPage.htm

Universidad Técnica Federico Santa María - Departamento de Informática

Bibliografía - Webgrafía

• Listas, pilas y colas. Ejercicios

7. Fundamentos de programación. Libro de problemas. Luis
Joyanes Aguilar
8. http://old.algoritmia.net/listas.htm
9. Estructura de datos y organización de archivos. Mary E.
Loomis. Prentice Hall. 2a Ed.
10. Pilas y Colas. Cursos Propedéuticos 2006, Programación y
Estructuras de Datos. Manuel Montes, Claudia Feregrino.