Programacion
a
Ingenier´ en Inform´tica de Gesti´n
ıa
a
o
Estructuras de Datos y de la Informaci´n
o
Grupos A y B, Marzo 2003
Ejercicios sobre colas
Ejercicio 1 A˜adir altipo abstracto de las colas:
n
• Una operaci´n que calcule el ultimo elemento de una cola.
o
´
• Una operaci´n que produzca la inversa de una cola.
o
• Una operaci´n que concatene dos colas, esdecir, que coloque los elementos de
o
una al final de la otra.
• Una operaci´n que intercale los elementos de dos colas.
o
Dise˜ar m´todos que implementen las nuevas operaciones usando larepresentaci´n
n
e
o
din´mica de las colas.
a
Ejercicio 2 Implementar el tipo abstracto de las colas utilizando como tipo representante
un par de pilas.
Ejercicio 3 Implementar el tipo abstracto de laspilas utilizando como tipo representante
un par de colas.
Ejercicio 4 Una cola doble o deque (double-ended queue) es un tipo de datos lineal que
permite consultar, a˜adir y eliminar elementos encualquiera de los dos extremos de
n
la cola. Se pide:
• Especificar algebraicamente las colas dobles.
• Implementar las colas dobles usando vectores circulares.
• Implementar las colas dobles usandolistas doblemente enlazadas.
Ejercicio 5 Dise˜ar dos algoritmos que decidan si una frase dada como una cola de
n
caracteres es pal´
ındroma utilizando como estructuras auxiliares:
• Una pila yuna cola.
• Una cola doble.
Ejercicio 6 Una cola medieval se comporta como una cola ordinaria, con la unica dife´
rencia de que los elementos almacenados en ella se dividen en dos estamentos: noblesy plebeyos. Dentro de cada estamento, los elementos deben ser atendidos en orden
de llegada; pero siempre que haya nobles en la cola, ´stos deben ser atendidos antes
e
que los plebeyos. Se pide:• Especificar un tipo abstracto de datos para las colas medievales que disponga
al menos de operaciones para:
1
–
–
–
–
–
–
–
crear una cola medieval vac´
ıa,
a˜adir un elemento...
Regístrate para leer el documento completo.