PDF de programación - Soluciones Ejercicios Pilas y Colas

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



Ejercicio 1.- Extender la especificación PILA[ELEMENTO] del tipo pila visto en clase
añadiendo las siguientes operaciones (pueden ser parciales):

● contar: pila → natural, para ver cuántos elementos tiene la pila.

●

fondo: pila → elemento, que consulta el elemento más profundo de la pila.

● montar: pila pila → pila, para poner la segunda pila encima de la primera

(respetando el orden de los elementos).

● quitar: pila natural → pila, que quita tantos elementos de la pila como indica el
parámetro natural; por ejemplo, quitar(p, 3) eliminaría tres elementos de la pila.



Extendemos la especificación de las pilas de la siguiente manera:
espec EJ1_PILA[ELEMENTO]

{la especificación del ejercicio 1}

usa PILA[ELEMENTO]



{usamos la especificación base, no cambia ni el géneros ni el parámetro formal,
añadimos las nuevas operaciones en pseudocódigo}


operaciones

contar: pila → natural
fun contar (p:pila): natural

var n:natural n0

mientras !vacia?(p) hacer

Desapilar(p)

nn+1

fmientras

devolver n

ffun


parcial fondo: pila →elemento
fun fondo (p:pila):elemento
var e:elemento



si vacía?(p) entonces error(pila vacía)
mientras (no vacía?(p)) hacer



{la pila tiene que tener datos }

{al menos hay un elto en la pila}

ecima(p)
desapilar(p)

fmientras
devolver e



ffun

Jesús Lázaro
Mª José Domínguez

1

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



montar: pila pila → pila
proc montar ( p1, p2:pila)
var e:elemento



{recursivo}

si !vacia?(p2) entonces

ecima(p2)
desapilar(p2)
montar(p1, p2)
apilar (e, p1)

fsi

fproc

invertir:pilapila {visto en clase}
proc montar ( p1, p2:pila)
var pi:pila e:elemento
piinvertir(p2)

mientras ¡vacia?(pi) hacer



ecima(pi)
desapilar(pi)
apilar(e,p1)

{Iterativo}



fmientras


fproc

parcial quitar: pila natural → pila
{esta operación es parcial porque la pila tiene que tener como poco tantos elementos
como se quieren quitar}
proc quitar (p:pila, n:natural)

si (n>contar(p)) entonces error(no hay suficientes datos)
sino


mientras (n>0) hacer

desapilar(p)
nn-1

fmientras



fproc



fsi



Jesús Lázaro
Mª José Domínguez

2

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



Ejercicio 2.- (Examen del Grado en Ingeniería en Informática, Noviembre 2012)
Suponiendo conocida la especificación PILA[ELEMENTO], y suponiendo que el TAD
de elemento tiene una operación _≤_: elemento elemento → bool, que comprueba si un
elemento es menor o igual que otro, crear operaciones para:

● contar cuántos elementos hay en una pila.

● obtener la inversa de una pila.

● comprobar si los elementos de una pila fueron introducidos en orden de mayor a

menor (el mayor debería estar en el fondo de la pila, y el menor en la cima).

● comprobar si los elementos de una pila fueron introducidos en orden de menor a

mayor (el menor debería estar en el fondo de la pila, y el mayor en la cima).

● eliminar el elemento que se encuentre en el fondo de la pila.

{procedimiento auxiliar, invierte p2 en p1}


invertir_aux: pila pila pila

proc invertir_aux (p1, p2: pila)

si !vacia?(p2) entonces

apilar(cima(p2), p1))

desapilar(p2)

invertir_aux(p1, p2)



fsi



fproc



invertir:pilapila

fun invertir(p:pila):pila

Invertir_aux (pvacia, p)

ffun


parcial mayorquecima:elemento pilabool
{f. auxiliar que comprueba si la cima de la pila es mayor o igual que elto. Es parcial
porque la pila no puede ser vacia}
fun mayorquecima (e:elemento, p:pila) :bool
si e>= cima (p) entonces devolver T



fsi
ffun

sino devolver F



Jesús Lázaro
Mª José Domínguez

3

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



demayoramenor:pilaboolean
fun demayoramenor (p:pila):bool
var e1: elemento

si vacia(p) entonces Devolver T
sino e1cima(p)
desapilar(p)
si mayorquecima (e1, p) entonces



devolver demayoramenor(p)
sino devolver F



fsi


ffun


demenoramayor:pilaboolean
fun demenoramayor (p:pil): boolean

var pi:pila

piinvertir(p)
devolver demayoramenor(pi)

ffun

parcial eliminarfondo: pilapila
pila}
proc eliminarfondo (p:pila)
var pi:pila



{debe haber al menos un elemento en la

si vacia (p) entonces error(pila vacía)
sino



piinvertir(p)
desapilar(pi)
devolver invertir(pi)



fsi

ffun

Ejercicio 3.- (Examen del Grado en Ingeniería de Computadores, Noviembre 2012).
Dar la especificación del TAD básico PILA[ENTERO]. Extender dicha especificación
con operaciones adicionales para (pueden ser parciales):

● sacar_en_pos: pila natural → pila, que elimina el número entero que se encuentra
en la posición indicada por el parámetro natural, siendo la posición número uno
la cima; por ejemplo, sacar_en_pos(p,2) debería quitar el dato que está justo
debajo de la cima de p.

4

Jesús Lázaro
Mª José Domínguez

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



● sacar_entre: pila natural natural → pila, que elimina de la pila todos los enteros
que se encuentren entre las posiciones indicadas por los parámetros naturales; así,
sacar_entre(p, 2, 4) quitaría los elementos que están en las posiciones 2, 3 y 4.

espec entero


spec EJE3_PILA[ENTERO]
usa NATURAL2
parámetro formal

fparametro
generos pila
operaciones (vistas en clase)
pvacia:pilapila
apilar:pila enteropila
parcial desapilar.pilapila
parcial cima:pilaentero
vacia?:pilabooleano

operaciones que extienden la especificación
parcial sacar_en_pos: pila naturalpila
{Debe haber al menos n enteros en la pila}
proc sacar_en_pos (p:pila, n:natural)
var e:entero



fproc
parcial sacar_entre:pila natural naturalpila
proc sacar_entre (p:pila, n,m:natural)

si (n>0) entonces



fsi

si vacía?(p) entonces error(no hay suficientes datos)
sino



fsi

ecima(p)
desapilar(p)
sacar_en_pos(p, n-1)
si (n≠1) entonces apilar(e, p) fsi

si n=m entonces sacar_en_pos (p, n) {el posible error lo detecta sacar_en_pos}
si no si n<m entonces

sacar_en_pos (p,m)
sacar_entre(p, n, m-1)

fsi


fsi



fproc

5

Jesús Lázaro
Mª José Domínguez

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



Ejercicio 4.- (Examen del Grado en Ingeniería Informática, Noviembre 2011) Se
conoce el TAD CONJUNTO[ELEMENTO] para representar los datos conjunto de
elemento con las siguientes operaciones:

● Ø: → conjunto

●

insertar: elemento conjunto → conjunto

● borrar: elemento conjunto → conjunto

● ver_uno: conjuntoelemento

● está?: elemento conjunto→ bool

● vacio?: conjuntobool

así como la especificación necesaria para PILAS[CONJUNTO[ELEMENTO]] (las pilas
que están formadas por conjuntos). Añadir operaciones para:

● comprobar si un elemento está en todos los conjuntos de la pila.

● comprobar si todos los conjuntos de la pila tienen, al menos, los mismos

elementos que el conjunto de la cima.

● quitar un elemento de todos los conjuntos de la pila.

● crear un único conjunto con todos los elementos de los conjuntos de la pila.

● quitar todos los conjuntos vacíos de la pila.


{operaciones nuevas}

esta_en_todos: elemento pila_conjuntosbooleano
fun esta_en_todos (e:elemento, pc:pila_conjuntos):booleano

si vacia?(pc) entonces devolver T
sino si esta?(e, cima(pc)) entonces



desapilar(pc)
devolver esta_en_todos(e, pc)
sino devolver F

fsi

ffun



Jesús Lázaro
Mª José Domínguez

6

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



subconjunto:conjunto conjuntobooleano

{operación auxiliar que comprueba que todos los elementos de un conjunto están
en el otro}

fun subconjunto (c1,c2:conjunto):booleano
var e:elemento

si vacio (c1) entonces devolver T
sino ever_uno(c1)

si esta?(e, c2) entonces

borrar(e,c1)
devolver subconjunto (c1, c2)
sino devolver F



fsi

ffun

subconjunto_de_todos:conjunto pila_conjuntosbooleano

{operación auxiliar que comprueba que el conjunto dado es subconjunto de todos
los de la pila.}

fun subconjunto_de_todos (c:conjunto, pc:pila_conjuntos):booleano

si vacio(pc) entonces devolver T
sino si subconjunto(c, cima(pc)) entonces

desapilar(pc)
devolver subconjunto_de_todos (c, pc)
sino devolver F


fsi



ffun

parcial cima_es_subconjunto: pila_conjuntosbooleano

{la pila debe tener al menos un conjunto para acceder a cima}

c cima (pc)
desapilar(pc)
devolver subconjunto_de_todos(c, pc)

si vacía?(pc) entonces error(Pila vacía)
si no



fsi

fun cima_es_subconjunto (pc:pila_conjuntos):booleano
var c:conjunto



ffun



Jesús Lázaro
Mª José Domínguez

7

Universidad de Alcalá

Departamento de Ciencias de la Computación

Estructuras de Datos

Soluciones Ejercicios de Pilas y Colas



quitar_en_todos: elemento pila_conjuntospila_conjuntos
proc quitar_en_todos (e:elemento, pc:pila_conjuntos)
var cc:conjunto

si !vacia(pc) entonces

cccima(pc)
desapilar(pc)
quitar_en_todos(e, pc)
apilar(quitar (e, cc), pc)

fsi


fproc

unión: conjunto conjuntoconjunto
{función auxiliar qu