ECTS ECTS

eees
Estructuras de Datos

eees
2ª Edición
y Métodos Algorítmicos
213 Ejercicios resueltos
2ª Edición
ects ects

y Métodos Algorítmicos
Estructuras de Datos
E
ste libro intenta llenar un hueco en el panorama editorial de-
EEES EEES
ECTS
dicado a libros académicos en el campo de la Informática. Si

ECTS
bien existen varios libros “de teoría” dedicados a algoritmos
o estructuras de datos (muchos de ellos traducciones de originales
en inglés), la cantidad de libros “de problemas (resueltos)” sobre

eees
estos temas es muy escasa.

eees
El libro se divide en dos partes: la primera se dedica a las estruc-
turas de datos (pilas, colas, listas, árboles binarios y generales,
árboles de búsqueda y tablas, colas con prioridad y grafos) y la

ects
segunda a los métodos algorítmicos (divide y vencerás, método

ects
voraz, programación dinámica, vuelta atrás y ramificación y poda),
si bien es imposible separar por completo ambas materias, y esto
se nota en algunos de los ejercicios que se incluyen. Cada capítu-

EEES
lo empieza con una breve introducción al tema correspondiente,
donde se fijan los conceptos y notaciones que se utilizan en el

EEES Estructuras de Datos

desarrollo posterior de las soluciones de los ejercicios. A continua-
ción aparecen los enunciados de los ejercicios del tema, cada

Y. Ortega Mallén
uno seguido de la solución correspondiente. En general, la solu-

ECTS
ción que se ofrece no es la única posible en absoluto y, de hecho,

N. Martí Oliet
ECTS y Métodos Algorítmicos
en algunos ejercicios se presenta más de una solución cuando la

A. Verdejo
variación es suficientemente interesante.

eees
Tras el éxito de la primera edición de 2003, se publica ahora esta
segunda edición en la que se han corregido todas las erratas co-

eees 213 Ejercicios resueltos

nocidas hasta la fecha y se han mejorado las explicaciones aten-
diendo a las críticas constructivas recibidas a lo largo de los años.
A pesar de todos los cambios que ha supuesto en las asignaturas

ects
y titulaciones la implantación de los grados, el contenido del libro

ects
continúa siendo fundamental en la formación de los graduados en
diferentes titulaciones relacionadas con la Informática.
2ª Edición

EEES Narciso Martí Oliet

ECTS
www.garceta.es
Yolanda Ortega Mallén
Alberto Verdejo
 3
Pilas
[\

3.1. Introducción
En la vida cotidiana suele ocurrir que las tareas se nos acumulan de forma que siempre nos dedicamos a
la tarea más reciente, dejando aplazadas las más antiguas, es decir, siguiendo el criterio de el último en entrar
es el primero en salir.
En este capítulo vamos a considerar una estructura de datos lineal cuya característica principal es que el
acceso a los elementos se realiza en orden inverso al de su almacenamiento. Aunque se las puede denominar
estructuras LIFO (Last In, First Out en inglés), el nombre más usual, que es el que vamos a utilizar, es pilas. El
comportamiento de las pilas es totalmente independiente del tipo de los datos almacenados en ellas, por lo
que se trata de un tipo de datos parametrizado.
La ventaja de las pilas es que el acceso a la estructura, tanto para su modificación (inserción y borrado) co-
mo para la consulta de los datos almacenados, se realiza en un único punto (la cima de la pila), lo que facilita
implementaciones sencillas y eficientes. A pesar de su sencillez, es una estructura con múltiples aplicaciones
en el diseño de algoritmos, como la evaluación de expresiones o la implementación de la recursión.

3.2. Ejercicios resueltos

3.1. Especificar un TAD para describir las pilas con elementos pertenecientes a un tipo dado como pará-
metro, con las siguientes operaciones:
crear la pila vacía,
apilar un elemento,
desapilar el elemento en la cima,
consultar el elemento en la cima, y
determinar si la pila es vacía.
72 Estructuras de datos y métodos algorítmicos

Solución

Como ya se ha comentado en la introducción, el comportamiento de una pila es independiente

del tipo de los datos almacenados en ella. Ello significa que no se requiere ninguna característica
especial para el tipo parámetro, por lo que consideraremos el parámetro más simple, ELEM, definido
en la sección 1.1.5.
La elección de constructoras no ofrece muchas alternativas: para obtener una pila se parte de una
estructura vacía (pila-vacía) y se van apilando los elementos (apilar). Como el orden de apilación es
fundamental para la posterior consulta y eliminación, las constructoras son libres.
El comportamiento de las otras tres operaciones (una modificadora y dos observadoras) viene
dado mediante la distinción de casos de las dos constructoras. Las operaciones de consulta y elimi-
nación del elemento en la cima de una pila solo tienen sentido si la pila no es vacía, por lo que ambas
operaciones son parciales. Las ecuaciones correspondientes simplemente reflejan el comportamiento
LIFO de una pila: la cima corresponde al último elemento apilado. Entonces, en el caso no vacío,
cima y desapilar son las “destructoras” asociadas a la constructora apilar.

especificación PILAS[ELEM]
usa BOOLEANOS
tipos pila
operaciones
pila-vacía : −→ pila { constructora }
apilar : elemento pila −→ pila { constructora }
desapilar : pila −→ p pila
cima : pila −→ p elemento
es-pila-vacía? : pila −→ bool
variables
e : elemento
p : pila
ecuaciones
desapilar(pila-vacía) = error
desapilar(apilar(e, p)) = p

cima(pila-vacía) = error
cima(apilar(e, p)) = e
es-pila-vacía?(pila-vacía) = cierto
es-pila-vacía?(apilar(e, p)) = falso
fespecificación

3.2. Extender la especificación de las pilas del ejercicio 3.1 con las siguientes operaciones:
calcular el número de elementos en una pila (profundidad),
consultar el elemento del fondo de una pila,
obtener la inversa de una pila,
duplicar una pila p, de forma que cada elemento de p aparezca apilado dos veces seguidas,
conservando el mismo orden relativo que en p,
concatenar dos pilas, colocando los elementos de la segunda sobre los de la primera, y
entremezclar dos pilas, donde la pila resultante se obtiene apilando alternativamente los ele-
mentos de las pilas argumento, empezando por el fondo de la primera pila.
 Pilas 73

Solución

De forma similar a la operación cima (véase el ejercicio 3.1), la consulta del elemento en el fondo
de una pila solamente tiene sentido si la pila no es vacía, por lo que esta operación es parcial.
La especificación del comportamiento de todas estas nuevas operaciones se hace, en general, por
distinción de casos sobre las dos constructoras de las pilas (pila-vacía y apilar), pero para facilitar la
especificación de inversa, utilizaremos una operación auxiliar apilar-inversa con dos argumentos de
tipo pila, que coloca la inversa de la primera sobre la segunda.

especificación PILAS+[ELEM]
usa PILAS[ELEM], NATURALES
operaciones
profundidad : pila −→ nat
fondo : pila −→ p elemento
inversa : pila −→ pila
duplicar : pila −→ pila
concatenar : pila pila −→ pila
entremezclar : pila pila −→ pila
operaciones privadas
apilar-inversa : pila pila −→ pila
variables
e, f : elemento
p, q : pila

La profundidad de una pila vacía es cero; cada vez que se apila un elemento, la profundidad de
la pila se incrementa en uno.

ecuaciones
profundidad(pila-vacía) = 0
profundidad(apilar(e, p)) = 1 + profundidad(p)

El acceso a la cima de la pila es directo, de ahí la sencillez de las ecuaciones dadas en la especi-
ficación de las pilas para cima y desapilar (ejercicio 3.1); pero para poder acceder al fondo de la pila
hay que “avanzar” a través de los elementos apilados hasta alcanzar el primero que se apiló. Por eso
se distinguen dos casos cuando la pila no es vacía: si hay solo un elemento o hay más de uno.

fondo(pila-vacía) = error
fondo(apilar(e, p)) = e ⇐ es-pila-vacía?(p)
fondo(apilar(e, p)) = fondo(p) ⇐ ¬es-pila-vacía?(p)

Para apilar la inversa de una pila sobre otra, basta con ir desapilando los elementos en la cima
de la primera y apilarlos sobre la segunda.

apilar-inversa(pila-vacía, p) = p
apilar-inversa(apilar(e, p), q) = apilar-inversa(p, apilar(e, q))

Entonces, para invertir una pila, nos limitamos a apilar su inversa sobre una pila vacía.

inversa(p) = apilar-inversa(p, pila-vacía)

Para duplicar los contenidos de una pila, basta apilar dos veces la cima de la pila sobre el resto
de la pila, el cual ha sido previamente duplicado.
74 Estructuras de datos y métodos algorítmicos

5 8 0 3 ... contenido

índice-cima

Figura 3.1: Representación estática de una pila.

duplicar(pila-vacía) = pila-vacía
duplicar(apilar(e, p)) = apilar(e, apilar(e, duplicar(p)))

Para especificar la concatenación, distinguimos casos sobre la segunda pila a concatenar: si es

vacía, nos quedamos con la primera pila, pero si no lo es, tendremos que apilar la cima de la segunda
pila sobre la concatenación de toda la primera pila con el resto de la segunda.

concatenar(p, pila-vacía) = p
concatenar(p, apilar(e, q)) = apilar(e, concatenar(p, q))

Una opción alternativa es colocar sobre la primera pila la inversa de la segunda pila invertida,
utilizando las operaciones apilar-inversa e inversa (nótese el cambio en el orden de los argumentos).

concatenar(p, q) = apilar-inversa(inversa(q), p)

Para entremezclar dos pilas, hay que comparar su profundidad, pues el último elemento a apilar
será el de la cima de la pila con mayor profundidad y, en el caso de que ambas sean igual de
profundas, corresponderá a la cima de la segunda pila.

entremezclar(pila-vacía, pila-vacía) = pila-vacía

entremezclar(apilar(e, p), q) = apilar(e, entremezclar(p, q))
⇐ profundidad(p) + 1 > profundidad(q)
entremezclar(p, apilar(e, q)) = apilar(e, entremezclar(p, q))
⇐ profundidad(p) ≤ profundidad(q) + 1
fespecificación

3.3. Diseñar una representación estática del TAD de las pilas utilizando vectores e implementar las ope-
raciones especificadas en el ejercicio 3.1.

Solución

La idea es utilizar un vector contenido donde vamos colocando los elementos de la pila, de izquier-
da a derecha según se van apilando, y un índice que apuntará a la cima, como muestra gráficamente
la figura 3.1, en la cual se representa la pila de naturales

apilar(3, apilar(0, apilar(8, apilar(5, pila-vacía))))

Por tanto, el tipo representante es el siguiente:

 Pilas 75

tipos
pila = reg
contenido[1..N ] de elemento
índice-cima : 0..N
freg
ftipos

Cuando la pila esté vacía, índice-cima tendrá el valor cero.

Como ya se comentó en la sección 2.1, estas representaciones sobre memoria estática tienen el
inconveniente de que el tamaño de la estructura queda restringido por la capacidad del soporte de
almacenamiento, en este caso, por el tamaño del vector contenido. De esta forma, la operación de
apilar resulta ser parcial, produciéndose un error cuando se intenta rebasar dicha capacidad.
La implementación de las operaciones es la siguiente:

fun pila-vacía() dev p : pila { Θ(1) }

p.índice-cima := 0
ffun
proc apilar(e e : elemento, p : pila) { Θ(1) }
si p.índice-cima = N entonces error(Espacio insuficiente)
si no
p.índice-cima := p.índice-cima + 1
p.contenido[p.índice-cima] := e
fsi
fproc
proc desapilar(p : pila) { Θ(1) }
si p.índice-cima = 0 entonces error(Pila vacía)
si no p.índice-cima := p.índice-cima − 1
fsi
fproc
fun cima(p : pila) dev e : elemento { Θ(1) }
si p.índice-cima = 0 entonces error(Pila vacía)
si no e := p.contenido[p.índice-cima]
fsi
ffun
fun es-pila-vacía?(p : pila) dev b : bool { Θ(1) }
b := (p.índice-cima = 0)
ffun

3.4. Implementar dos pilas sobre un mismo vector, de forma que el desbordamiento de cualquiera de las
pilas solo se produzca en el caso de que el vector esté completamente ocupado.

Solución

A partir de la representación estática mediante un vector y un índice (véase el ejercicio 3.3),

la idea es utilizar el mismo vector de almacenamiento para las dos pilas, de forma que una va
76 Estructuras de datos y métodos algorítmicos

P1 P2

... contenido

cima1 cima2

Figura 3.2: Dos pilas en un vector.

avanzando desde el extremo izquierdo, mientras que la otra lo hace desde el extremo derecho, como
ilustra el gráfico de la figura 3.2. De esta forma, el soporte estará completamente lleno cuando los
dos índices tengan valores consecutivos.
Así pues, el tipo representante es el siguiente:

tipos
doble-pila = reg
contenido[1..N ] de elemento
índice-cima[1..2] de 0..N + 1
freg
ftipos

Inicialmente ambas pilas están vacías; el índice a la cima de la primera estará más allá del extre-
mo izquierdo (0), mientras que el índice a la cima de la segunda estará más allá del extremo derecho
(N + 1).

fun doble-pila-vacía() dev p : doble-pila

p.índice-cima[1] := 0
p.índice-cima[2] := N + 1
ffun

A la hora de apilar un nuevo elemento, la cima se desplaza una posición: hacia la derecha en el
caso de la primera pila (+1) y hacia la izquierda en el caso de la segunda pila (−1). En cambio, para
desapilar, el desplazamiento de la cima se realiza en el sentido contrario: hacia la izquierda en el
caso de la primera pila (−1) y hacia la derecha en el caso de la segunda pila (+1). Evitamos el uso
de una instrucción condicional mediante la exponenciación del valor −1: (−1)1 = −1 y (−1)2 = +1.
En los cuatro algoritmos que siguen, el argumento i de tipo 1..2 indica sobre cuál de las dos pilas
tiene lugar la acción correspondiente.

proc doble-apilar(e e : elemento, p : doble-pila, e i : 1..2) { Θ(1) }

si p.índice-cima[1] + 1 = p.índice-cima[2] entonces error(Espacio insuficiente)
si no p.índice-cima[i] := p.índice-cima[i] − exp(−1, i)
p.contenido[p.índice-cima[i]] := e
fsi
fproc
proc doble-desapilar(p : doble-pila, e i : 1..2) { Θ(1) }
si doble-es-pila-vacía?(p, i) entonces error(Pila vacía)
si no p.índice-cima[i] := p.índice-cima[i] + exp(−1, i)
fsi
fproc
 Pilas 77

sig sig sig

p 3 2 −5

Figura 3.3: Estructura enlazada para una pila.

fun doble-cima(p : doble-pila, i : 1..2) dev e : elemento { Θ(1) }

si doble-es-pila-vacía?(p, i) entonces error(Pila vacía)
si no e := p.contenido[p.índice-cima[i]]
fsi
ffun
fun doble-es-pila-vacía?(p : doble-pila, i : 1..2) dev b : bool { Θ(1) }
si i = 1 entonces b := (p.índice-cima[i] = 0)
si no b := (p.índice-cima[i] = N + 1)
fsi
ffun

3.5. Diseñar una representación dinámica del TAD de las pilas e implementar las operaciones especifica-
das en el ejercicio 3.1.

Solución

Una pila puede representarse mediante una estructura lineal enlazada, de forma que la cima
corresponda al extremo directamente accesible de la estructura, con lo que se consigue que el coste
en tiempo de todas las operaciones sea constante.
La figura 3.3 muestra, utilizando dicha representación, una pila de enteros donde se han apilado,
sucesivamente, los números −5, 2 y 3.
El tipo representante se define de la siguiente manera:

tipos
enlace-pila = puntero a nodo-pila
nodo-pila = reg
valor : elemento
sig : enlace-pila
freg
pila = enlace-pila
ftipos

La pila vacía corresponde al caso en el que el enlace exterior no apunta a ninguna estructura.

fun pila-vacía() dev p : pila { Θ(1) }

p := nil
ffun
78 Estructuras de datos y métodos algorítmicos

En la implementación de las operaciones de apilar y desapilar se utiliza un enlace auxiliar para

hacer la reserva o liberar la memoria dinámica.

proc apilar(e e : elemento, p : pila) { Θ(1) }

var q : enlace-pila
reservar(q)
q ↑.valor := e ; q ↑.sig := p
p := q
fproc
proc desapilar(p : pila) { Θ(1) }
var q : enlace-pila
si p = nil entonces error(Pila vacía)
si no q := p ; p := p ↑.sig
liberar(q)
fsi
fproc
fun cima(p : pila) dev e : elemento { Θ(1) }
si p = nil entonces error(Pila vacía)
si no e := p ↑.valor
fsi
ffun
fun es-pila-vacía?(p : pila) dev b : bool { Θ(1) }
b := (p = nil)
ffun

3.6. Usando la representación dinámica del ejercicio 3.5, programar una función copiar-pila que dada una
pila p devuelva un puntero a una estructura que represente la misma pila que p, pero ocupando
posiciones de memoria diferentes; y un procedimiento anular-pila cuyo efecto sea liberar todo el
espacio de memoria ocupado por la pila p antes de la llamada, dejando como nuevo valor de p la
pila vacía.

Solución

Puesto que la representación dinámica de una pila consiste en una estructura lineal enlazada,
remitimos al lector a la solución dada para el ejercicio 2.8 donde precisamente se describen sen-
dos algoritmos para copiar y anular una estructura lineal enlazada. Tan solo se necesitaría cambiar
nombres de los algoritmos y los tipos de los parámetros para que sean de tipo pila.

3.7. Diseñar una representación de las pilas cuando los elementos son dígitos, utilizando números natu-
rales, e implementar las operaciones especificadas en el ejercicio 3.1.

(a) Considerar dígitos entre 1 y 9.

(b) Considerar dígitos entre 0 y 9.
 Pilas 79

Solución

Apartado (a)

La idea es utilizar números naturales representados en base 10, de forma que el dígito más signi-
ficativo (situado más a la izquierda) corresponde al fondo de la pila, y el dígito menos significativo
(situado más a la derecha) corresponde a la cima. Por tanto, el tipo representante es el siguiente:

tipos
pila-d1 = nat
ftipos

Obviamente, no todo número natural representa una pila, ya que en este primer apartado no se
admiten dígitos 0 en las pilas. La implementación de las operaciones se detalla a continuación. En
primer lugar, la pila vacía se representa con el número cero.

fun pila-vacía() dev p : pila-d1 { Θ(1) }

p := 0
ffun

Para apilar un nuevo dígito debemos añadirlo por la derecha del número que representa la pila,
es decir, sumamos el dígito al número multiplicado por 10.

proc apilar(e d : 1..9, p : pila-d1 ) { Θ(1) }

p := p ∗ 10 + d
fproc

Para desapilar debemos eliminar el dígito menos significativo, es decir, dividimos por 10 el nú-
mero que representa la pila; el resto de dicha división corresponde a la cima de la pila.

proc desapilar(p : pila-d1 ) { Θ(1) }

si p = 0 entonces error(Pila vacía)
si no p := p div 10
fsi
fproc
fun cima(p : pila-d1 ) dev d : 1..9 { Θ(1) }
si p = 0 entonces error(Pila vacía)
si no d := p mod 10
fsi
ffun
fun es-pila-vacía?(p : pila-d1 ) dev b : bool { Θ(1) }
b := (p = 0)
ffun

Suponiendo que las operaciones aritméticas sobre naturales tengan un coste constante, el coste
en tiempo de todas las operaciones también es constante.
80 Estructuras de datos y métodos algorítmicos

Apartado (b)

El problema al admitir el dígito 0 en las pilas es que el número 0 representa tanto la pila vacía
como una pila con uno o varios ceros. En realidad, tenemos problemas para representar cualquier
pila en cuyo fondo haya uno o más dígitos 0, puesto que estos corresponderían a ceros a la izquierda,
que no se consideran en la representación decimal de los naturales. Por esta razón, representaremos
cada pila con un registro con dos números naturales: el primero indica el número de dígitos 0 en el
fondo de la pila, y el segundo representa el resto de los dígitos en la pila. Así, el tipo representante
es el siguiente:

tipos
pila-d2 = reg
ceros-fondo : nat
dígitos : nat
freg
ftipos

La implementación de las operaciones es la siguiente, donde hay que tener cuidado con los ceros
en el fondo de la pila. Por lo demás, las operaciones siguen las ideas de la implementación vista en
el apartado anterior.

fun pila-vacía() dev p : pila-d2 { Θ(1) }

p.ceros-fondo := 0
p.dígitos := 0
ffun
proc apilar(e d : 0..9, p : pila-d2 ) { Θ(1) }
si p.dígitos = 0 entonces { en la pila solo hay ceros }
si d = 0 entonces { se añade un cero al fondo }
p.ceros-fondo := p.ceros-fondo + 1
si no { se añade el primer dígito que no es cero }
p.dígitos := d
fsi
si no { se añade el dígito por la derecha }
p.dígitos := p.dígitos ∗ 10 + d
fsi
fproc
proc desapilar(p : pila-d2 ) { Θ(1) }
si p.dígitos = 0 entonces { en la pila solo hay ceros }
si p.ceros-fondo = 0 entonces error(Pila vacía)
si no { se elimina un cero del fondo }
p.ceros-fondo := p.ceros-fondo − 1
fsi
si no { se elimina el dígito más a la derecha }
p.dígitos := p.dígitos div 10
fsi
fproc
fun cima(p : pila-d2 ) dev d : 0..9 { Θ(1) }
si p.dígitos = 0 entonces { en la pila solo hay ceros }
si p.ceros-fondo = 0 entonces error(Pila vacía)
 Pilas 81

si no { el dígito de la cima es un cero }

d := 0
fsi
si no { se devuelve el dígito más a la derecha }
d := p.dígitos mod 10
fsi
ffun
fun es-pila-vacía?(p : pila-d2 ) dev b : bool { Θ(1) }
b := (p.dígitos = 0) ∧ (p.ceros-fondo = 0)
ffun

Como en el apartado anterior, si suponemos que las operaciones aritméticas sobre naturales
tienen un coste constante, el coste en tiempo de todas las operaciones es constante también.

3.8. Tenemos como dato un vector D[1..N ] que contiene registros, cada uno de los cuales consta de tres
campos con información sobre grandes desastres:

fecha del desastre,

número de víctimas, y
la fecha del último desastre anterior que tuvo más víctimas que el presente.

Los registros del vector están ordenados cronológicamente, del más antiguo al más reciente, pero el
tercer campo está vacío en todos los registros. El objetivo es completar el vector, rellenando el tercer
campo de cada registro a partir de la información que contiene el vector.

(a) Escribir un algoritmo que no utilice ninguna estructura auxiliar y tenga un coste en tiempo en
Θ(N 2 ).
(b) Escribir un algoritmo que utilice una pila como estructura auxiliar y tenga un coste en tiempo
en Θ(N ).

Solución

El tipo registro indicado en el enunciado para representar un desastre es como sigue:

tipos
desastre = reg
fecha : fecha
víctimas : nat+
último : fecha
freg
ftipos

Vamos a representar con el valor especial sin-fecha de tipo fecha el hecho de que no hay ningún
desastre anterior con más víctimas; en particular, esto es siempre cierto para el primer desastre.
82 Estructuras de datos y métodos algorítmicos

Apartado (a)

Dado que el vector ya está ordenado por fechas, basta recorrerlo desde cada posición i hacia la
posición 1, para encontrar el último desastre con más víctimas. Si no existe tal desastre, se llegará a
la “posición” 0.

proc completar1(D[1..N ] de desastre) { Θ(N 2 ) }

para i = 1 hasta N hacer
j := i − 1
mientras j > 0 ∧c D[ j].víctimas ≤ D[i].víctimas hacer
j := j − 1
fmientras
si j = 0 entonces D[i].último := sin-fecha
si no D[i].último := D[ j].fecha
fsi
fpara
fproc

El coste en tiempo de este algoritmo con dos bucles anidados está efectivamente en Θ(N 2 ).

Apartado (b)

Para reducir el tiempo de ejecución, se recurre a la utilización de una estructura auxiliar. En con-
creto, se utiliza una pila, como sugiere el enunciado, de forma que en la misma queden almacenados
solamente los desastres anteriores con un número de víctimas mayor que el último desastre consi-
derado. Los desastres se apilan de tal forma que quedan ordenados cronológicamente, y forman una
sucesión decreciente en el número de víctimas, estando el menor en la cima. El desastre de turno se
compara con los desastres almacenados en la pila, empezando por la cima (que contiene el desastre
en la posición anterior en el vector), hasta encontrar un desastre con un número de víctimas mayor.
Los desastres con un número de víctimas menor o igual pueden descartarse definitivamente, ya que
no pueden ser el último desastre con más víctimas para ninguna de las posiciones del vector que
quedan por considerar. Si la pila se queda vacía, es que no hay ningún desastre anterior con más
víctimas. En cualquier caso, se apila el desastre en estudio para así abordar la siguiente iteración.
Obsérvese que dicha inserción mantiene la propiedad invariante de que los elementos en la pila
forman una sucesión decreciente.

proc completar2(D[1..N ] de desastre) { Θ(N ) }

var p : pila[desastre]
p := pila-vacía()
para i = 1 hasta N hacer
mientras ¬es-pila-vacía?(p) ∧c cima(p).víctimas ≤ D[i].víctimas hacer
desapilar(p)
fmientras
si es-pila-vacía?(p) entonces D[i].último := sin-fecha
si no D[i].último := cima(p).fecha
fsi
apilar(D[i], p)
fpara
anular-pila(p)
fproc
 Pilas 83

punto de interés

... ...

cima-iz cima-dr

Figura 3.4: Secuencia vista como dos pilas enfrentadas.

Nótese el uso de anular-pila para liberar la memoria ocupada por la estructura auxiliar al finalizar
el proceso de completar el vector.
El coste en tiempo de este algoritmo es lineal con respecto al número de desastres, ya que cada
desastre entra en la pila exactamente una vez, y solo se puede desapilar una vez.

3.9. Una secuencia es una estructura lineal con un punto de interés donde se realizan las modificaciones y
las consultas. Especificar el tipo de las secuencias representando una secuencia con un par de pilas,
incluyendo las siguientes operaciones:

crear una secuencia vacía,

insertar un elemento delante del punto de interés,
eliminar el elemento en el punto de interés,
consultar el elemento en el punto de interés,
avanzar en un elemento el punto de interés,
trasladar el punto de interés al comienzo de la secuencia,
determinar si el punto de interés se encuentra al final de la secuencia, y
determinar si la secuencia es vacía.

Solución

Como indica el enunciado, representamos una secuencia mediante un par de pilas: la primera
contiene la parte de la secuencia a la izquierda del punto de interés, y la segunda contiene el punto
de interés y la parte de la secuencia a la derecha de este. La figura 3.4 ilustra esta idea. Conviene
el uso de estructuras LIFO, porque siempre trabajaremos en el mismo extremo de cada parte de la
secuencia (la zona de interés), y que será la cima de la pila correspondiente.
Tenemos, por tanto, una operación constructora libre que construye una secuencia a partir de dos
pilas. Sin embargo, como esta operación constructora es parte de la representación, tiene un cierto
carácter “privado”, de forma que conviene que el usuario de las secuencias desconozca su existencia,
pudiendo utilizar solo las operaciones enumeradas en el enunciado, las cuales estarán definidas en
términos de esta constructora.
Algunas de las operaciones son parciales. En concreto, no se puede avanzar, ni eliminar, ni con-
sultar el elemento actual en el punto de interés si estamos al final de la secuencia.
Como no se exige ningún requisito especial para los elementos de una secuencia, consideramos
la forma más simple de parámetro.
84 Estructuras de datos y métodos algorítmicos

especificación SECUENCIAS[ELEM]
usa PILAS[ELEM], BOOLEANOS
tipos secuencia
operaciones
crear : −→ secuencia
insertar : secuencia elemento −→ secuencia
eliminar : secuencia −→ p secuencia
actual : secuencia −→ p elemento
avanzar : secuencia −→ p secuencia
reiniciar : secuencia −→ secuencia
fin? : secuencia −→ bool
es-sec-vacía? : secuencia −→ bool
operaciones privadas
〈 _, _ 〉 : pila pila −→ secuencia { constructora }
variables
e : elemento
s : secuencia
iz, dr : pila

Al crear una secuencia no existe ningún elemento en el punto de interés, y ambas partes, izquier-
da y derecha, están vacías.

ecuaciones
crear = 〈 pila-vacía, pila-vacía 〉

Al insertar un elemento (por delante del punto de interés) lo colocamos en la parte izquierda; el
punto de interés no cambia.

insertar(〈 iz, dr 〉, e) = 〈 apilar(e, iz), dr 〉

Para eliminar el elemento en el punto de interés tenemos que quitar el primer elemento en la
parte derecha, es decir, el elemento en la cima de la segunda pila.

eliminar(〈 iz, pila-vacía 〉) = error

eliminar(〈 iz, apilar(e, dr) 〉) = 〈 iz, dr 〉

El elemento en el punto de interés se encuentra en la cima de la parte derecha.

actual(〈 iz, pila-vacía 〉) = error

actual(〈 iz, apilar(e, dr) 〉) = e

Al avanzar en la secuencia pasamos un elemento de la parte derecha a la parte izquierda.

avanzar(〈 iz, pila-vacía 〉) = error

avanzar(〈 iz, apilar(e, dr) 〉) = 〈 apilar(e, iz), dr 〉

Para reiniciar la secuencia, debemos pasar todos los elementos de la parte izquierda hacia la parte
derecha.

reiniciar(〈 pila-vacía, dr 〉) = 〈 pila-vacía, dr 〉

reiniciar(〈 apilar(e, iz), dr 〉) = reiniciar(〈 iz, apilar(e, dr) 〉)
 Pilas 85

primero anterior

punto de
interés
sig sig sig sig sig
e1 ...
ek−1 ek ...
en

Figura 3.5: Estructura enlazada para una secuencia.

Estamos al final de una secuencia si su parte derecha está vacía.

fin?(〈 iz, dr 〉) = es-pila-vacía?(dr)

Una secuencia solo es vacía si su parte izquierda y su parte derecha lo son.

es-sec-vacía?(〈 iz, dr 〉) = es-pila-vacía?(iz) ∧ es-pila-vacía?(dr)

fespecificación

3.10. Desarrollar una implementación dinámica del TAD de las secuencias especificado en el ejercicio 3.9,
de manera que todas las operaciones sean ejecutables en tiempo constante.

Solución

La especificación de las secuencias se dio en términos de dos pilas (parte izquierda y parte dere-
cha). Resulta sencillo obtener una implementación de las secuencias mediante pilas, ya sean imple-
mentadas de forma estática (véase el ejercicio 3.3) o de forma dinámica (véase el ejercicio 3.5), pero
en ese caso el coste en tiempo de la operación reiniciar es lineal con respecto al tamaño de la secuen-
cia, ya que es preciso mover todos los elementos de la pila izquierda hacia la pila derecha. En cambio,
la solución que mostramos a continuación, que implementa una secuencia mediante una única es-
tructura lineal enlazada, consigue un coste constante para todas las operaciones de la especificación.
Para ello, necesitamos poder acceder en tiempo constante al primer elemento de la secuencia, para
poder reiniciar en tiempo constante. También necesitamos acceder en tiempo constante al punto de
interés. Como los elementos se insertan por delante del punto de interés (véase la especificación en el
ejercicio 3.9), tenemos que acceder también al nodo anterior al punto de interés. Para no tener que
distinguir el caso especial en el que el punto de interés está en el primer elemento, resulta convenien-
te añadir un nodo “fantasma” a la cabecera de la estructura. Dicho nodo no contiene información real
alguna, pero con su mera existencia se consigue que todo nodo que contiene un elemento real tenga
un nodo anterior. Con todo ello, una secuencia vendrá definida por dos punteros, uno que apunta
al primer nodo de la estructura (el nodo fantasma) y otro que apunta al nodo anterior al punto de
interés. Dicha representación se ilustra mediante el gráfico de la figura 3.5. Así la parte izquierda
comprende desde el nodo siguiente al fantasma hasta el nodo apuntado por anterior; mientras que
la parte derecha va desde el nodo siguiente al apuntado por anterior hasta el final de la estructura.
Con todo esto, el tipo representante es el siguiente:
86 Estructuras de datos y métodos algorítmicos

tipos
enlace-secuencia = puntero a nodo-secuencia
nodo-secuencia = reg
valor : elemento
sig : enlace-secuencia
freg
secuencia = reg
primero, anterior : enlace-secuencia
freg
ftipos

Al crear una secuencia vacía solo creamos el nodo fantasma, adonde apuntarán los dos punteros
de la secuencia.

fun crear() dev s : secuencia { Θ(1) }

var p : enlace-secuencia
reservar(p)
s.primero := p
s.anterior := p
p ↑.sig := nil
ffun

Para insertar un elemento en la secuencia hay que crear un nuevo nodo, que se enlaza en la
estructura por detrás del nodo apuntado por anterior. Dicho nodo pasa a ser el anterior al punto de
interés.

proc insertar(s : secuencia, e e : elemento) { Θ(1) }

var p : enlace-secuencia
reservar(p)
p ↑.valor := e
p ↑.sig := (s.anterior)↑.sig
(s.anterior)↑.sig := p
s.anterior := p
fproc

Las siguientes operaciones se basan en usar adecuadamente la información de anterior. Las tres
primeras dan error si nos encontramos al final de la secuencia.

Para eliminar un elemento se suprime el nodo situado detrás del apuntado por anterior.
Para consultar el elemento actual en la secuencia, se accede al nodo siguiente al apuntado por
anterior.
Para avanzar en la secuencia es suficiente trasladar el puntero anterior al nodo siguiente.
Para reiniciar la secuencia basta trasladar el puntero anterior al nodo fantasma en la cabecera.
Estamos al final de una secuencia si no hay nodos tras el nodo apuntado por anterior.

proc eliminar(s : secuencia) { Θ(1) }

var p : enlace-secuencia
si (s.anterior)↑.sig = nil entonces error(Final de la secuencia)
 Pilas 87

si no
p := (s.anterior)↑.sig
(s.anterior)↑.sig := p ↑.sig
liberar(p)
fsi
fproc
fun actual(s : secuencia) dev e : elemento { Θ(1) }
si (s.anterior)↑.sig = nil entonces error(Final de la secuencia)
si no e := ((s.anterior)↑.sig)↑.valor
fsi
ffun
proc avanzar(s : secuencia) { Θ(1) }
si (s.anterior)↑.sig = nil entonces error(Final de la secuencia)
si no s.anterior := (s.anterior)↑.sig
fsi
fproc
proc reiniciar(s : secuencia) { Θ(1) }
s.anterior := s.primero
fproc
fun fin?(s : secuencia) dev b : bool { Θ(1) }
b := ((s.anterior)↑.sig = nil)
ffun

Finalmente, la secuencia es vacía cuando solo tenemos el nodo fantasma.

fun es-sec-vacía?(s : secuencia) dev b : bool { Θ(1) }

b := ((s.primero)↑.sig = nil)
ffun

3.11. Una expresión aritmética construida con los operadores binarios +, -, *, / y constantes (representa-
dos cada uno por un carácter) se dice que está en forma postfija si, o bien es una única constante,
o bien consiste en dos expresiones en forma postfija una tras otra, seguidas inmediatamente por
un operador. A continuación se presenta un ejemplo de una expresión escrita en la notación infija
habitual junto con su correspondiente forma postfija:

Forma infija: (A/(B − C)) ∗ (D + E)

Forma postfija: ABC − /DE + ∗

Diseñar un algoritmo iterativo que calcule el valor de una expresión dada en forma postfija. Se su-
pone que la expresión viene representada como una secuencia de caracteres (véase el ejercicio 3.9),
y que hay disponibles una función valor que asocia a cada constante su valor numérico (real) y una
función aplicar que realiza la operación aritmética indicada sobre dos números reales dados.
88 Estructuras de datos y métodos algorítmicos

Solución

Para evaluar una expresión en forma postfija, vamos a utilizar como estructura auxiliar una pila
(de números reales) donde iremos almacenando el valor de los operandos de la expresión y de los
resultados intermedios. Se comienza el proceso con una pila vacía y se va recorriendo la secuencia
(que contiene la expresión) de izquierda a derecha. Cada vez que se pasa por una constante, se apila
su valor. Cada vez que se pasa por un operador, se desapilan los dos valores más arriba en la pila,
se componen con el operador (teniendo en cuenta el orden), y se apila el resultado. Al acabar el
proceso la pila contendrá un solo número, que es el valor de la expresión. Aunque el contenido de
la secuencia dada como argumento no se modifica, el punto de interés va cambiando al hacer el
recorrido, por lo que implementamos el algoritmo mediante un procedimiento.

proc evaluar(exp : secuencia[car], r : real )

var p : pila[real]
p := pila-vacía()
reiniciar(exp)
mientras ¬fin?(exp) hacer
x := actual(exp) ; avanzar(exp)
si es-constante?(x) entonces apilar(valor(x), p)
si no { operador }
op2 := cima(p) ; desapilar(p)
op1 := cima(p) ; desapilar(p)
r := aplicar(x, op1 , op2 ) ; apilar(r, p)
fsi
fmientras
r := cima(p) ; desapilar(p)
fproc

3.12. Implementar una función que compruebe si una sucesión de paréntesis abiertos y cerrados está
“equilibrada”, es decir, a cada paréntesis abierto le corresponde uno cerrado, estando bien anidados.
Por ejemplo, ((()())()) está equilibrada, pero (()( no lo está. Se supone que la sucesión viene
dada en una secuencia de caracteres (véase el ejercicio 3.9). Generalizar el ejercicio suponiendo que
además de paréntesis, la sucesión contiene corchetes y llaves que también deberán estar equilibrados.
Así, {([])}() está equilibrada, pero ({]{ no lo está.

Solución

En el caso en el que solo haya paréntesis abiertos y cerrados, basta con recorrer la secuencia
de caracteres manteniendo en un contador cont el número de paréntesis abiertos aún no cerrados.
Si en la posición actual de la secuencia se encuentra un paréntesis abierto, incrementamos cont; si
encontramos un paréntesis cerrado y cont > 0, restamos uno al contador y continuamos. Pero si
encontramos un paréntesis cerrado y cont = 0, entonces la secuencia no está equilibrada. Además, al
terminar de recorrer la secuencia, el contador debe ser cero para que la misma esté equilibrada. El
coste en tiempo de este algoritmo es lineal con respecto al tamaño de la secuencia.

proc equilibrada?1(s : secuencia[car], b : bool )

cont := 0 ; b := cierto ; reiniciar(s)
 Pilas 89

mientras ¬fin?(s) ∧ b hacer

x := actual(s) ; avanzar(s)
si x = ( entonces cont := cont + 1
si no { x =)}
si cont > 0 entonces cont := cont − 1
si no b := falso
fsi
fsi
fmientras
b := b ∧ (cont = 0)
fproc

Cuando además de paréntesis tenemos llaves y corchetes, necesitamos una estructura auxiliar
para guardar los separadores abiertos todavía no cerrados, en el orden en el que han aparecido en
la secuencia. La estructura auxiliar que necesitamos es una pila, ya que los separadores se cierran
en sentido inverso al que se abrieron. Cuando en la secuencia encontramos un separador abierto,
este se apila; cuando encontramos uno cerrado, comprobamos si es la pareja de la cima de la pila,
siempre que esta no sea vacía. Si la pila es vacía o los separadores no forman pareja, la secuencia de
entrada no está equilibrada. Además, al terminar de recorrer la secuencia, la pila debe quedar vacía
para que la misma sea equilibrada.

proc equilibrada?2(s : secuencia[car], b : bool )

var p : pila[car]
b := cierto ; reiniciar(s) ; p := pila-vacía()
mientras ¬fin?(s) ∧ b hacer
x := actual(s) ; avanzar(s)
si es-abierto?(x) entonces apilar(x, p)
si no { x es cerrado }
si es-pila-vacía?(p) entonces b := falso
si no
y := cima(p) ; desapilar(p)
b := es-pareja?(x, y)
fsi
fsi
fmientras
b := b ∧ es-pila-vacía?(p)
anular-pila(p)
fproc

Nótese que si la secuencia está equilibrada, la pila auxiliar quedará vacía al final del proceso,
pero si no está equilibrada, pueden quedar caracteres en la pila, por lo que es oportuno anular la
pila auxiliar.
A pesar de la necesidad de manejar la estructura auxiliar, el coste en tiempo de este algoritmo
también es lineal con respecto al tamaño de la secuencia, como en el caso anterior.